離散数学・組合せ論の問題

人に $1,2,3,4,5$ と番号をつけ、人 $i$ が持ってきたプレゼントにも番号 $i$ をつけます。配り方は、人 $i$ が受け取るプレゼントの番号を $\sigma (i)$ とする $\{1,2,3,4,5\}$ の置換 $\sigma$ と 1 対 1 に対応し、全部で $5!=120$ 通りあります。求めるのは、すべての $i$ について $\sigma (i)\ne i$ となる置換、つまり攪乱順列の個数 $D_5$ です。

包除原理で数える。 $A_i$ を「$\sigma (i)=i$ となる置換の集合」とします。$k$ 個の番号 $i_1,\dots ,i_k$ を選んだとき、$A_{i_1}\cap \cdots \cap A_{i_k}$ は、その $k$ 人が自分のプレゼントを受け取り、残りの $5-k$ 人には自由に配る置換の集合なので、要素は $(5-k)!$ 個です。$k$ 個の番号の選び方は $\left(\genfrac{}{}{0ex}{}{5}{k}\right)$ 通りなので、一般の包除原理より
$$D_5=\sum _{k=0}^5(-1{)}^k(\genfrac{}{}{0ex}{}{5}{k})(5-k)!=5!\sum _{k=0}^5\frac{(-1{)}^k}{k!}$$
となります。これを計算すると
$$D_5=120\left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}-\frac{1}{120}\right)=0+60-20+5-1=44.$$

漸化式で確かめる。 $D_1=0,D_2=1$ と $D_n=(n-1)(D_{n-1}+D_{n-2})$ より
$$D_3=2(1+0)=2,D_4=3(2+1)=9,D_5=4(9+2)=44.$$
両方の方法で同じ値になりました。

よって、求める配り方は $44$ 通りです。

これは 5 個の要素の完全順列（攪乱順列）の個数 $D_5$ を求める問題である。包除原理より $D_n={\sum }_{k=0}^n(-1{)}^k\frac{n!}{k!}$ なので、
$D_5=120-120+60-20+5-1=44$。
検算：漸化式 $D_n=(n-1)(D_{n-1}+D_{n-2})$ を使う。$D_1=0,D_2=1,D_3=2,D_4=9$ なので $D_5=4(9+2)=44$。一致する。