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

手紙の入れ方は、$\{1,2,\dots ,6\}$ の置換 $\sigma$（手紙 $i$ を封筒 $\sigma (i)$ に入れる）と $1$ 対 $1$ に対応するので、全部で $6!=720$ 通りある。求める個数は、すべての $i$ で $\sigma (i)\ne i$ となる置換（攪乱順列）の個数 $D_6$ である。

包除原理を使う。 $i=1,2,\dots ,6$ に対し、$A_i$ を「手紙 $i$ が封筒 $i$ に入る」入れ方の集合とする。求めるのは $\left|\overline{A_1}\cap \cdots \cap \overline{A_6}\right|$ である。

$k$ 個の番号 $i_1,\dots ,i_k$ を指定すると、$A_{i_1}\cap \cdots \cap A_{i_k}$ はその $k$ 通の手紙を同じ番号の封筒に固定し、残り $6-k$ 通を残りの $6-k$ 枚の封筒に自由に入れる入れ方なので、その個数は $(6-k)!$ である。番号の選び方は $\left(\genfrac{}{}{0ex}{}{6}{k}\right)$ 通りあるから、一般の包除原理より
$$D_6=\sum _{k=0}^6(-1{)}^k(\genfrac{}{}{0ex}{}{6}{k})(6-k)!=\sum _{k=0}^6(-1{)}^k\frac{6!}{k!}.$$
各項を計算すると
$$D_6=720-6\cdot 120+15\cdot 24-20\cdot 6+15\cdot 2-6\cdot 1+1$$
$$=720-720+360-120+30-6+1=265.$$

漸化式による確認。 $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$、$D_6=5(44+9)=265$ となり、一致する。

よって答えは $265$ 通りである。

これは $6$ 個の撹乱順列（完全順列）の個数 $D_6$ を求める問題である。包除原理より $D_n=n!{\sum }_{k=0}^n\frac{(-1{)}^k}{k!}$。

$D_6=720\left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}-\frac{1}{120}+\frac{1}{720}\right)=720-720+360-120+30-6+1=265$。

検算：漸化式 $D_n=(n-1)(D_{n-1}+D_{n-2})$ を使う。$D_1=0,D_2=1,D_3=2(1+0)=2,D_4=3(2+1)=9,D_5=4(9+2)=44,D_6=5(44+9)=265$。一致する。