確率か組み合わせか

diary

誕生日のパラドックスというものがあります。
たとえば、1クラス50人の中に、誕生日が同じペアが一つ以上いる確率はどれくらいか？ という問題の答えがそれ。誕生日の選択肢は365日もあるのだから、たった50人の集団に同じ誕生日の人がいる確率は凄く低いのでは…？ と感じてしまうのはマチガイ。


この答えは次のようになります。
誕生日が同じペアがいる確率を p とすると、誕生日が同じペアがいない確率は 1-p になります。これがミソ。自分以外の 49 人の誕生日が自分の誕生日以外である確率 1-p は、


1-p = \frac{364}{365} \cdot \frac{363}{365} \cdot \cdot \cdot \frac{364-48}{365} = 0.029


従って、求めたい確率 p は


p = 1-0.029= 0.971


となります。なんと、97%の確率で同じ誕生日の人のペアがいる計算になります。
感覚的には、まあ居れば運が良いかな…程度に思えるのに、実際に計算をするとこんなに高確率である、というところがパラドックスである由。なかなか面白い話です。
ここまでが前置き。

それでは…

1年は365日です。
では、365人以上（たとえば1000人）からなる集団があったとき、すべての誕生日の人が揃っている確率はどれくらいでしょう？


（ここからしばらく間違っているため畳みます　読まないでね！）



これは並べ替えの問題になります。
まず、おさらいですが、n個のお互いに区別のないものを mグループに分けるとき、分け方は何通りになるでしょうか。
これはこう考えるといいです。
n個の○（もの）を、m-1個の|（区切り）で区切ってやるのです。
たとえば、10個の○を7グループに分けるとすると、

○|○○○||○|○○○||○○

となります。10個の「○」が6本の「|」で7グループに分かれました。
ではこの分け方は何通りあるでしょうか？
ここで見方を変えてみます。つまり、「16個の（○か|）の中から10個の○を選ぶ」のは何通り？ という問題にすりかえてしまいます。
これは簡単で、 {}_{16}\mathrm{C}_{10}=8008 通りです。


すなわち、 n 個のものを m グループに分ける分け方は、

{}_{n+m-1}\mathrm{C}_{m-1} = \frac{(n+m-1)!}{n!(m-1)!}

ということになります。


ところで、最初の問題は「1000人の集団があるとき、365日すべての誕生日の人が揃っている確率は？」というようなものでした。

ここに今の考え方を当てはめてみると…
まず、1000人を365日に分ける方法が何通りあるかを計算してみます。
これは上の公式そのままですね。つまり、


{}_{1000+365-1} \mathrm{C}_{365-1} = {}_{1364}\mathrm{C}_{364} = \frac{1364!}{1000!364!}


だいたい 1.08 \times 10^{342} くらいです。
次に、365日すべてに人がいるという条件下で、1000人を365日に分ける方法が何通りあるかを計算します。
これはつまり、「最初から365日に一人ずつを振り分けてやってから、残りを適当に振り分けるときの分ける方法の数」ですから、1000-365人 を 365日に振り分ける方法の数になります。すなわち、


{}_{635+365-1} \mathrm{C}_{365-1} = {}_{999}\mathrm{C}_{364} = \frac{999!}{635!364!}


これは 9.60 \times 10^{282} くらいです。


これで確率を求める準備が整いました。求めたい確率 p は、「すべての誕生日の人がいる選び方の数÷すべての選び方の総数」ですから、


p = \frac{999!}{635!364!} / \frac{1364!}{1000!364!} = \frac{9.60 \times 10^{282}}{1.08 \times 10^{342}} = 8.89 \times 10^{-60}


つまり、0.0000000000000000000000000000000000000000000000000000000000889 です。低いですね！


ちなみに、10000人で1.69 \times 10^{-6}、100000人で0.26になります。
というわけで、（この結果が正しいとすれば）思ったよりもずっとたくさんの人がいる必要があるようです。


と、わざわざ急にこんなエントリを書いたのは、正しいかどうか自信がないからです。数学に詳しい方、アドバイスください…。

検算


5人が集まって、誕生日の候補日が5日〜1日に限定されている条件でやってみましょうか。

人の分かれ方 埋まる日数 5日 4日 3日 2日 1日
○○○○○ 1日 5通り 4通り 3通り 2通り 1通り
○｜○○○○ 2日 20通り 12通り 6通り 2通り -
○○｜○○○ 2日 20通り 12通り 6通り 2通り -
○｜○｜○○○ 3日 30通り 12通り 3通り - -
○｜○○｜○○ 3日 30通り 12通り 3通り - -
○｜○｜○｜○○ 4日 20通り 4通り - - -
○｜○｜○｜○｜○ 5日 1通り - - - -
すべての条件 　 126通り 56通り 21通り 6通り 1通り
限定条件 　 1通り 4通り 6通り 4通り 1通り
確率 　 1/126 1/14 2/7 2/3 1
  • 「人の分かれ方」は、5人がどのように分割されたかを表します。
  • 「埋まる日数」は、その分割方法では誕生日の人がいる日数が何日になるかを表します。
  • 表の右側は、その分割方法を実際の日付に割り当てる場合、何通りの割り当て方があるかを表します。
  • 結果の数字を縦に足していき、そのうち何通りが「全部の日に人がいる」かを計算します。


上の式で n（人数）=5、m（日数）=5,4,3,2,1 でそれぞれ計算すると上記の確率が求まり、結果はすべて一致しました。ふむー。
suno様の作成したシミュレーションソフトでは、2000人になるとほぼ確率が1.0になってしまい、この計算式とまったく違う結果が出るんですよね…。何か、致命的な間違いがあるのかな？