一つの答えから、対称形・合同形を考えることで、9,984(=2の8乗×3×13)通りの入れ方が出来るものがある
というのが前回の話でした。
素因数分解に出てくる2や3は前回の例であったように、対称形や合同形でよく出てきます。
では13って一体どんな形なんでしょう。
初めは全くわかりませんでしたが、前回の記事を考えている時に、たまたま次のようなものを見つけたのがヒントになりました。
こちらのブログのこちらの記事です。参考にさせてもらいます。
次のような解が載っていました。
この5つのピースは１２３４５の順の列として見ると、どの隣り合う2つも入れ換えることができます。
このような場合は何通りの入れ方があるでしょうか。
まず3つぐらいから考えてみましょう。
3つのピースが並んでいて隣り同士入れ換えられる場合は、123,132,213の三通りあります。
4つの場合、5つの場合と増やしていくとどうなるでしょう。
ここはカッコつけて、一気に一般のn個の場合を考えてみましょ。つまり次の問題です。
「1からnまでのピースが番号順に並んでいるとします。
任意のkとk+1 (k=1,・・・n-1) が入れ換え可能であるとき、全部で何通りの並べかたがあるか？」
解答は以下のような感じでどうでしょう。
i個のピースの場合の並べ方の個数をA(i)と書くことにします。
先頭に注目しましょう。先頭に入るのは1か2のどちらかですので、その2通りに場合分けできます。
・1の場合、2番目以降のn-1個のの並べ方は、A(n-1)通りです。
・2の場合は、2番目は必ず1になります。3番目以降の残りのn-2個の並べ方はA(n-2)通りとなります。
すると
A(n)=A(n-1)+A(n-2)
となりますね。
おっと！フィボナッチ数列ですね。こんな所で出会うとは。
正確にいうとA(1)=1, A(2)=2, A(3)=3ですから、フィボナッチ数列の2番目以降ということになります。
フィボナッチ数列Fnの一般項は、ネットで調べますと
となるようです。
今求めたいA(n)は一つずれていますので
となります。これが上の問題の答えです。めでたしめでたし
もっと簡単な式が出るかなと思ってやり始めたんですが、なんか難しい式が出てきちゃいましたね。
とはいえ、晴れて一般項が出たわけです。具体的な数字を入れて確かめてみましょう。
A(1)=1, A(2)=2, A(3)=3, A(4)=5, A(5)=8
となりますね。
つまり上の画像のパターンの5個の場合は8通りの入れ方があるというわけです。
そしてA(6)=13です。
ふぅ、やっと出ました13です。これを出したいがためにずいぶんかかりました。
つまり「6個のピースがそれぞれ隣り合って一列と見なせる時に、どの隣り合う2つも入れ換えが可能な形」
これが含まれていれば13が出てきます。おそらく9984通りできるパターンにはこの形が入っているんじゃないでしょうか。
てことで上の例に一つ繋げて、こんな形でどうでしょう。
6ピースからなる列ができています。
さあ、これが入る形で残りのピースが埋められるのでしょうか！？果たして？
時間がある時に考えてみたいと思います。
ちなみにヘプタモンドのピースは全部で24個。
24個が全て隣りと入れ換えられるような列でぴったりはまれば、n=24でA(24)=75,025通りです！
まあこんな入れ方はさすがにないわなぁ。
でも実現可能な最長列はどのぐらいか、今度考えてみようかな。