circular_permutation

<h2>円順列と数珠順列</h2>

円順列と数珠順列の公式として以下が示されていることが多い。


\(n\) 人を円卓に並べる順列の総数：
\[
(n-1)!
\]
\(n\) 色のビーズを一色ずつ数珠つなぎにする順列の総数：
\[
\frac{(n-1)!}{2}
\]
これはこの形では覚えてはいけない。せめて、以下の意味を理解して覚える。


円順列：
\[
\frac{\permu{n}{n}}{n} = \frac{n!}{n} = (n-1)!
\]
数珠順列：
\[
\frac{\permu{n}{n}}{2n} = \frac{n!}{2n} = \frac{(n-1)!}{2}
\]


すると、先の順列はすべてを並べる場合だったが、\(p\) から \(k\) だけ選んで並べる円順列と数珠順列も自ずと覚えられる。


\(n\) 人中 \(k\) 人を円卓に並べる順列の総数：
\[
\frac{\permu{n}{k}}{k}
\]
\(n\) 色中 \(k\) 色のビーズを一色ずつ数珠つなぎにする順列の総数：
\[
\frac{\permu{n}{k}}{2k} 
\]


円順列：
\[
\frac{\permu{n}{k}}{k} = \frac{n^{\underline{k}}}{k}
= \frac{n!}{k(n-k)!} = \frac{k!}{k}\dbinom{n}{k} = (k-1)!\dbinom{n}{k}
\]
上のように変形して \(n=k\) とすれば \(\binom{n}{n} = 1\) なので元の公式 \((n-1)!\) と等しい。


数珠順列：
\[
\frac{\permu{n}{k}}{2k} = \frac{n^{\underline{k}}}{2k}
= \frac{n!}{2k(n-k)!} = \frac{k!}{2k}\dbinom{n}{k} = \frac{(k-1)!}{2}\dbinom{n}{k}
\]
上のように変形して \(n=k\) とすれば \(\binom{n}{n} = 1\) なので元の公式 \(\frac{(n-1)!}{2}\) と等しい。


\(n=4, k=4\) の場合の円順列と数珠順列：
\[
(4-1)! = \frac{\permu{4}{4}}{4} = (4-1)!\binom{4}{4} = 6
\]
\[
\frac{(4-1)!}{2} = \frac{\permu{4}{4}}{2\cdot 4} = \frac{(4-1)!}{2}\binom{4}{4} = 3
\]
\(n=5, k=4\) の場合の円順列と数珠順列：
\[
\frac{\permu{5}{4}}{4} = (4-1)!\binom{5}{4} = 30
\]
\[
\frac{\permu{5}{4}}{2\cdot 4} = \frac{(4-1)!}{2}\binom{5}{4} = 15
\]

<h2 style="page-break-before: always;">同じものを含む円順列</h2>

まず、同じものの個数 \(p_1, p_2, \cdots, p_{m-1}, p_m\) で表されるものすべて並べる順列は：
\[
\frac{(p_1+p_2+\cdots p_{m-1} + p_m)!}{p_1!p_2!\cdots p_{m-1}!p_m!}
\]
もしくは、
\[
\dbinom{p_1+p_2+\cdots p_m}{p_1}\dbinom{p_2+\cdots p_m}{p_2}\cdots\dbinom{p_{m-1}}{p_{m-1}}\dbinom{p_m}{p_m}
\]
で表される。総和と総積の記号を用いれば：
\[
\frac{(\sum_{i=1}^{m}p_i)!}{\prod_{i=1}^{m}p_i!}
= \prod_{i=1}^{m}\dbinom{\sum_{j=i}^{m}p_j}{p_i}
\]
さらに、順列と組み合わせの記号に置き換えれば：
\[
\frac{\permu{\sum_{i=1}^{m}p_i}{\sum_{i=1}^{m}p_i}}{\prod_{i=1}^{m}\permu{i}{i}}
= \prod_{i=1}^{m}\combi{\sum_{j=i}^{m}p_j}{p_i}
\]
つまり、左辺は、分子「同じものを区別しない場合の順列の場合の数」を分母「重複度、つまり、同じものを並べた場合の順列の場合の数の総積」で割ることを意味している。一方で、右辺は、空いている並びの位置に同じものを割り当てる組み合わせの場合の数の総積を意味している。


\(m\) 色の玉の個数 \(p_1,\; p_2, \cdots, p_{m-1},\; p_m\) として、これらを円に並べる順列の総数：
\[
\frac{(\sum_{i=1}^{m}p_i)!}{\sum_{i=1}^{m}p_i\prod_{i=1}^{m}p_i!}
= \frac{1}{\sum_{i=1}^{m}p_i}\prod_{i=1}^{m}\dbinom{\sum_{j=i}^{m}p_j}{p_i}
\]
\[
\frac{\permu{\sum_{i=1}^{m}p_i}{\sum_{i=1}^{m}p_i}}{\sum_{i=1}^{m}p_i\prod_{i=1}^{m}\permu{i}{i}}
= \frac1{\sum_{i=1}^{m}p_i}\prod_{i=1}^{m}\combi{\sum_{j=i}^{m}p_j}{p_i}
\]
\(m=3,\; p_1=2,\; p_2=2,\; p_3=2\) の場合の同じものを含む円順列：
\[
\frac{(2+2+2)!}{(2+2+2)2!2!2!}
= \frac{1}{2+2+2}\dbinom{2+2+2}{6}\binom{2+2}{2}\binom{2}{2} = 15
\]


以上は、「大学への数学10月号2014年」12頁で掲載され「大学への数学11月号2014年」96頁で訂正された誤った答えに等しい。正解は：
\[
16
\]
なぜなら、同じものがあるので意図しない点対称のものを個別に除外して考えねばならず、この方法が通用しないのである。もしくは、群論の「コーシー・フロベニウスの定理」（バーンサイドの補題）を用いるが、何れにしても、上述の公式のようなものは存在しない。詳しくは、<a href="http://izumi-math.jp/M_Matumoto/101_matsumoto.pdf">松本 睦郎「重複円順列の考え方 − 周期解決法とコーシー・フロベニウス定理」2017年</a>に譲る。


ちなみに、\(m\) 色のビーズの個数 \(p_1,\; p_2, \cdots, p_{m-1},\; p_m\) として、これらを数珠つなぎにする順列の総数は、やはり上式を \(2\) で割ればよいというものではないのでこれも他に譲る。