$\newcommand{\lnl}{\\[8pt]}$
$\newcommand{\Lnl}{\\[18pt]}$
$\newcommand{\delt}{\mathrm{d}}$
$\newcommand{\comb}{\mathrm{C}}$
$\DeclareMathOperator*{\ssum}{\Sigma}$
$\DeclareMathOperator*{\sprod}{\Pi}$
今回は順列の特別な場合である円順列について学びます.
円順列
人や物が円形に並ぶ順列を円順列(Circular Permutation)といいます.
通常の横に並ぶ順列と異なるのは, 円順列の場合, 図のように回転して同じ並び方となる場合は同じとみなすことです.
結論を先に述べます.
$n$人を円形に並べる円順列の総数は,
(n-1)!
\end{align}
となります.
円順列の総数の求め方
方法1(固定パターン)
$n$人の円順列を数えます.
回転して同じになると同じとみなすという条件がありますので, これを逆手にとって回転しても絶対に同じにならないようにすれば数えやすいということに気づきます.
回転して絶対に同じにならないやり方はいくつもあると思いますが, ここではとある一人を固定してしまいます.図のような感じで$1$さんの席を$1$つ決めてしまいます.
こうすると,どんなに回転しても絶対に同じになりませんよね(回転した結果, 元の位置に戻る場合を除きます)
逆に回転した結果が同じであれば同じとみなすことになっていますので, $1$が別の位置にあったとしても, 回転して上記と同じ位置に$1$を持ってこれますので, $1$さんの席を固定しても全ての並び方を網羅できますね.(わかりやすいように色分けしてみました)
$1$さんの場所は決まりましたので, 残りの$(n-1)$人を並べればよいということになります.その並べ方は $(n-1)!$通りです.
方法2(数え上げ)
この方法は純粋に数え上げだけを使います.
まず円順列ということを忘れて$n$人を普通の順列と同じように並べます.この総数は,$n!$通りです.
次に, 回転して同じになるもを同一視します. 下記のように$n$個のパターンを同一視すればいいことがわかります.(円の中の数字は一番左の円順列を何個分右に回転させたかを表します)
従って, 円順列の総数は,
\frac{n!}{n} = (n-1)!
\end{align}
となります.
全員が並ばない円順列
次に, $n$人全員が並ぶのではなく, $k$人($n > k$)が並ぶ円順列を考えます.
これは簡単で, まず並ぶ$k$人を選択します.その選び方は${}_n\comb_k$通りです.
そして, その$k$人全員が円順列に並ぶ総数ですから, 上記で見た通り$(k-1)!$通りあります.
従って, $n$人から$k$人を選び円順列にする総数は,
{}_n\comb_k \times (k-1)! &= \frac{1}{k} \frac{n!}{(n-k)!}\lnl
&= \frac{1}{k}\big(\underbrace{\mathstrut n\cdot(n-1)\cdots(n-k+1)}_{k\text{個}}\big)
\end{align}
となります.
数珠順列
さらに円順列の特別な場合を考えます.円順列と同様に回転して同じ並びになる場合に加えて, 裏返して同じ並びになる場合も同じとみなすのが数珠順列です.
どうも厄介そうですが, 円順列がわかっていれば簡単です.
どの円順列でも裏返したものは必ず$1$つあり, しかも$1$つしかありません.
つまり, 裏返して元の円順列と同じになったり, 裏返したものが$2$つも$3$つもあるケースはありません.
ですので, 数珠順列の総数は円順列のちょうど半分となります.つまり, $n$人を数珠順列に並べる総数は,
\frac{(n-1)!}{2}
\end{align}
となります.
また, $n$人から$k$人選び($n>k$) , $k$人を数珠順列に並べる総数は,
{}_{n}\comb_k \frac{(k-1)!}{2}
\end{align}
となります.