1から$n$までの番号が書かれた$n$枚の封筒に、1から$n$までの番号札を1枚ずつ入れる。どの封筒にも、封筒の番号と異なる番号札が入るような入れ方を完全順列と呼ぶ。 $n=5$のとき、完全順列の総数を求めよ。

1. 問題の内容

1から$n$までの番号が書かれた$n$枚の封筒に、1から$n$までの番号札を1枚ずつ入れる。どの封筒にも、封筒の番号と異なる番号札が入るような入れ方を完全順列と呼ぶ。

$n=5$のとき、完全順列の総数を求めよ。

2. 解き方の手順

完全順列の総数を求める公式は、以下の通り。

$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$

$n=5$を代入すると、

$D_5 = 5! \sum_{k=0}^{5} \frac{(-1)^k}{k!} = 5! (\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!})$

$= 120(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120})$

$= 120(\frac{60 - 20 + 5 - 1}{120})$

$= 60 - 20 + 5 - 1 = 44$

または漸化式を使う。

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

$D_1 = 0$

$D_2 = 1$

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

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

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

3. 最終的な答え

44通り