2006/10/29に書いた「My Quiet Book」問題とその答えです。
N組のボタンとそれに留める花の形の布がある。N個のボタンはすべて違う色で、最初の状態では花は留めてあるボタンと同じ色である。花とボタンの組み合わせを変えて、N組のボタンと花がすべて違う色になっているようにしたい。何通りのやり方があるか？
m組のボタンと花をすべて違う色にするやり方の数を P(m) とする。P(1) = 0, P(2) = 1。
m >= 3 について、ボタン1に花kがついているとする（2 <= k <= m）。それぞれについて、ボタンkに花1がついている場合とそれ以外の場合に分ける。前者の場合、残りの m - 2 個のボタンは1,k以外のボタン／花の組み合わせになるので、P(m - 2) 通り。後者の場合、ボタンkについている花をk'とすると、ボタン1に花kの代わりに花k'をつけてボタンkと花kを除いてしまうと、k 以外の m - 1 個の組み合わせになり、P(m - 1) 通りの場合がある。従って、
[1] P(m) = (m - 1)(P(m - 1) + P(m - 2))
P(m)/m! = Q(m) とおいて [1] を変形すると、
[2] m!Q(m) = (m - 1)((m - 1)!Q(m - 1) + (m - 2)!Q(m - 2)) = m!Q(m - 1) - (m - 1)!Q(m - 1) + (m - 1)!Q(m - 2) [3] ∴ m!(Q(m) - Q(m - 1)) = (-1)(m - 1)!(Q(m - 1) - Q(m - 2))
[3] を用いて m を順に 1 まで減らして行くと、
[4] m!(Q(m) - Q(m - 1)) = (-1)(m - 1)!(Q(m - 1) - Q(m - 2)) = (-1)2(m - 2)!(Q(m - 2) - Q(m - 3)) = ... = (-1)m2!(Q(2) - Q(1)) = (-1)m [5] ∴ Q(m) - Q(m - 1) = (-1)m/m! (m >= 3)
[5] は m = 2 でも成り立つ。m = 2 から N まで [5] の和をとると、
[6] Q(N) - Q(1) = sum(m=2,N){(-1)m/m!} (N >= 2)
Q(N) = P(N)/N!, Q(1) = 0 を代入して整理すると、
[7] P(N) = sum(m=2,N){(-1)mN!/m!} (N >= 2)
なお、[7] の右辺を0からNまでの和とすると、N >= 2 に対しては値は変わらず、P(1) に対しても成り立つようになる。すなわち、
[8] P(N) = sum(m=0,N){(-1)mN!/m!}
（以下、2006/11/01 に最初に書いたもの。上の答えの方がはるかに簡潔）
m組のボタンと花をすべて違う色にするやり方の数を P(m) とする。
N組のボタンと花の組み合わせは全部で N! 通りある。この中で、k組が違う色で(N-k)組が同じ色になっている組み合わせの数を考える。k組を選び出す方法が NCk 通りあり、それぞれについてk組を違う色にするやり方が P(k) 通りあるので、このような組み合わせの数は NCkP(k) である。k を 0 から N まで変化させて和をとるとすべての場合を網羅するので、その和は N! に等しい。すなわち、
[1] sum(k=0,N){NCkP(k)} = N!
（総和記号は画像を使わないと書きづらいため、sum(k=0,N){...} で「... を k = 0 から N までとった総和」の意味とする。）
なお、上の式で「すべてが同じ色」になっている組み合わせは k=0 の項に対応する。これは NC0P(0) = P(0) に相当する。すべてが同じ色の組み合わせは１つしかないので、P(0) = 1 となる。P(0)は形式的には「０個のボタンと花がすべて違う色の組み合わせの数」となるが、上の式の一貫性を保つため P(0) = 1 と定義する。
さて、[1] 式で k=N の項を分離して移項すると、[2] 式を得る。
[2] P(N) = N! - sum(k=0,N-1){NCkP(k)}
ここで、右辺が次の [3] 式と等しいことを数学的帰納法で証明する。
[3] sum(k=0,m-1){(-1)kNCN-k*(N-k)!} + (-1)msum(k=0,N-m){NCk*N-k-1Cm-1*P(k)} (m = 1, 2, ..., N)
まず、m = 1 の時は [3] 式と [2] 式の右辺は全く同じになる。
次に、一般の m について、[3] の第２項の sum を次のように変形する。
[4] (-1)msum(k=0,N-m){NCk*N-k-1Cm-1*P(k)} = (-1)mNCN-m*m-1Cm-1*P(N-m) + (-1)msum(k=0,N-m-1){NCk*N-k-1Cm-1*P(k)} # k = N - m の項を分離 = (-1)mNCN-m*((N-m)! - sum(k=0,N-m-1){N-mCkP(k)}) + (-1)msum(k=0,N-m-1){NCk*N-k-1Cm-1*P(k)} # [2] で N を N - m で置き換えたものを第一項に代入 = (-1)mNCN-m*(N-m)! + (-1)m+1sum(k=0,N-m-1){NCN-m*N-mCkP(k) - NCk*N-k-1Cm-1*P(k)}
sum の中の P(k) の係数を変形すると、
[5] NCN-m*N-mCk - NCk*N-k-1Cm-1 = N!/(m!(N-m)!)*(N-m)!/(k!(N-m-k)!) - N!/(k!(N-k)!)*(N-k-1)!/((N-m-k)!(m-1)!) = N!/(m!k!(N-m-k)!) - N!(N-k-1)!/(k!(N-k)!(N-m-k)!(m-1)!) = {N!(N-k)! - mN!(N-k-1)!}/(m!k!(N-m-k)!(N-k)!) = N!(N-k-1)!(N-k-m)/(m!k!(N-m-k)!(N-k)!) = N!(N-k-1)!/(m!k!(N-m-k-1)!(N-k)!) = NCk*N-k-1Cm
従って、[4] の右辺は次のようになる。
[6] [4]の右辺 = (-1)mNCN-m*(N-m)! + (-1)m+1sum(k=0,N-m-1){NCk*N-k-1CmP(k)}
[3] の第２項にこれを代入して、 [7] sum(k=0,m-1){(-1)kNCN-k*(N-k)!} + (-1)msum(k=0,N-m){NCk*N-k-1Cm-1*P(k)} = sum(k=0,m-1){(-1)kNCN-k*(N-k)!} + (-1)mNCN-m*(N-m)! + (-1)m+1sum(k=0,N-m-1){NCk*N-k-1CmP(k)} = sum(k=0,m){(-1)kNCN-k*(N-k)!} + (-1)m+1sum(k=0,N-m-1){NCk*N-k-1CmP(k)}
[7] の最右辺は [3] の m を m+1 に置き換えたものになっている。これで数学的帰納法が成立し、すべての m (<= N) について [3] が P(N) に等しいことが示された。
[3] で m = N と置くと、
[8] P(N) = sum(k=0,N-1){(-1)kNCN-k*(N-k)!} + (-1)N{NC0*N-1CN-1*P(0)} = sum(k=0,N-1){(-1)kNCN-k*(N-k)!} + (-1)N = sum(k=0,N){(-1)kNCN-k*(N-k)!} = sum(k=0,N){(-1)kN!/k!} # 書き換えただけ
従って、問題の答えは、
[9] P(N) = sum(k=0,N){(-1)kN!/k!}
なお、漸化式を使うと次のように表記できる。
[10] P(N) = P(N-1)*N + (-1)N P(0) = 1
題意からこの漸化式が直接導ければもっと簡単に解けるのだけど、うまい解釈を思いつかなかった。（2006/11/5追記：この式ではないが、「答え１」では簡単な漸化式を直接導いている。）
ちなみに、N = 0 から 20 までの値を python で計算してみた。
% cat sample.py p = 1 sn = -1 for i in range(21): print i, p p = p * (i+1) + sn sn = -sn % python sample.py 0 1 1 0 2 1 3 2 4 9 5 44 6 265 7 1854 8 14833 9 133496 10 1334961 11 14684570 12 176214841 13 2290792932 14 32071101049 15 481066515734 16 7697064251745 17 130850092279664 18 2355301661033953 19 44750731559645106 20 895014631192902121 %