00/11/04 11:00
n 人が 1列に並んだときに、順序を保つ組の数が k であるような
並び方の総数を A(n,k) で表すと
A(n,0) = (n-1)*A(n-1,0) + A(n-1,1)
だけど
A(n,1) = (n-1)*A(n-1,0)
だから、結局
A(n,0) = (n-1)*A(n-1,0) + (n-2)*A(n-2,0), A(1) = A(2) = 1
求める確率は P(n) = A(n,0)/n! だから
P(n) = {(n-1)/n}*P(n-1) + {(n-2)/{n(n-1)}}*P(n-2), P(1) = 1, P(2) = 1/2
ここで
Q(n) = {n/(n+1)}*P(n)
と定義すると
Q(n) - Q(n-1) = {-1/(n+1)}*{Q(n-1) - Q(n-2)},
Q(1) = 1/2 = 1/2!, Q(2) = 1/3 = 1/2! - 1/3!
だから
Q(n) - Q(n-1) = (-1)^{n-2}/{(n+1)n(n-1)…4}*{Q(2) - Q(1)} = (-1)^{n+1}/(n+1)!
よって
Q(n) = Σ[k=1,n] (-1)^{k+1}/(k+1)!
以上より
P(n) = {(n+1)/n} Σ[k=1,n] (-1)^{k+1}/(k+1)!