完全順列
|
・2人がそれぞれ1組のトランプを持って1枚ずつめくっていくとき、 途中でカードが一致する確率は63% ・n人がプレゼント交換して自分自身のプレゼントに当たる人がいる確率は、 nにほとんど関係なく63% ・n人がプレゼント交換して自分自身のプレゼントに当たる人数の期待値は、 nに関係なく1人 |
これらは完全順列といって、n個を並べ替えたときに再び同じ所に並ばない並べ方、すなわち固定点が0個の順列の問題に帰着する。n個の完全順列の数D(n,0)は包除原理から次のように計算できる。なお、ここの計算は「反直観の数学パズル」(ジュリアン・ハヴィル)によっている。
別の計算方法として、n個のうち固定点がk個の順列の数はD(n-k,0)個で、k=0からnまで全部たすと通常の順列の数n!に等しくなるから
これに2項係数の反転公式を適用すれば(→補足-2項係数の反転公式)
と求められる。
さて、この和はn→∞のとき、指数関数exのテイラー展開でx=-1とおいた級数になるから1/eに収束し、しかも収束が速い。実際に計算してみるとn=4ぐらいで1/e=0.37に収束する。したがって、プレゼント交換で自分自身のプレゼントに当たる人がいる確率は人数にほとんど関係なく63%となる。
◇
さらに拡張してm個の固定点を持つ順列の数D(n,m)も計算できる。すなわちm個の固定点の選び方はnCm通りあり、残り(n-m)個が完全順列であればいいから
具体的に数値を計算してみると次図のようになる。
特徴的なのは、n個中n-1個が固定点になることはありえないのでゼロになっていることである。
またnを大きくしていくと、mが小さい範囲では
となるから、確率D(n,m)/n! はnが大きくなると平均値1のポアソン分布に収束する。
実は、固定点の数の期待値はnに関係なく常に1であることが示せてしまう。
◇◇
なおD(n,m) は、前項で求めた「あるm個の事象A1からAn-mが起きてその他の(n-m)個の事象は起こらない確率」の式からも求められる。
この式において、事象Akを k番目の人が固定点になる事象とすれば、
だからこれらを代入すれば、同じ結果が得られる。