ザ計算力

解答(その18)の末尾の式を計算するために、
σ'(M,N) ≡ Σ_k=0^M (-1)^k _MC_k k^N
を計算する。

M≧2では、
σ'(M,1) = Σ_k=0^M (-1)^k _MC_k k
　= Σ_k=1^M (-1)^k _MC_k k = (d/dx)Σ_k=0^M _MC_k x^k |_x=1
　= (d/dx)(1-x)^M|_x=1 = -M(1-x)^M-1|_x=1 = 0
σ'(M,N+1) = Σ_k=0^M (-1)^k _MC_k k^N+1
= Σ_k=1^M (-1)^k _MC_k k^N+1
= Σ_k'=0^M-1 (-1)^k'+1 _MC_k'+1 (k'+1)^N+1
ここで
_MC_k'+1 (k'+1) = (k'+1)M!/[(k'+1)!(M-k'-1)!] = M(M-1)!/[k'!(M-1-k')!] = M _M-1C_k'
を使うと、
σ'(M,N+1) = -M Σ_k'=0^M-1 (-1)^k' _M-1C_k' (k'+1)^N
この式に
(k'+1)^N = 1 + Σ_r=1^N _NC_r k'^r　(k'=0の場合についても考えるのでr=0の項を分けて書いた)
を代入すると、
σ'(M,N+1) = -M Σ_k'=0^M-1 (-1)^k' _M-1C_k' (1 + Σ_r=1^N _NC_r k'^r)
= - M Σ_k'=0^M-1 (-1)^k' _M-1C_k' -M Σ_r=1^N _NC_r σ'(M-1,r)
ここで
Σ_k'=0^M-1 (-1)^k' _M-1C_k' = (1+x)^M-1|_x=-1 = 0
を使うと、
σ'(M,N+1) = -M Σ_r=1^N _NC_r σ'(M-1,r)
この式を2次元的な漸化式の様なものと見なし、
σ'(M,1) = 0　(M≧2)
を使うと、
σ'(M,N) = 0　(M≧N+1≧2)
だと分かる。
---
最終更新日時2011/03/04/10:24JST

解答(その19)の結果を解答(その18)の式に代入すると、

n≧n'≧3では、
Π₁(n,n') - n'Π₁(n-1,n'-1) = Σ_k=2^n' (-1)^n'-k _n'C_k [n'k^n-1 + k² - (n'+1)k]
= Σ_k=0^n' (-1)^n'-k _n'C_k [n'k^n-1 + k² - (n'+1)k] - Σ_k=0¹ (-1)^n'-k _n'C_k [n'k^n-1 + k² - (n'+1)k]
= (-1)^n'[n'σ'(n',n-1) + σ'(n',2) -(n'+1)σ'(n',1)]　∵Σ_k=0¹ (-1)^n'-k _n'C_k [n'k^n-1 + k² - (n'+1)k] = 0
= (-1)^n'n'σ'(n',n-1)　∵σ'(n',2)=0,σ'(n',1)=0

σ'(n',2)=0,σ'(n',1)=0の成立は、
解答(その19)の結果：
σ'(M,N) = 0　(M≧N+1≧2)
にM=n',N=1,2を代入する事によって、分かります。

---
最終更新日時2011/03/09/10:42JST

解答(その20)と解答(その18)の結果を解答(その15)の式に代入すると、

n≧365の場合には、
(挙手者数の期待値) = (n/365ⁿ)Σ_n'=1³⁶⁵ ₃₆₅C_n' [Π₁(n,n') - n'Π₁(n-1,n'-1)]
= (n/365ⁿ)[365 + ₃₆₅C₂ (2ⁿ-4) + Σ_n'=3³⁶⁵ ₃₆₅C_n' (-1)^n'n'σ'(n',n-1)]
= (n/365ⁿ)[365 + (365×364/2)(2ⁿ-4) + Σ_n'=3³⁶⁵ ₃₆₅C_n' (-1)^n'n'Σ_k=0^n' (-1)^k _n'C_k k^n-1]
= (n/365ⁿ)Σ_n'=1³⁶⁵ ₃₆₅C_n' (-1)^n'n'Σ_k=0^n' (-1)^k _n'C_k k^n-1
= (n/365ⁿ)Σ_n'=1³⁶⁵ ₃₆₅C_n' (-1)^n'n'Σ_k=1^n' (-1)^k _n'C_k k^n-1
ここで、
₃₆₅C_{n' n'}C_k = {365!/[n'!(365-n')!]}{n'!/[k!(n'-k)!]}
= 365!/[(365-n')!k!(n'-k)!] = {365!/[k!(365-k)!]}{(365-k)!/[(365-n')!(n'-k)!]}
= ₃₆₅C_{k 365-k}C_n'-k
および、
Σ_n'=1³⁶⁵ Σ_k=1^n' = Σ_k=1³⁶⁵ Σ_n'=k³⁶⁵
を使うと、
(挙手者数の期待値) = (n/365ⁿ)Σ_k=1³⁶⁵ ₃₆₅C_k (-1)^k k^n-1 Σ_n'=k³⁶⁵ _365-kC_n'-k (-1)^n'n'
ここで、k≦363では、
Σ_n'=k³⁶⁵ _365-kC_n'-k (-1)^n'n' = (-1)^k Σ_n'-k=0^365-k _365-kC_n'-k (-1)^n'-k(n'-k) + k (-1)^k Σ_n'-k=0^365-k _365-kC_n'-k (-1)^n'-k
= (-1)^k σ'(365-k,1) + k (-1)^k (1+x)^365-k|_x=-1
= (-1)^k σ'(365-k,1)
= 0　∵365-k≧2[解答(その19)参照]
を使うと、
(挙手者数の期待値) = (n/365ⁿ)[₃₆₅C₃₆₄ (-1)³⁶⁴ 364^n-1 Σ_n'=364³⁶⁵ _365-364C_n'-364 (-1)^n'n'
　　　　　　　　　　　　　　　　　　　　　+ ₃₆₅C₃₆₅ (-1)³⁶⁵ 365^n-1 Σ_n'=365³⁶⁵ _365-365C_n'-365 (-1)^n'n']
= (n/365ⁿ)[365×364^n-1(364-365)-365^n-1×(-365)]
= (n/365ⁿ)[-365×364^n-1 + 365ⁿ]
= n[1 - (364/365)^n-1]

2≦n≦365の場合には、
(挙手者数の期待値) = (n/365ⁿ)Σ_n'=1ⁿ ₃₆₅C_n' [Π₁(n,n') - n'Π₁(n-1,n'-1)]
= (n/365ⁿ)[365 + ₃₆₅C₂ (2ⁿ-4) + Σ_n'=3ⁿ ₃₆₅C_n' (-1)^n'n'σ'(n',n-1)]
= (n/365ⁿ)Σ_n'=1ⁿ ₃₆₅C_n' (-1)^n'n'σ'(n',n-1) ∵σ'(1,n-1)=-1,σ'(2,n-1)=2^n-1-2[解答(その19)参照]
ここで
σ'(n',n-1) = 0　(n'≧n≧2)
を使うと、
Σ_n'=1ⁿ を Σ_n'=1³⁶⁵ に書き換えても計算結果は変わらない事が分かる。
したがって、
(挙手者数の期待値) = (n/365ⁿ)Σ_n'=1³⁶⁵ ₃₆₅C_n' (-1)^n'n'σ'(n',n-1)
以下、n≧365の場合と同様にして、
(挙手者数の期待値) = n[1 - (364/365)^n-1]

n=0の場合とn=1の場合には挙手者数は必ずゼロに成るので、挙手者数の期待値はゼロだ。
一方、n=0の場合とn=1の場合には n[1 - (364/365)^n-1]=0
従って、n=0の場合とn=1の場合も、
(挙手者数の期待値) = n[1 - (364/365)^n-1]

以上をまとめると、全ての非負整数nに対して、
(挙手者数の期待値) = n[1 - (364/365)^n-1]
---
最終更新日時2011/03/09/10:34JST

以下は、当時の私の「物理とともに」への投稿の一つです。

この問題が怨念によって埋もれさせられている、という意味ではない。
私が解き始めた時には既に埋もれていた。
この問題についての一連の投稿の事を私は、怨念の歴史、と呼んでいます。

参考までに、解答(その7)の計算を初めて行なった当時の資料を以下に掲載しておく。
番号の付け方が解答(その7)と若干違う事、に気を付けて下さい。


---
最終更新日時2011/01/18/09:36JST

誰かからメールで教えてもらった解法は次の様なものだった、と思う。

n人の中の1人に着目した時、その人が手を挙げないのは、他のn-1人の誕生日が全て、その人の誕生日と異なる場合で、そうなる確率は(364/365)^n-1だ。

したがって、その人が手を挙げる確立は1-(364/365)^n-1だ。

その様な人がn人いるのだから、挙手者数の期待値は、n[1-(364/365)^n-1]だ。

これに対して私は、各人が手を挙げるか挙げないかは互いに独立ではないので、一人が手を挙げる確率に単純にnを掛けてはいけないのではないか、と聞き返した。

教えてくれた人も、その点については分からない、との事だった。

因みに、この人とのやり取りは、険悪な雰囲気には成らなかった、つもりだ。

---
最終更新日時2011/02/06/10:52JST