攪乱順列（完全順列）の個数を求める公式

1の移動先を「$i$ 番目」 として，攪乱順列を以下の2通りに場合分けする。

• パターン1：$i$ の移動先が1番目となる場合の数（交換型）

$i$ の選び方が $n-1$ 通りで，それぞれに対して1と $i$ 以外の $n-2$ 個の攪乱順列の数だけあるので，全部で $(n-1)a_{n-2}$ 通り。

• パターン2：$i$ の移動先が1番目以外となる場合の数（非交換型）

$i$ の選び方が $n-1$ 通りで，それぞれに対して1以外の $n-1$ 個の攪乱順列の数だけあるので，全部で $(n-1)a_{n-1}$ 通り。

よって，$a_n=(n-1)(a_{n-1}+a_{n-2})$

あとは，$a_2=1, a_3=2$ のもとでこの三項間漸化式を解けばよいだけです。解き方の詳細→階乗を用いる漸化式の解法の例題3より，

$a_n=n!\displaystyle\sum_{k=2}^n\dfrac{(-1)^{k}}{k!}$ が分かります。

$i$ が移動しない順列の集合を $A_i$ とおくと，

$a_n=n!-|A_1\cup A_2\cup\cdots\cup A_n|$

$i$ が移動しない順列の数は，$|A_i|=(n-1)!$

$i$ も $j$ も移動されない順列の数は，$|A_i\cap A_j|=(n-2)!$

以下同様にして，特定の $k$ 個の要素が移動されない順列の数は，$(n-k)!$ となる。すなわち「かつ」の確率は計算できるので，包除原理より，

$a_n=n!-|A_1\cup A_2\cup\cdots\cup A_n|\\ =n!-\displaystyle\sum_{k=1}^n(-1)^{k-1}{}_n\mathrm{C}_k(n-k)!\\ =n!-n!\displaystyle\sum_{k=1}^n\dfrac{(-1)^{k-1}}{k!}\\ =n!\displaystyle\sum_{k=2}^n\dfrac{(-1)^k}{k!}$