「もっとプログラマ脳を鍛える数学パズル」Q39の別解がわかりません

Question

「もっとプログラマ脳を鍛える数学パズル」という本に載っている
「Q39 隣り合うと消えちゃうんです」の別解の解説でわからないところがあります。
どなたか教えていただけいただけないでしょうか？

問題は以下です。

解説は以下です。



解答コードは以下です。

N = 11

@memo = {1 => 0, 2 => 1}
def pair(n)
  return @memo[n] if @memo[n]
  @memo[n] = (2 * (n - 1) + 1) * pair(n - 1) + pair(n - 2)
end

puts pair(N)

漸化式の変形部分などは理解できたのですが、
理解できないのは解説の total()関数で i ＝ 0 ～ n-1 までを足していっているところです。
足すと言うことは、Nがどんなに大きくても、
題意を満たす(隣り合っていない)pair(3)やpair(4)に対応した、
題意を満たしていない(隣り合っている)のに消えない残りの色の並びが必ずあると言うことでしょうか？
もしそうならそれはどのような並びになっているのでしょうか？

例えばNがある程度大きい数で、pair(3)の時の色を数字で表すと、
「123123」と並んでいるのに対し残りの445566778899....はどのように並んでいるのでしょうか？
宜しくお願いします。

Comments

[Y.H.]

著作物の複製(写真)を載せてられますが大丈夫ですか？

[pyxis]

引用ルールの範囲内だと考えております。
しかしサイト運営や著者、出版社の方から取り消すよういわれればこの質問を削除します。

Answer 1

解説には特に書いてないようですが、123123に対して4567654 (pair(7)の場合)を挿入するような場合でしょう(結果7_123_4567654_123のようになる)。

上の例で分かるように連続した色の間に新しい色を挿入できる場合について、n - 2色の並びが連続して"いない"必要はありません。
試しに上の例で6と7を削除すると4554となり、n - 2色について同色が連続するようになります。n - 3についても同様(44になる)で、n - 4で初めて連続しない並びになりそれに対応するのがpair(3)です。

totalのn-1についてはもともと同色の間に挿入する場合ではないので、対応する並び方はありません。
totalではn - 2までを足すようにして、別に2(n - 1) * pair(n - 1)を足すと考えたほうがわかりやすいでしょう。

Comments

[pyxis]

理解できました、ありがとうございます。
確かに残りの数字を456654のように左右対称に並べれば
123_456654_123
123_4554_123
123_44_123
のようにどれだけ数が増えようと連続する数値の所を除いてもまたその隣同士が連続になるので
その数列は絶対にpair(n)に含まれないので全ての場合で排反になる(被りが存在しない)。
そして最後の数字で分割することにより題意を満たす(連続するところがなくなる)のですね。