同じものを含む円順列の一般公式
はじめに
この記事では次の問題を解いていきたいと思います。
$n_1$個の玉$P_{1}$,$n_2$個の玉$P_2,$...,$n_{m}$個の玉$P_{m}$、合計$n_1+n_2+ \cdot \cdot \cdot +n_m$個の玉を円形に並べる方法の総数は何通りか？
メビウス関数やオイラーの$\phi$関数などが出てきますが、記事内で定義から用いる性質までしっかり説明しますので、これらの関数について知らなくても、楽しんでいただけると思います。
"円形に並べる"をとらえる
まずはここを明確にしていきます。
円順列は、順列においては異なるとみなしていたものを同じとみなしたときの総数ととらえることができます。すなわち、順列として考えられるもの全体に対して、１つ１つのはじをつなげて輪っかにし、適当に回すことで完全に一致するものを集めて一つのグループにし、そのグループの総数が、求める円順列の総数となります。
周期
すると、一つの順列に対し同じグループに属する順列の総数は違うことがあります。その値をここではその順列に対する周期と呼ぶことにします。
周期は、輪っかにしたものを最初から一つずつずらして回転していったときに、初めて全体が一致するまで動かした回数に等しいです。一周しても一致しなければ周期は$n_1+n_2+\cdot$$\cdot$$\cdot+n_m$となります。
また周期は$n_1$,$\cdot$$\cdot$$\cdot$,$n_m$の最大公約数を$g$,$n_1$=$g$$ \acute{ n_1} $,$\cdot$$\cdot$$\cdot$,$n_m$=$g$$\acute{n_m}$としたとき、($\acute{n_1}+\cdot\cdot\cdot+\acute{n_m}$)$d$ ($d$は$g$の約数) と表されることが分かります。
ここで$\acute{n_1},\cdots,\acute{n_m}$を固定します。
$n$に対して$P_1$を$\acute{n_1}n$個,$\cdots,P_m$を$\acute{n_m}n$個用いた順列の総和を$F(n)$とおくと$F(n)= \frac{(\acute{n_1}n + \cdots \acute{n_m}n)!}{(\acute{n_1}n)! \cdots (\acute{n_m}n)!} $です。
また、周期が$(\acute{n_1}+ \cdots+\acute{n_m} )d$である順列の総数を$f(d)$とすれば、$F(n)= \sum_{d|n}^{} f(d)$が成り立ちます。
さらに、求める総数を$X$とすれば、$X= \sum_{d|n}^{} \frac{f(d)}{(\acute{n_1}+ \cdots+\acute{n_m})d} $であることが、周期の定義からわかります。
このように、求める$X$を$f(d)$を仲介にして$F(n)$という簡単に計算できるものと結びつけることができました。以下ではこれを一つの等式として結び付ける形に仕上げていくのですが、それにはメビウス関数とそれを用いた"メビウスの反転公式"に、オイラーの$\phi$関数が必要となります。
メビウス関数$\mu(n)$
この関数は
$$
\mu (n)=\begin{eqnarray}
\left\{
\begin{array}{l}
1 (n=1のとき)\\
0 (nがある素数で二回以上割り切れるとき) \\
(-1)^{k} (nが相異なるk個の素数の積のとき)
\end{array}
\right.
\end{eqnarray}
$$
と定義されます。
すると、以下の重要な性質が成り立ちます。
$n \geq 2$な整数に対し、$\sum_{d|n}^{} \mu (n)=0$
$\mu(d) \neq 0$である$d$は、$n$の素因数を$p_1,p_2, \cdots ,p_l$としたとき、$ p_1^{e_1} \times\cdots\times\ p_l^{e_l} $($e_1,\cdots,e_l$はすべて$0$か$1$)の$2^l$個。$k$個の素数の積に対して$\mu$は$(-1)^k$を返すので、この$2^l$個の和は、
$1- {}_l \mathrm{ C }_1 +\cdots+(-1)^k {}_l \mathrm{ C }_l=(1-1)^l=0 $となって示されました。
$f(n),g(n)$を正の整数から実数への関数とすると
$f(n)= \sum_{d|n}^{}g(d) $ ならば、$g(n)= \sum_{d|n}^{} \mu ( \frac{n}{d} )f(d) $
が成り立つ。
$\sum_{d|n}^{} \mu( \frac{n}{d} )f(d) = \sum_{d|n}^{}\mu(\frac{n}{d}) \sum_{\acute{d}|d}^{} g(\acute{d})$
$=\sum_{d|n}^{} \sum_{\acute{d}|d}^{} \mu( \frac{n}{d} )g(\acute{d})$
$\acute{d}$を固定して$d$を動かすと、$d$は$n$の約数かつ$\acute{d}$の倍数を動き、これはすなわち、$\frac{n}{d}$が$\frac{n}{\acute{d}}$の約数になるように動くということです。このとき$\acute{d}$は$n$の約数を動くので、上の式は
$\sum_{\acute{d}|n}^{}g(\acute{d}) \sum_{ \frac{n}{d}| \frac{n}{\acute{d}} }^{ } \mu( \frac{n}{d} )$
と変形することができます。
$\frac{n}{\acute{d}} \geq 2$つまり$\acute{d} \neq n$に対しては$\sum_{ \frac{n}{d}|\frac{n} {\acute{d}}}^{}\mu( \frac{n}{d} )=0$であったので
$=g(n)\mu( \frac{n}{n} )=g(n)$
となって、これが求める式でした。
オイラーの$\phi$関数
正の整数$n$に対して、$1$以上$n$以下で、$n$と互いに素であるような整数の個数を$\phi(n)$と書き、これをオイラーの$\phi$関数と呼びます。ここでは次の性質のみを押さえておけば十分です。
$n= \sum_{d|n}^{} \phi(d) (= \sum_{d|n}^{} \phi( \frac{n}{d} ) )$
$1 \leq k \leq n$が、$k=d\acute{k}$($\acute{k}$は$\frac{n}{d}$と互いに素)と一意的に表すことができることを示せばよく、これは$\frac{n}{d}=\acute{n}$とすると、
$\begin{eqnarray}
\left\{
\begin{array}{l}
k=d\acute{k} \\
n=d\acute{n}
\end{array}
\right.
\end{eqnarray}$
となり、$\acute{k}$と$\acute{n}$は互いに素なので、$d$が$k$と$n$の最大公約数となることから分かる。
これとメビウスの反転公式から
$ \phi(n)= \sum_{d|n}^{} \mu( \frac{n}{d} )d $
が分かります。
仕上げ
これまでで
$\begin{eqnarray}
\left\{
\begin{array}{l}
F(n)= \sum_{d|n}^{} f(d) \\
X= \sum_{d|n}^{} \frac{f(d)}{(\acute{n_1}+\cdots+\acute{n_m})d}
\end{array}
\right.
\end{eqnarray}$
が導かれていたのでした。
上の式にメビウスの反転公式を適用して、
$f(n)= \sum_{d|n}^{} \mu( \frac{n}{d} )F(d) $
これを下の式に代入して、
$X= \frac{1}{\acute{n_1}+\cdots+\acute{n_m}} \sum_{d|n}^{} \frac{1}{d} \sum_{\acute{d}|d}^{} \mu ( \frac{d}{\acute{d}} ) F(\acute{d})$
$ = \frac{1}{\acute{n_1}+\cdots+\acute{n_m}} \sum_{d|n}^{}\sum_{\acute{d}|d}^{} \frac{1}{d} \mu( \frac{d}{\acute{d}} )F(\acute{d})$
$=\frac{1}{\acute{n_1}+\cdots+\acute{n_m}}\sum_{d|n}^{}\sum_{\acute{d}|d}^{}\frac{n}{d}\mu( \frac{ \frac{n}{\acute{d}} }{ \frac{n}{d} } ) \frac{F(\acute{d})}{n}
$
メビウスの反転公式の場合と同様に、$\acute{d}$を固定すると、$ \frac{n}{d} $が$\frac{n}{\acute{d}}$の約数となるように動くので
$= \frac{1}{\acute{n_1}+\cdots+\acute{n_m}}\sum_{\acute{d}|n}^{} \frac{F(\acute{d})}{n}\sum_{ \frac{n}{d}| \frac{n}{\acute{d}} }^{ } \frac{n}{d} \mu( \frac{ \frac{n}{\acute{d}} }{ \frac{n}{d} } ) $
オイラーの$\phi$関数の節の中で示した最後の式からこれは
$=\frac{1}{(\acute{n_1}+\cdots+\acute{n_m})n}\sum_{\acute{d}|n}^{}F(\acute{d}) \phi( \frac{n}{\acute{d}} ) $
となり、次の結論の式を得ることができました。
$n_1$個の玉$P_{1}$,$n_2$個の玉$P_2,$...,$n_{m}$個の玉$P_{m}$計$n_1+n_2+ \cdots +n_m$個の玉を円形に並べる方法の総数は、$n_1,n_2,\cdots,n_m$の最大公約数を$g$とすると、
$ \frac{1}{n_1+n_2+ \cdots +n_m} \sum_{d|g}^{}F(d) \phi( \frac{g}{d} )$
で表される。
計算例
例えば白玉$6$個,黒玉$3$個のときは、$g=3$であり、円順列の総数は
$ \frac{1}{9}(F(3)+2F(1))=\frac{1}{9}( \frac{9!}{6!3!}+ 2\frac{3!}{2!1!} )= \frac{1}{9}(84+6)=10$
と計算できます。
