撹乱順列

解答1：包含と排除の原理

$U$ ：プレゼントの分け方のすべて

$A$ ：A君が自分自身のプレゼントをもらう

$B$ ：B君が自分自身のプレゼントをもらう

$C$ ：C君が自分自身のプレゼントをもらう

$D$ ：D君が自分自身のプレゼントをもらう

と集合をおくと

\begin{align} &\ n(U)-n(A\cup B\cup C\cup D)\\ =&\ n(U)-\bigl\{n(A)+n(B)+n(C)+n(D)\\ &\ -n(A\cap B)-n(A\cap C)-n(A\cap D)\\ &\ -n(B\cap C)-n(B\cap D)-n(C\cap D)\\ &\ +n(A\cap B\cap C)+n(A\cap B\cap D)\\ &\ +n(A\cap C\cap D)+n(B\cap C\cap D)\\ &\ -n(A\cap B\cap C\cap D)\bigr\}\\ =&\ 4!-\bigl\{\ _{4}\mathrm{C}_{1}(4-1)!-\ _{4}\mathrm{C}_{2}(4-2)!\\ &\ +\ _{4}\mathrm{C}_{3}(4-3)!-\ _{4}\mathrm{C}_{4}(4-4)!\bigr\}\\ =&\ 4!\left(\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\dfrac{1}{4!}\right)\\ =&\ 4!-4\cdot3!+6\cdot2!-4\cdot1!+1\\ =&\ \boldsymbol{9} \end{align}

通り

解答2：漸化式を使う

$n$ 人のプレゼント交換において， 自分自身の持ってきたプレゼントに誰も当らない場合の数を $D(n)$ とする．

いま， $D(4)$ は次の3つに場合分けできる．

1. A君がB君のプレゼントに当る
2. A君がC君のプレゼントに当る
3. A君がD君のプレゼントに当る

i. ～iii. は対称的なので，以下i. についてだけ考える（のち4 − 1 = 3倍すればよい）．

プレゼントを小文字のアルファベットで表すとして，“A君のプレゼントaをbと考えて”，残りの3人へのプレゼントの配り方を考えると

1. B君にb（本当はa）を配り，残りC，D君に自分自身のプレゼントが当らないように配る
2. B，C，D君に自分自身のプレゼントが当らないように配る（見かけの上ではあるが，B君にbが配られない場合を考える）

の2通りに場合分けできる．ここで1. は $D(2)$ ，2. は $D(3)$ に他ならない．つまり $D(4)$ は

\[D(4)=(4-1)\left\{D(3)+D(2)\right\}\]

で計算できる．この関係は $n$ が自然数で一般的に成り立つから

\begin{align} D(4)=&\ (4-1)\left\{D(3)+D(2)\right\}\\ =&\ 3D(3)+3D(2)\\ =&\ 3\left[2\left\{D(2)+D(1)\right\}\right]+3D(2)\\ =&\ 9D(2)+6D(1)\\ =&\ 9D(2)+0\\ =&\ 9\cdot1\\ =&\ \boldsymbol{9} \end{align}

通り