完全順列(その3・一般化)

前回前々回は「5人のプレゼント交換会」を行いました.

「\(n\)人のプレゼント交換会」ならどうでしょうか?この場合の完全順列の総数を求めてみましょう.

以下,\(i\)は自然数とします.

完全順列とは,「\(i\)番目に\(i\)が来ないような並び方\((1\leq i \leq n)\)」,すなわち\[\text{\(1\)以上\(n\)以下のすべての\(i\)に対して,\(i\)番目に\(i\)が来ない}\quad\cdots(\ast)\]という意味でした.この総数を求めたい,というわけですね.

今まで見てきた通り,これが一筋縄ではいかない問題でした.まして今回は\(n\)人です.そこで,お馴染みのアイデア:直接求めるのが難しいのなら,全体からその否定を除けばいい,という「余事象」の考え方で攻めてみることにしましょう.というわけで,\((\ast)\)の否定を考えてみます.

「すべての」の否定は「存在する」でしたから(なぜ?),\((\ast)\)の否定は次のようになります.\[\text{\(i\)番目が\(i\)になる\(1\)以上\(n\)以下の\(i\)が存在する}\quad\cdots(\ast\ast)\]

この総数を数え,そして並べ替えの総数\(n!\)から引いてやりましょう.ここで,\(i\)番目が\(i\)となるような事象を\(A_i~(1\leq i \leq n)\)とおくことにします.すると\((\ast\ast)\)となる総数は
\[n(A_1\cup A_2\cup A_3 \cup \cdots \cup A_n)=n \left( \bigcup^n_{i=1}A_i \right)\]と表せることになります.したがって,求める完全順列の総数は
\[n!-n\left(\bigcup^n_{i=1}A_i\right)\]
となります.さて,この式の二項目\(n(\bigcup^n_{i=1}A_i)\)ですが,これは以下のように計算できます(なぜ?).

\[
n\left(\displaystyle\bigcup_{i}^{n} A_i\right)=\displaystyle\sum_{i}^{n} n(A_i)-\displaystyle\sum_{i<j}^{n}n(A_i \cap A_j)+\displaystyle\sum_{i<j<k}^{n}n(A_i \cap A_j \cap A_k)-\cdots+(-1)^{n-1}\displaystyle\sum^{n}_{i<j<\cdots} n(A_i \cap A_j \cap \cdots )
\]

ここで,\[\displaystyle\sum_{i}^{n} n(A_i),~\sum_{i<j}^{n}n(A_i \cap A_j),~\sum_{i<j<k}^{n}n(A_i \cap A_j \cap A_k),\cdots,\sum^{n}_{i<j<\cdots} n(A_i \cap A_j \cap \cdots)\]を求めてみると,
\[
\begin{align*}
&\displaystyle\sum_{i}^{n} n(A_i)={ }_n\mathrm{C}_1\times (n-1)!\\
&\sum_{i<j}^{n}n(A_i \cap A_j)={ }_n\mathrm{C}_2\times(n-2)!\\
&\sum_{i<j<k}^{n}n(A_i \cap A_j \cap A_k)={ }_n\mathrm{C}_3\times(n-3)!\\
&\qquad\qquad\vdots\\
&\sum^{n}_{i<j<\cdots} n(A_i \cap A_j \cap \cdots)={ }_n\mathrm{C}_n\times(n-n)!
\end{align*}
\]
ですから結局,
\[n\left(\displaystyle\bigcup_{i}^{n} A_i\right)={ }_n\mathrm{C}_1\times (n-1)!-{ }_n\mathrm{C}_2\times(n-2)!+{ }_n\mathrm{C}_3\times(n-3)!-\cdots+(-1)^{n-1}{ }_n\mathrm{C}_n\times(n-n)!\]
よって,求める完全順列の総数は,
\[
\begin{align*}
n!-n\left(\bigcup^n_{i=1}A_i\right)=~&n!-\left({ }_n\mathrm{C}_1\times (n-1)!-{ }_n\mathrm{C}_2\times(n-2)!+{ }_n\mathrm{C}_3\times(n-3)!-\cdots+(-1)^{n-1}{ }_n\mathrm{C}_n\times(n-n)!\right)\\
=~&n!-\left(\frac{n!}{1!}-\frac{n!}{2!}+\frac{n!}{3!}-\cdots+(-1)^{n-1}\frac{n!}{n!} \right)\\
=~&n!-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+\cdots+(-1)^{n}\frac{n!}{n!} \\
=~&n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^{n}\frac{1}{n!}\right)\\
=~&n!\sum^{n}_{k=0}\frac{(-1)^k}{k!}\\
\end{align*}
\]
となります.

実験してみましょう.\(n=5\)と代入してみます.
\[
\begin{align*}
5!\sum^{5}_{k=0}\frac{(-1)^k}{k!}&=5!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}\right)\\
&=5\cdot 4\cdot 3-5\cdot 4 +5-1\\
&=60-20+5-1\\
&=44
\end{align*}
\]

おっけい!

完全順列(その2)

前回のプレゼント交換会を次ので考えます.例えば前回の例
\[
\left(
\begin{array}{ccc}
1 & 2 & 3 & 4 & 5\\
2 & 1 & 4 & 5 & 3
\end{array}
\right)
\]であれば

と表し,
\[
\left(
\begin{array}{ccc}
1 & 2 & 3 & 4 & 5\\
2 & 3 & 4 & 5 & 1
\end{array}
\right)
\]であれば

といった具合です.

以下,\(n\)個の完全順列の総数を\(f(n)\)で表すことにします(なので求めたいものは\(f(5)\)).また,\(i\)行\(j\)列にある欄を\((i,~j)\)と表すことにします.

ここで,まず1行目に着目します.1行目で〇が入り得るのは,2,3,4,5のいずれかです.

ここでは\((1,~2)\)に〇が入る場合を考えてみます.

こんな場合です.

次に,2行目に着目します.ここでは,

(ⅰ)\((2,~1)\)に〇が入る場合

と,

(ⅱ)\((2,~1)\)に入らない場合(\((2,~3)\)か\((2,~4)\)か\((2,~5)\)に入る場合)

が考えられますので,場合分けしてみます.表で表すと,

という具合です.

まず(ⅰ)の場合について考察してみます.
この場合,下図の黄色と緑のライン上に〇が来ることはありません(〇が同じ行または列でダブるとそれはプレゼントを2つ受け取るor与えることを意味してしまうから).なので,どうせ〇が来ないのならいっそのこと消しゴムで消して繋げてしまいましょう.

そうして出来上がった表を眺めると,この完全順列の総数は\(f(3)\)となることがわかります.これで(ⅰ)のときすなわち\((2,~1)\)に〇が入る場合その完全順列の総数は\(f(3)\)であることが分かりました.

次に(ⅱ)の場合について考えてみます.(ⅰ)のときと同様に考え,

出来上がった表を眺めると,この完全順列の総数は\(f(4)\)となることがわかります.これで(ⅱ)のとき\((2,~1)\)に〇が入らない場合その完全順列の総数は\(f(4)\)であることが分かりました.

ここまででしたことをまとめます.

最初の場合分けで4通り,この4通りそれぞれにおいて,(ⅰ)タイプと(ⅱ)タイプに分類したので,結局,求める\(f(5)\)は,
\[f(5)=4(f(3)+f(4))\]
となります.

以上の議論を\(5\)人のプレゼント交換会ではなく,\(n\)人で置き換えると,
\[f(n+2)=(n+1)(f(n)+f(n+1))\]という漸化式が得られます.これを利用すれば,

\[
\begin{align*}
&f(3)=2(f(1)+f(2))\\
&f(4)=3(f(2)+f(3))\\
&f(5)=4(f(3)+f(4))\\
\end{align*}
\]

\(f(1)=0,~f(2)=1\)ですから,順次計算することで
\(f(3)=2,~f(4)=9,~f(5)=44\)となり答えを得ます.

このように考えると,プレゼント交換会の人数がそれなりに多くても,漸化式\(f(n+2)=(n+1)(f(n)+f(n+1))\)を考えることで単純な計算により完全順列の総数を算出できることが分かります.

次は,完全順列の総数の一般化を考えてみます.

完全順列

問題
5人がそれぞれプレゼントを持ち寄り,それらを無作為に1つずつ再分配してプレゼント交換するとき,5人すべてが自分のプレゼントと異なるプレゼントを受け取る場合は何通りあるか.

一般に,\(1\)~\(n\)の数字を1列に並べるとき,数字\(i~(1\leq i \leq n)\)が左から\(i\)番目に来ないような並べ方を完全順列といいます.今回はこの完全順列の総数の求め方について触れてみたいと思います.

まず,5人にそれぞれ番号をふりましょう.1,2,3,4,5.

このとき,次のように書くことに決めます.

例えば「1が2へ渡し,2が1へ渡し,3が4へ渡し,4が5へ渡し,5が3へ渡す」なら

\[
\left(
\begin{array}{ccc}
1 & 2 & 3 & 4 & 5\\
2 & 1 & 4 & 5 & 3
\end{array}
\right)\quad \cdots (1)
\]

例えば「1が2へ渡し,2が3へ渡し,3が4へ渡し,4が5へ渡し,5が1へ渡す」なら

\[
\left(
\begin{array}{ccc}
1 & 2 & 3 & 4 & 5\\
2 & 3 & 4 & 5 & 1
\end{array}
\right)\quad \cdots (2)
\]

例えば「全員,自分のプレゼントを自分に渡す」なら

\[
\left(
\begin{array}{ccc}
1 & 2 & 3 & 4 & 5\\
1 & 2 & 3 & 4 & 5
\end{array}
\right)
\]

といった具合です(この場合は題意に沿いませんね).このようにして考えると,この「プレゼント交換会」にはある特徴が見えてきます.

まず\((1)\).1に着目すると\[1~\rightarrow~2~\rightarrow~1~\rightarrow~\cdots\]と2つの数字がループしていることが分かります.
3に着目するとこちらは\[3~\rightarrow~4~\rightarrow~5~\rightarrow~3~\rightarrow~\cdots\]と3つの数字がループしています.

\((2)\)はどうでしょう.1に着目すると
\[1~\rightarrow~2~\rightarrow~3~\rightarrow~4~\rightarrow~5~\rightarrow~1\cdots\]と5つの文字がループしています.

このようにみると,「プレゼント交換会」にはループ構造が潜んでいることがわかります.

では,この二つの例に登場しなかった1つの文字のループ,4つの文字のループはあるでしょうか?これは明らかにダメですね.例えば\(1~\rightarrow~1~\rightarrow~\cdots\)は1が自分のプレゼントを受け取ることになり題意に反します.\(1~\rightarrow~2~\rightarrow~3~\rightarrow~4~\rightarrow~1~\cdots\)はよさそうですが残りの5が\(5~\rightarrow~5~\rightarrow~\cdots\)となり自分がプレゼントを受け取ることになりますのでこれもやはり題意に反します.

ここでひとつ言葉を定義しましょう.2つの数字のループ構造互換3つ以上の数字のループ構造巡回置換,ループしないとき(自分が自分のプレゼントを受け取るとき)恒等置換と呼ぶことにします.\((1)\)の例だと互換が1個で巡回置換が1個,\((2)\)の例だと互換が0個で巡回置換が1個,\((3)\)の例だと恒等置換が5個ですね.

ここまでくるとふと思います.結局,完全順列の総数は「互換の数で場合分けして求めればよいのでは?」と.やってみましょう.

    1. 互換が0個のとき
      5つの数字の巡回置換(5つの数のループ)になりますから,
      \[1~\rightarrow~2~\rightarrow~3~\rightarrow~4~\rightarrow~5~\rightarrow~1\cdots\]
      この場合のループの種類は,真ん中の2,3,4,5の順列の数だけ存在するので,\(4!=24\)通り.
    2. 互換が1個のとき
      どの2数を互換とするかで\({}_5\mathrm{C}_2=10\)通り.そのそれぞれに対し,3つの数字の巡回置換(3つの数のループ)を考える.例えば3,4,5のループなら,\[3~\rightarrow~4~\rightarrow~5~\rightarrow~3~\rightarrow~\cdots\]であるから(ⅰ)と同様に考えて真ん中の4,5の順列より\(2!=2\)通り.したがって\(10\times2=20\)通り
    3. 互換が2個のとき
      残りの1つの数字が恒等置換になるので,題意に適さない.

以上より,\(24+20=44\)通り ・・・(答)

さて,ここで問題.今回の問題はたった5人の小規模なプレゼント交換会でしたが,これがもし「10人」「20人」・・・と人数が増えていったらどのように完全順列の総数を求めればいいのでしょうか(また「互換の数で場合分け」はしたくないですよね^^;).また,人数を「\(n\)人」としたとき,完全順列の総数は求まるのでしょうか?

次回はこの話題について書いてみたいと思います.