【場合の数】完全順列 〜席替えで全員前と同じ席に座らない場合は何通り〜

(1,2,3)を並び替えると

$$\begin{array}{|c|c|c|} \hline ① & ② & ③ &\\\hline 1 & 2 & 3 &×\\\hline 1 & 3 & 2 &×\\\hline 2 & 1 & 3 &×\\\hline 2 & 3 & 1 &○\\\hline 3 & 1 & 2 &○\\\hline 3 & 2 & 1 &×\\\hline \end{array}$$

表の６パターンのうち、並び替えた先が同じ場所のならないのは、○の２パターン。

これが、完全順列。

$$a_2=2!\sum_{k=2}^2\frac{(-1)^k}{k!}=2\frac{(-1)^2}{2}=1$$

$$a_3=3!\sum_{k=2}^3\frac{(-1)^k}{k!}=3!(\frac{(-1)^2}{2!}+\frac{(-1)^3}{3!})=3!(\frac{1}{2}-\frac{1}{6})=2$$

$$a_4=4!\sum_{k=2}^4\frac{(-1)^k}{k!}=4!(\frac{(-1)^2}{2!}+\frac{(-1)^3}{3!}+\frac{(-1)^4}{4!})=4!(\frac{1}{2}-\frac{1}{6}+\frac{1}{24})=9$$

（１）「１」と「２」を入れ替える　場合

$$\begin{array}{|c|c|c|} \hline ① & ②&③&④&⑤&\cdots& n\\\hline 2&1&&&& \\\hline \end{array}$$

③〜nの (n-2)個の完全順列の個数を考えれば良いので　$a_{n-2}$

（２）「1」を②の場所に置き、「２」は①以外の場所におく　場合

$$\begin{array}{|c|c|c|} \hline ① & ②&③&④&⑤&\cdots& n\\\hline 2は×&1&3は×&4は×&5は×&\cdots&nは× \\\hline \end{array}$$

これは、(n-1)個の完全順列の個数を考えれば良いので　$a_{n-1}$

（１）（２）より　$a_{n-1}+a_{n-2}$

「1」を入れる位置を②以外にも③、④、・・・、n の場合も考えられるので　(n-1)通りある

よって

$$a_n=(n-1)(a_{n-1}+a_{n-2})$$

$$a_n=(n-1)(a_{n-1}+a_{n-2})$$

この漸化式を解く

両辺$n!$で割る

$$\frac{a_n}{n!}=\frac{n-1}{n!}a_{n-1}+\frac{n-1}{n!}a_{n-2}$$

$$\frac{a_n}{n!}=\frac{n-1}{n}\frac{a_{n-1}}{(n-1)!}+\frac{1}{n}\frac{a_{n-2}}{(n-2)!}$$

$b_n=\dfrac{a_n}{n!}$ とおく

$$b_n=\frac{n-1}{n}b_{n-1}+\frac{1}{n}b_{n-1}$$

両辺$b_{n-1}$を引いて

$$b_n-b_{n-1}=-\frac{1}{n}(b_{n-1}-b_{n-2})$$

$$=(-\frac{1}{n})(-\frac{1}{n-1})(b_{n-2}-b_{n-3})$$

$$=(-\frac{1}{n})(-\frac{1}{n-1})(-\frac{1}{n-2})\cdots(-\frac{1}{5})(-\frac{1}{4})(b_3-b_2)$$

$$=(-\frac{1}{n})(-\frac{1}{n-1})(-\frac{1}{n-2})\cdots(-\frac{1}{5})(-\frac{1}{4})(\frac{1}{3}-\frac{1}{2})$$

$$=(-\frac{1}{n})(-\frac{1}{n-1})(-\frac{1}{n-2})\cdots(-\frac{1}{5})(-\frac{1}{4})(-\frac{1}{3\cdot2})$$

$$=\frac{(-1)^{n-2}}{n!}$$

$$=\frac{(-1)^{n}}{n!}$$

　階差数列がわかったので、

$$b_n=b_2+\sum_{k=3}^n\frac{(-1)^k}{k!}$$

$$=\frac{1}{2}+\sum_{k=3}^n\frac{(-1)^k}{k!}$$

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

$b_n=\dfrac{a_n}{n!}$より

$$\frac{a_n}{n!}=\sum_{k=2}^n\frac{(-1)^k}{k!}$$

$$a_n=n!\sum_{k=2}^n\frac{(-1)^k}{k!}$$