完全順列

問題
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\)人」としたとき,完全順列の総数は求まるのでしょうか?

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

© 2022 佐々木数学塾, All rights reserved.