問題
５人がそれぞれプレゼントを持ち寄り，それらを無作為に１つずつ再分配してプレゼント交換するとき，５人すべてが自分のプレゼントと異なるプレゼントを受け取る場合は何通りあるか．
一般に，\(1\)～\(n\)の数字を１列に並べるとき，数字\(i~(1\leq i \leq n)\)が左から\(i\)番目に来ないような並べ方を完全順列といいます．今回はこの完全順列の総数の求め方について触れてみたいと思います．
まず，５人にそれぞれ番号をふりましょう．１，２，３，４，５．
このとき，次のように書くことに決めます．
例えば「１が２へ渡し，２が１へ渡し，３が４へ渡し，４が５へ渡し，５が３へ渡す」なら
\[
\left(
\begin{array}{ccc}
1 & 2 & 3 & 4 & 5\\
2 & 1 & 4 & 5 & 3
\end{array}
\right)\quad \cdots (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~\rightarrow~2~\rightarrow~1~\rightarrow~\cdots\]と２つの数字がループしていることが分かります．
３に着目するとこちらは\[3~\rightarrow~4~\rightarrow~5~\rightarrow~3~\rightarrow~\cdots\]と３つの数字がループしています．
\((2)\)はどうでしょう．１に着目すると
\[1~\rightarrow~2~\rightarrow~3~\rightarrow~4~\rightarrow~5~\rightarrow~1\cdots\]と５つの文字がループしています．
このようにみると，「プレゼント交換会」にはループ構造が潜んでいることがわかります．
では，この二つの例に登場しなかった１つの文字のループ，４つの文字のループはあるでしょうか？これは明らかにダメですね．例えば\(1~\rightarrow~1~\rightarrow~\cdots\)は１が自分のプレゼントを受け取ることになり題意に反します．\(1~\rightarrow~2~\rightarrow~3~\rightarrow~4~\rightarrow~1~\cdots\)はよさそうですが残りの５が\(5~\rightarrow~5~\rightarrow~\cdots\)となり自分がプレゼントを受け取ることになりますのでこれもやはり題意に反します．
ここでひとつ言葉を定義しましょう．２つの数字のループ構造を互換，３つ以上の数字のループ構造を巡回置換，ループしないとき（自分が自分のプレゼントを受け取るとき）恒等置換と呼ぶことにします．\((1)\)の例だと互換が１個で巡回置換が１個，\((2)\)の例だと互換が０個で巡回置換が１個，\((3)\)の例だと恒等置換が５個ですね．
ここまでくるとふと思います．結局，完全順列の総数は「互換の数で場合分けして求めればよいのでは？」と．やってみましょう．
-
- 互換が０個のとき
５つの数字の巡回置換（５つの数のループ）になりますから，
\[1~\rightarrow~2~\rightarrow~3~\rightarrow~4~\rightarrow~5~\rightarrow~1\cdots\]
この場合のループの種類は，真ん中の２，３，４，５の順列の数だけ存在するので，\(4!=24\)通り． - 互換が１個のとき
どの２数を互換とするかで\({}_5\mathrm{C}_2=10\)通り．そのそれぞれに対し，３つの数字の巡回置換（３つの数のループ）を考える．例えば３，４，５のループなら，\[3~\rightarrow~4~\rightarrow~5~\rightarrow~3~\rightarrow~\cdots\]であるから(ⅰ)と同様に考えて真ん中の４，５の順列より\(2!=2\)通り．したがって\(10\times2=20\)通り - 互換が２個のとき
残りの１つの数字が恒等置換になるので，題意に適さない．
- 互換が０個のとき
以上より，\(24+20=44\)通り ・・・（答）
さて，ここで問題．今回の問題はたった５人の小規模なプレゼント交換会でしたが，これがもし「１０人」「２０人」・・・と人数が増えていったらどのように完全順列の総数を求めればいいのでしょうか（また「互換の数で場合分け」はしたくないですよね＾＾；）．また，人数を「\(n\)人」としたとき，完全順列の総数は求まるのでしょうか？
次回はこの話題について書いてみたいと思います．