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

手紙と封筒にそれぞれ $1,2,\dots ,6$ の番号を付け、手紙 $i$ を封筒 $\sigma (i)$ に入れるとみなす。すると入れ方は $\{1,\dots ,6\}$ の置換 $\sigma$ と $1$ 対 $1$ に対応し、求めるものは $\sigma (i)\ne i$ がすべての $i$ で成り立つ置換、すなわち攪乱順列の個数 $D_6$ である。

包除原理による計算

$A_i$ を「手紙 $i$ が正しい封筒に入る」入れ方の集合とする。$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)!=6!\sum _{k=0}^6\frac{(-1{)}^k}{k!}.$$
各項を計算すると
$$D_6=720-720+\frac{720}{2}-\frac{720}{6}+\frac{720}{24}-\frac{720}{120}+\frac{720}{720}=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.$$
両者は一致する。

よって求める入れ方は $265$ 通りである。

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

$n=6$ のとき、
$D_6=720-720+360-120+30-6+1$
$=720-720=0$、$0+360=360$、$360-120=240$、$240+30=270$、$270-6=264$、$264+1=265$。

検算として漸化式 $D_n=(n-1)(D_{n-1}+D_{n-2})$ を使う。$D_1=0,D_2=1,D_3=2,D_4=9,D_5=44$ より、$D_6=5\times (44+9)=265$。一致する。

よって答えは $265$ 通り。