数学A 完全順列･攪乱順列･モンモール数 問題 3 解説

方針・初手

5人それぞれについて、「その人宛ての招待状が、その人の封筒に入ってしまう」ことを禁止する問題である。

これは、5個のものを5個の場所に入れる順列のうち、どの位置にも正しいものが入らない場合、すなわち完全順列の個数を求める問題である。包除原理で、少なくとも1人は正しく入る場合を除いて数える。

解法1

5人を $1,2,3,4,5$ とし、招待状も封筒も同じ番号で表す。

まず、招待状を封筒に入れるすべての方法は、5枚の招待状を5個の封筒に並べることと同じなので、

$$ 5!=120 $$

通りである。

ここから、少なくとも1人について正しい封筒に入っている場合を除く。

$A_i$ を「人 $i$ 宛ての招待状が、人 $i$ の封筒に入っている」という事象とする。求めるのは

$$ A_1,A_2,A_3,A_4,A_5 $$

のどれも起こらない場合の数である。

包除原理より、求める個数は

$$ 5!-{}_{5}\mathrm{C}_{1}4!+{}_{5}\mathrm{C}_{2}3!-{}_{5}\mathrm{C}_{3}2!+{}_{5}\mathrm{C}_{4}1!-{}_{5}\mathrm{C}_{5}0! $$

である。

ここで、${}_{5}\mathrm{C}_{k}(5-k)!$ は、「正しく入っている人を $k$ 人指定し、残りの招待状を自由に入れる」場合の数を表している。重複して数えた分を、包除原理に従って足し引きする。

計算すると、

$$ \begin{aligned} 5!-{}_{5}\mathrm{C}_{1}4!+{}_{5}\mathrm{C}_{2}3!-{}_{5}\mathrm{C}_{3}2!+{}_{5}\mathrm{C}_{4}1!-{}_{5}\mathrm{C}_{5}0! &=120-5\cdot 24+10\cdot 6-10\cdot 2+5\cdot 1-1 \\ &=120-120+60-20+5-1 \\ &=44 \end{aligned} $$

したがって、全部間違った封筒に入れる方法は $44$ 通りである。

解法2

完全順列の漸化式を用いても求められる。

$n$ 人の完全順列の個数を $D_n$ とする。完全順列では、1番の招待状は1番以外の封筒に入る。1番の招待状が $k$ 番の封筒に入ったとする。このとき、$k$ は $2,3,\dots,n$ のいずれかなので、選び方は $n-1$ 通りある。

このあと、$k$ 番の招待状が1番の封筒に入る場合と、入らない場合に分ける。

(i)

$k$ 番の招待状が1番の封筒に入る場合

1番と $k$ 番が互いに入れ替わる形になる。残りの $n-2$ 人について完全順列を作ればよいので、$D_{n-2}$ 通りである。

(ii)

$k$ 番の招待状が1番の封筒に入らない場合

1番の封筒を、$k$ 番の招待状が入ってはいけない場所とみなすと、残りは実質的に $n-1$ 人の完全順列と同じ数え方になる。よって $D_{n-1}$ 通りである。

したがって、

$$ D_n=(n-1)(D_{n-1}+D_{n-2}) $$

が成り立つ。

初期値は、

$$ D_1=0,\qquad D_2=1 $$

である。これを順に計算すると、

$$ D_3=2(D_2+D_1)=2(1+0)=2 $$

$$ D_4=3(D_3+D_2)=3(2+1)=9 $$

$$ D_5=4(D_4+D_3)=4(9+2)=44 $$

よって、求める方法は $44$ 通りである。

解説

この問題は「全員が間違う」ことを直接並べようとすると、条件が絡み合って数えにくい。

そのため、まず全体の $5!$ 通りを数え、そこから「少なくとも1人が正しい封筒に入る場合」を包除原理で取り除くのが標準的である。特に、複数人が同時に正しい封筒に入る場合があるため、単純に $5\cdot4!$ を引くだけでは重複を処理できない点に注意する。

完全順列の公式を知っていれば、

$$ !5=5!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}\right) $$

として計算してもよい。

答え

$$ 44 $$

通りである。