|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
これは，要するに，一筆書きの総数ですね。 気付けば「あ，そうか」なのですが，少し歯ごたえがありました。こんな感じで。 まず，２点の間を n 本の経路で結んだ図を，アｎ，と書くことにします。 例えば，ア１は線分，ア２は円，ア３は円に直径を引いたもの，ア４は円に二本の経路を引いたもの，などと同等です。 これらの一筆書きは，明らかに n! 通りです。 さて，今回の問題で， 中央の円から右端の円に行った場合は，右端の円の一筆書きを終えて中央の円に戻って来るしかありません。 同様に，中央の円から左端の円に行った場合も，左端の円の一筆書きを終えて中央の円に戻って来るしかありません。 そして，右端，左端の円は実際にはア３と同等なので，これら自体の一筆書きは 3! 通りです。 そこで，右端，左端の円＝ア３を除いて代わりに 3! の重みを付けた一つの経路を考えれば， 右下，左下の円が 3! の重み付きの経路を一つもった新たなア３になります。 これより，図を，これらの 3! の重み付きの経路をもった二つのア３を上下でつないだ図に描き直すことができます。 ここで，P は右側のア３の下の経路の集まった点になります。 そして，この図でも経路を一回だけ通るように，一筆書きを考えることになります。 このとき，3! の重み付きの経路も一回しか通らないので， 一筆書きの総数は，通常の一筆書きを考えて，後で 3! * 3! を掛ければいいです。 そこで，この新たな図の P，右側のア３の下の点，からの一筆書きを考えます。 右側のア３から左側のア３へ行った場合は，左側のア３の一筆書きを終えて右側のア３に戻って来るしかないので， 同じようにして，左側のア３をその一筆書き 3! 通りを重みにした経路に置き換えると， 一つの経路の重みが 3! の一つのア４に，さらに図を描き換えられます。 これは，同様にして，ア４の通常の一筆書きが 4! 通りなので，これに経路の重みの 3! を掛ければいいです。 このようにして，先程の 3! * 3! も掛けて，結局，4! * 3! * 3! * 3! = 5184 通り，になります。 一応，経路に重み付けをしながら順番に図を描き換えていきましたが， もちろん，頭が柔軟な方は，一度に，ア３が三つとア４が一つが，順番に入れ子になった図を描いてもいいですね。 |
|
ネコの住む家
4月5日（木） 12:22:05
39188 |