(O+P)ut

アウトプット



(O+P)ut

エンジニアのアウトプット

【モンモール数】プレゼント交換が成功する確率

スポンサーリンク

プレゼント交換が成功する確率

5人が持ち寄ったプレゼントをシャッフルしてから5人に配る時、プレゼント交換が成功する(全員が自分以外のプレゼントを受け取る)確率は何パーセントでしょうか?

また

10人が持ち寄ったプレゼントをシャッフルしてから10人に配る時、プレゼント交換が成功する確率は何パーセントでしょうか?

f:id:mtiit:20190405231753j:plain

この答え、どちらも約37%です。

さらに、100人でも1000人でも、人数が何人に増えてもこの確率はほぼ変わりません

この直感に反する現象は、モンモール数(Montmort number)という値で扱われます。

本記事では、この値について簡単に解説しています。



モンモール数とは?

例えば、(1,2,3)という要素の並び替えを考えます。
1の帽子をかぶった人、2の帽子をかぶった人、3の帽子をかぶった人を一列に並べるのと同義です。

その組み合わせは
(1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1) の6通り、いわゆる3の階乗です。

3! = 3x2x1 = 6 

この中でそれぞれの要素が元の位置にいない組み合わせ
(2,1,3) (3,1,2)の2通りだけです。
これは、冒頭でいう「プレゼント交換が成功する場合」でもあります。

それを、要素の数が3のモンモール数は2という言い方をします。

そんなモンモール数、計算はかなりシンプルな式で行えます。

要素の数がNのモンモール数 =
( N - 1 ) x (要素の数がN-1のモンモール数 + 要素の数がN-2のモンモール数)

証明は割愛しますが、実際に確認してみます。

例えば、要素の数が4のモンモール数を数え挙げてみます。

(2,1,4,3) (2,3,4,1) (2,4,1,3) (3,1,4,2) (3,4,1,2) (3,4,2,1) (4,1,2,3) (4,3,1,2) (4,3,2,1)

この9通りです。

要素が3のモンモール数が2であるのは既に確認したので、要素が2のモンモール数を求めます。
これは簡単で、(2,1)の1通りで1です。

先ほどの式に当てはめてみます。

( 4 - 1 )x( 2 + 1 ) = 9

確かに式は満たしています。

これを実際にN=10まで計算したのが以下の表です。

要素の数 モンモール数 組み合わせの総数 プレゼント交換が成功する確率(%)
1 0 1 0
2 1 2 50
3 2 6 33.33333333
4 9 24 37.5
5 44 120 36.66666667
6 265 720 36.80555556
7 1854 5040 36.78571429
8 14833 40320 36.78819444
9 133496 362880 36.78791887
10 1334961 3628800 36.78794643

確かに約37%で収束しています。

終わりに

プレゼント交換が成功する確率は人数の増減で変動しない、という直感に反する事実を実際に計算して確認しました。
モンモール数という言葉自体よりも、直感に反する事象があるということで確率のおもしろさが伝われば幸いです。