■誕生日のパラドックス(その12)
nTk=k!・nSk
pn,k=k!/k^n・nSk
nSkは第2種スターリング数と呼ばれるもので,漸化式
n+1Sk=nSk-1+knSk
が成り立つ.
nS1=1を出発点として
nS2=2^n-1−1
nS3=3^n-1/2−2^n-1+1/2
nS4=4^n-1/6−3^n-1/2+2^n-2−1/6
一般項は
nSk=1/k!Σ(−1)^k-jkCjj^n
となります.以下,
nS5=(5^n−5・4^n+10・3^n−10・2^n+5)/5!
nS6=(6^n−6・5^n+15・4^n−20・3^n+15・2^n−6)/6!
と続く.
===================================
k!/k^n+1・n+1Sk=pn+1,k
(k−1)!/(k−1)^n・nSk-1=pn,k-1
k!/k^n・nSk=pn,k
を
n+1Sk=nSk-1+knSk
に代入すると,
pn+1,k・k^n+1/k!=pn,k-1・(k−1)^n/(k−1)!+kpn,k・k^n/k!
pn+1,k・k^n+1=kpn,k-1・(k−1)^n+kpn,k・k^n
pn+1,k=pn,k-1・(1−1/k)^n+pn,k
===================================
[まとめ]pn,1=1を出発点として,漸化式を使って,pn,365を求めることができればよいのであるが・・・
===================================