トランプ組み合わせ by AKI
トランプ組み合わせ by AKI
最終更新日: 2002年4月22日（月曜日）
トランプの中から二つのスート（13*2）を抜き出し、それぞれよくきって一枚ずつ照合していくと、同じものがない確立はいくつか？
このままだとわかりにくいので、抽象的かつ一般的に書き直します。このとき、ひとつのスートが常に{1,2,3,4,5,6,7,8,9,10,11,12,13}だったとしても、確率は変わりません（もうひとつのほうを変換することですべての場合に、片方をこのようにすることができる）。また、13となっているとわかりにくいのでnとして、この問題は「n個の数字を並べる順列が、不動点を一つも持たない確率を求めよ」となります。
定義：このとき、M(a,b)は、a個の順列の中で、b個の不動点(n番目がnであるようなもの)があるような物の数を示すとします。
まず､順列を、一番目のものがx1になって、x1番目のものがx2になって、…のものが1になるというような、いくつかの輪として書く。このとき、nの所属する輪に、いくつ数があるか（2個か、3個以上か）で場合分けし、n枚目のカードをその輪から抜いた場合を考えてそれぞれ何通りかを求めていく。
ex . (n=14, 入れ替わった順列={2,11,8,10,12,3,14,6,1,5,13,4,9,7})
輪A 1-2-11-13-9-1
輪B 3-8-6-3
輪C 4-10-5-12-4
輪C 7-14-7
このときを例に考えます。輪Cから14を抜くわけですから、以下のようになります
輪A 1-2-11-13-9-1
輪B 3-8-6-3
輪C 4-10-5-12-4
輪C 7
この輪Cは７ひとつだけですから、これは不動点です。よって、これはM(n-1,1)となります。また、輪Cに残る数はn-1通りあり、輪C以外の部分はn-2個の数字の順列が不動点を一つも持たない場合の数と等しいので、このような場合は(n-1)M(n-2,0)通りとなります。(n≧2)
ex. (n=14, 入れ替わった順列={2,11,8,10,12,7,6,14,1,5,13,4,9,3})
輪A 1-2-11-13-9-1
輪B 3-8-14-3
輪C 4-10-5-12-4
輪C 6-7-6
このときを例に考えます。輪Bから14を抜くわけですから、以下のようになります
輪A 1-2-11-13-9-1
輪B 3-8-3
輪C 4-10-5-12-4
輪C 6-7-6
これは、ちょうどn-1個の数字の順列が不動点を一つも持たない場合の数*(n-1)と等しい(∵ 図のようになるのがM(n-1,0)通りであり、どの"-"を"-14-"にしてn=14にするかが"-"の数、(n-1)通りある)ので、このような場合は(n-1)M(n-1,0)通りとなります。
以上より、M(n+2,0)=(n+1){M(n+1,0)+M(n,0)} であることがわかった。
ここで、P(n)を、適当にn個の数字の順列を作ったときにそれが完全順列（不動点を一つも持たない数列、乱列、すれ違い順列とも呼ぶらしい）となる確率します。
M(n,0)の定義より、P(n+2)=M(n+2,0)/(n+2)!となります。
さらに、A(x)=P(x+1)-P(x)とおきます。
A(x)={M(x+1,0)-(x+1)M(x,0)}/(x+1)! (1)
A(x)={x(M(x,0)+M(x-1))-(x+1)M(x,0)}/(x+1)! (x≧2)
A(x)=(xM(x,0)+xM(x-1)-xM(x,0)-M(x,0))/(x+1)! (x≧2)
A(x)=(xM(x-1,0)-M(x,0))/(x+1)! (x≧2) (2)
また、Aより、A(x-1)=(M(x,0)-xM(x-1,0))/x! (x≧2) (3)
よって、(2)、(3)より、A(x)=-A(x-1)/(x+1) (x≧2) となる。またA(1)=1/2である（M(1,0),M(2,0)を考えれば瞬殺）ので、A(x)=(-1)x+1/(x+1)!となることがわかりました。
以上より、P(x)=1/2-1/6+1/24-1/120+1/720…(-1)x/x!であることが示された。
これを計算すると、P(13)≒0.36787944117144232159552377016155…(=e-1)となります。
xを無限に近づけていくことでe-1に収束するというのはe^xという関数をテイラー展開して、x=-1を代入するとまったく同じ式になることから示せるらしいです。詳しいことはよく知りません。