６人でプレゼント交換する時、全員が自分以外のプレゼントを貰うパターンはいくつ？【数学】【上級】（完全順列）

今日のテーマは「完全順列」です！

問題

6人がそれぞれ１つずつプレゼントを持参。誰がどのプレゼントを受け取るかをランダムに決める。全員が自分で持ってきたプレゼントが当たらずに済む場合の数は何通りあるか？

【数学】6人がプレゼント交換をして全員が自分のものに当たらない確率（完全順列）

「6人がそれぞれ1つずつプレゼントを持ち寄り、ランダムに交換したとき、全員が自分の持ってきたプレゼントに当たらない場合の数は何通りあるか？」

今回は、この有名かつ少し厄介な問題（完全順列・攪乱順列）を、公式の丸暗記ではなく「実験」と「論理」で解く方法を解説します。

数え上げが大変そうなときは、小さい数で実験して法則を見つけるのが鉄則です！

人数を $ n $ 人、求める場合の数を $ a_n $ とします。
いきなり $ n=6 $ を考えるのは大変なので、$ n=1 $ から順に書き出して様子を見てみましょう。

$ n=1 $ のとき（1人）
自分のプレゼントしかないので、交換できません。 $$ a_1 = 0 $$
$ n=2 $ のとき（A, B）
Aがb、Bがaを取るパターンの1通りだけです。 $$ a_2 = 1 $$
$ n=3 $ のとき（A, B, C）
Aがbを取った場合、残りはBとC。Bはc、Cはaを取るしかありません（Bがaを取るとCがcになってしまうため）。
同様にAがcを取る場合もあるので、全部で2通りです。 $$ a_3 = 2 $$
$ n=4 $ のとき（A, B, C, D）
少し書き出すのが大変になりますが、全部書き出すと9通りになります。 $$ a_4 = 9 $$

ここまでの結果を表にすると以下のようになります。

人数 $ n $	1	2	3	4	5	6
場合の数 $ a_n $	0	1	2	9	?	?

さて、ここから $ n=5, 6 $ をどう求めるかが本題です。
単なる数列の規則性ではなく、構造から漸化式を作ってみましょう。

$ n $ 人（A, B, C, …）でプレゼント交換をする場合を考えます。
まず、Aさんが誰のプレゼントを取るかで場合分けをします。

Aさんは自分以外の $ n-1 $ 人のうち、誰か（例えばBさん）のプレゼントを取ります。
（Aが選べる相手は $ n-1 $ 通り）

AがBのプレゼントを取ったとき、残されたBさんの行動でさらに2つのパターンに分かれます。

AとBでお互いのプレゼントを交換してしまった状態です。
AとBはこれで満足して抜けるので、残りの人数は $ n-2 $ 人。
この $ n-2 $ 人が誰も自分のプレゼントを取らない場合の数は $ a_{n-2} $ 通りです。

ここがポイントです。

この状況は、「Aのプレゼント」を「B本来のプレゼント」と見なしてしまえば、Bを含む残り $ n-1 $ 人が完全順列を行う状況と全く同じになります。
つまり、この場合の数は $ a_{n-1} $ 通りです。

以上のことから、漸化式は次のように立てられます。

$$ \begin{aligned} a_n &= (\text{Aの選び方}) \times \{ (\text{①交換成立}) + (\text{②交換不成立}) \} \\ a_n &= (n-1) \times ( a_{n-2} + a_{n-1} ) \end{aligned} $$

この法則を使って、一気に $ n=6 $ まで計算しましょう。

$ n=5 $ のとき $$ \begin{aligned} a_5 &= (5-1)(a_3 + a_4) \\ &= 4 \times (2 + 9) \\ &= 4 \times 11 \\ &= 44 \end{aligned} $$
$ n=6 $ のとき $$ \begin{aligned} a_6 &= (6-1)(a_4 + a_5) \\ &= 5 \times (9 + 44) \\ &= 5 \times 53 \\ &= 265 \end{aligned} $$