今回は、「完全順列」について解説します。
この記事を読むと
・完全順列とは
・完全順列の一般項とその求め方
・完全順列の確率
について理解することができます。
この記事は、「わか」が執筆しています。
私「わか」（https://twitter.com/wakkachan2019）は、国立大学数学科を卒業後、数学教育に10年以上関わっています。
完全順列とは
完全順列
まずは定義を確認します。
完全順列・・・自然数\(1,2,3,4,…,n\)を並び替えたとき、k番目がkでない順列
例えば、１、２、３の数字を並び替えた時を考えます。
(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}
表の６パターンのうち、並び替えた先が同じ場所のならないのは、○の２パターン。
これが、完全順列。
・上記の例のように、並び替えたときに、全て同じ場所にならない順列を完全順列や錯乱順列と呼ぶ
・完全順列の総数をモンモール数という。（例のモンモール数は２）
完全順列の例
n個の自然数の「完全順列」の例を見てみましょう。
１個の数字を並び替えると、当然同じ場所になるので、完全順列はない。
(1,2)を並び替える
\begin{array}{|c|c|c|} \hline ① & ② \\\hline 2 & 1\\\hline \end{array}
の１通り
(1,2,3)を並び替える
\begin{array}{|c|c|c|} \hline ① & ② & ③\\\hline 2 & 3 & 1\\\hline 3 & 1 & 2\\\hline \end{array}
の２通り
(1,2,3,4)を並び替える
\begin{array}{|c|c|c|} \hline ① & ② & ③ &④\\\hline 2 & 1 & 4 &3\\\hline 2 & 3 & 4 &1\\\hline 2 & 4 & 1 &3\\\hline 3 & 1 & 4 &2\\\hline 3 & 4 & 1 &2\\\hline 3 & 4 & 2 &1\\\hline4 & 1 & 2 &3\\\hline4 & 3 & 2 &1\\\hline4 & 3 & 1 &2\\\hline \end{array}
の９通り
4個くらいまでならすぐに数え上げることができます。
完全順列の総数（モンモール数）一般項
完全順列の総数（モンモール数）の一般項
n=1,2,3,4のときは、数え上げればすぐに完全順列の総数を求めることができます。しかし、数が大きくなった時のために、一般項を考えたいと思います。
一般項は、以下の通りです。
n個の完全順列の総数\(a_{n}\)は
$$a_n=n!\sum_{k=2}^n\frac{(-1)^k}{k!}$$
n=2,3,4を代入して本当に成り立つか確認しましょう。
$$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_2=\frac{1}{2} , b_3=\frac{1}{3}$$
$$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_{n-1}=\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!}$$
完全順列の確率
完全順列の確率
完全順列になる確率を考えましょう。
まずn=2,3,4のときを考えます。
$$\frac{1}{2!}=\frac{1}{2}$$
$$\frac{2}{3!}=\frac{1}{3}$$
$$\frac{9}{4!}=\frac{3}{8}$$
続いて、nの場合の完全順列を考えます。
$$\frac{a_{n}}{n!}=\frac{n!\sum_{k=2}^n\frac{(-1)^{k}}{k!}}{n!}$$
$$=\sum_{k=2}^n\frac{(-1)^{k}}{k!}$$
nを無限大に近づけるときを考えます。
$$\sum_{k=2}^n\frac{(-1)^{k}}{k!}=\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}\cdots\frac{(-1)^n}{n!}$$
マクローリン展開より
$$e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!}+\cdots$$
\(x=-1\)を代入すると
$$e^{-1}=\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}\cdots$$
以上のことから、
$$\lim_{n\to \infty}\sum_{k=2}^n\frac{(-1)^{k}}{k!}=\frac{1}{e}$$
完全順列の例
身近な例として、完全順列は「プレゼント交換」や「席替え」があります。
席替えで全員が前と同じ席にならない
席替えをしたとき、クラスで1人ぐらいは「また同じ席になったよー」と言っている人いる気がしませんか。席替えで、全員が前と同じ席にならないというのは、まさに「完全順列」を考えています。
プレゼント交換で全員が自分のプレゼントを受け取らない
プレゼント交換で、全員が自分のプレゼントを受け取らない場合を考えるのも「完全順列」を考えていることになります。
「席替え」や「プレゼント交換」が成功する確率
n（人数）を増やしていけば、完全順列になる確率は
\(\dfrac{1}{e}\)に近づいていく
$$\frac{1}{e}=0.367879\cdots$$
なので、３７パーセント位の確率で「全員が自分のプレゼントを受け取らない」
逆に、６３パーセント位の確率で「少なくとも1人は自分のプレゼントを受け取ってしまう」
ということになります。
まとめ：完全順列
完全順列のまとめは以下の通り
・「完全順列」は、自然数\(1,2,3,4,…,n\)を並び替えたとき、k番目がkでない順列
・「完全順列」の総数を「モンモール数」といい、\(a_n\)で表す。
・モンモール数の一般項 \(a_n=n!\sum_{k=2}^n\frac{(-1)^k}{k!}\)
・完全順列の確率は \(\sum_{k=2}^n\frac{(-1)^k}{k!}\)
・完全順列の確率は \(\lim_{n\to\infty}\sum_{k=2}^n\frac{(-1)^k}{k!}=\frac{1}{e}\)
以上「完全順列」の解説でした。
少しでも参考になれば幸いです。それではまた！
コメント