完全順列

[] [] []


2人がそれぞれ1組のトランプを持って1枚ずつめくっていくとき、途中でカードが一致する確率は63%

n人がプレゼント交換して自分自身のプレゼントに当たる人がいる確率は、nにほとんど関係なく63%

n人がプレゼント交換して自分自身のプレゼントに当たる人数の期待値は、nに関係なく1

これらは完全順列といって、n人を並べ換えたときに再び同じ所に並ばない並べ方、すなわち固定点が0個の順列の問題に帰着する。n個の完全順列の数D(n,0)は包除原理から次のように計算できる。なお、ここの計算は「反直観の数学パズル」(ジュリアン・ハヴィル)によっている。

別の計算方法として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であるとが示せてしまう。

◇◇

なおm個の固定点を持つ順列の数D(n,m) は、前項で求めた一般式「あるm個の事象A1からAn-mが起きてその他の(n-m)個の事象は起こらない確率」からも求められる。

この式において、事象Ak k番目の人が固定点になる事象とすれば、

だからこれらを代入すれば、同じ結果が得られる。


[] [] []