クリスマスのプレゼント交換で確率計算してみよう（解答・解説編）

　クリスマスのプレゼント交換で、みんなが持ち寄ったプレゼントを一人に１個ずつ無作為に配る。このとき「おいおい、自分が持ってきたものが自分のところに来ちゃったよ」という人が現れる確率はどれくらいでしょうか？
　実は（ア）人以上のグループであれば、クリスマス・パーティーに参加した人の誰かがそういう目に合う確率は約（イ）％になります。

　では、ここで【問題】です。（ア）に入る最も小さい自然数とそのときの自然数（イ）を答えてください。「約（イ）％」というのは、百分率で表した数の小数点以下を四捨五入して自然数で表した値が（イ）になるということです。

　ちなみに、その状況は「席替えしたのに結局前と同じ席になっちゃったよ」というのと同じです。人数が１人の場合、２人の場合、３人の場合・・・と実際に計算してみてください。たぶん見えてきます。そしてその値が意外に大きいこと、人数が変わってもその値がほとんど変わらないことにちょっと驚くことでしょう。

　では、計算してみましょう。
「1 から n までの数を１列に並べたとき、数字 k が k 番目に並ぶ、そういう k が存在する」確率を p_n とします。
「10 人でプレゼント交換をしたとき、そのうちの誰かが自分の用意したものに当たる」確率は p₁₀ であり、
「42 人のクラスで席替えをしたのに、誰かが同じ席になっちゃう」確率は p₄₂ です。

◇　n＝1 のとき、
　　すべての場合の数は (1) の 1 通りだけで、これは条件を満たしている。よって、p₁ ＝ 1/1 ＝ 100 ％ 。

◇　n＝2 のとき、
　　すべての場合の数は (1 , 2) , (2 , 1) の 2 通りで、このうち条件を満たすのは (1 , 2) の 1 通り。
　　よって、p₂ ＝ 1/2 ＝ 50 ％ 。

◇　n＝3 のとき、
　　すべての場合の数は (1 , 2 , 3) , (1 , 3 , 2) , (2 , 1 , 3) , (2 , 3 , 1) , (3 , 1 , 2) , (3 , 2 , 1) の 6 通り …(a) で、このうち条件を満たすのは 4 通り。よって、p₃ ＝ 4/6 ＝ 66.7 ％ 。

◇　n＝4 のとき、
　　すべての場合の数は 4 ! ＝ 24 通り。
　　このうち条件を満たすのは、最初の数が 1 のときは 6 通り全部 ○ 。
　　最初の数が 2 のとき、その後は (1 , 3 , 4) , (1 , 4 , 3) , (3 , 1 , 4) , (3 , 4 , 1) , (4 , 1 , 3) , (4 , 3 , 1) のうちの 3 通りが ○ …(b) 。最初の数が 3 のとき、最初の数が 4 のときも同じく 3 通りずつが ○ 。
　　以上から、条件を満たすのは 15 通り。よって、p₄ ＝ 15/24 ＝ 62. 5％ 。

◇　n＝5 のとき、
　　すべての場合の数は 5 ! ＝ 120 通り。
　　このうち条件を満たすのは、最初の数が 1 のときは 4 ! ＝ 24 通り全部 ○ 。
　　最初の２つが (2 , 1) のときは (a) と同じで 4 通りが ○。
　　最初の２つが (2 , 3) のときは (b) と同じで 3 通りが ○。 最初の２つが (2 , 4) のとき、(2 , 5) のときも同じ。
　　つまり、最初の数が 2 のときは 4＋3×3 ＝ 13 通りが ○ で、最初の数が 3 , 4 , 5 のときも同じ。
　　以上から、条件を満たすのは 24＋13×4 ＝ 76 通り。 よって、p₅ ＝ 76/120 ＝ 63. 3％ 。

　と、このように順番に数えていってはキリがないのですが、何はともあれここまでのところをグラフ化してみましょう。上のグラフです。そしてここまで（n ≦ 5）の結果から、この先（n ≧ 6）どうなるかを予想してみると、 p_n は減衰振動しそうですね。
　n ≦ 5 では確かに減衰振動していて、n ＝ 4 , n ＝ 5 のときは「四捨五入して 63 ％」になっています。この流れがこの先続けば「n ≧ 4 のすべての n で、四捨五入して 63 ％」となりそうですね。

　とはいえ、これでもって証明完了というにはちょっと力不足でしょう。そこで漸化式を立ててみましょう。

　　○　「1 から n までの数を１列に並べたとき、どの数字 k も k 番目に並ばない場合の数」を a_n とします。
　　○　このとき「1 から n までの数を１列に並べたとき、どの数字 k も k 番目に並ばない確率」は q_n＝a_n ／n！ で、
　　○　「1 から n までの数を１列に並べたとき、数字 k が k 番目に並ぶ、そういう k が存在する確率」は p_n＝1－q_n です。

このとき、

　　○　a_n について漸化式　a_n+2＝(n＋1) (a_n+1＋a_n)　が成り立ち、・・・ (1)
　　○　q_n で書き換えると、漸化式　(n＋2)q_n+2＝(n＋1)q_n+1＋q_n　となり、・・・ (2)
　　○　p_n で書き換えると、漸化式　(n＋2)p_n+2＝(n＋1)p_n+1＋p_n　となって、・・・ (3)
　　これを解くと
　　○　p_n の一般項は　p_n＝1／1！－1／2！＋1／3！－1／4！＋ ・・・ ＋(-1)^{n +1}／n！　となります。・・・ (4)

※　(1) の計算法や考え方は「完全順列」（またはモンモール数）というワードでネットで検索してください。
　　 (3) から (4) を導くのは難しいが、結果を示されれば数学的帰納法で証明できます。

(4) より「n が大きくなると、減衰振動します」。　（← ここがまだちょっと曖昧でしょうか？）
このことと、p4＝0.625 , p5＝0.633... から、「４人以上の人がクリスマスのプレゼント交換したとき、自分が持ってきたものが自分のところに来ちゃったよという人が現れる確率」は、約（小数点以下を四捨五入すると）63 ％　であることが証明できます。//