次: １の 
乗根
上: オイラーの関数
前: メビウスの反転公式
$ m $ を自然数とし， $ m $ 個の自然数の組，
$ n_1,\ n_2,\ \cdots,\ n_m $ を考える．
$ N=n_1+n_2+ \cdots+n_m $ とする．
また， $ n_1,\ n_2,\ \cdots,\ n_m $ の最大公約数を $ g $ とする．
$ m $ 種類の異なる色の玉がそれぞれ $ n_1,\ n_2,\ \cdots,\ n_m $ 個ある．
これらの玉の順列の総数を $ F(n_1,\ n_2,\ \cdots,\ n_m) $ とする．
\[
F(n_1,\ n_2,\ \cdots,\ n_m)=\dfrac{N!}{n_1!n_2!\cdots n_m!}
\]
である．
次に，これらの玉を円周上に等間隔に並べる．
回転して並びが同じになるものは同じ並べ方とする．
これを円順列という．
円順列の総数を $ f(n_1,\ n_2,\ \cdots,\ n_m) $ とする．
円順列のうち，1回転してはじめてそれ自身と重なるものを既約円順列という．
既約円順列の総数を $ p(n_1,\ n_2,\ \cdots,\ n_m) $ とする．
$ \dfrac{1}{d} $ の回転によってはじめてそれ自身と重なるものの個数を
$ q_d(n_1,\ n_2,\ \cdots,\ n_m) $ とする． $ p(n_1,\ n_2,\ \cdots,\ n_m)=q_1(n_1,\ n_2,\ \cdots,\ n_m) $
である．
補題
このとき，次のことが成立する．
(1) $ q_d(n_1,\ n_2,\ \cdots,\ n_m)\geqq 1 $ なら， $ d $ は $ n_1,\ n_2,\ \cdots,\ n_m $ の公約数であり， したがって $ g $ の約数である．
(2) $ \displaystyle f(n_1,\ n_2,\ \cdots,\ n_m)=\sum_{d|g}q_d(n_1,\ n_2,\ \cdots,\ n_m) $ ．
(3) $ \displaystyle F(n_1,\ n_2,\ \cdots,\ n_m)=N\sum_{d|g}\dfrac{1}{d}q_d(n_1,\ n_2,\ \cdots,\ n_m) $ ．
(4) $ d|g $ のとき，
$ \displaystyle q_d(n_1,\ n_2,\ \cdots,\ n_m)
=p\left(\dfrac{n_1}{d},\ \dfrac{n_2}{d},\ \cdots,\ \dfrac{n_m}{d}\right) $ ．■
証明
(1) 円順列の $ \dfrac{1}{d} $ の区画にあるそれぞれの色の個数の $ d $ 倍がその色の個数なので， $ d $ は $ n_1,\ n_2,\ \cdots,\ n_m $ の公約数であり， $ g $ の約数である．
(2) 各円順列は， $ \dfrac{1}{d} $ の回転によってはじめてそれ自身と重なるという $ d $ が， $ d|g $ なるいずれかの $ d $ 一つに対応する．
(3) $ \dfrac{1}{d} $ の回転によってはじめてそれ自身と重なる円順列に対して， $ \dfrac{1}{d} $ の区画には $ \dfrac{N}{d} $ の玉があり，そのいずれかの手前で切断することにより， 一つの順列が得られ，これらはすべて異なる．よって， $ \displaystyle F(n_1,\ n_2,\ \cdots,\ n_m)\geqq N\sum_{d|g}\dfrac{1}{d}q_d(n_1,\ n_2,\ \cdots,\ n_m) $ である． 逆に，一つの順列は両端を閉じることにより一つの円順列を定め， それから同じ手順で順列を作ることにより，もとの順列が得られる． よって，等号が成立する．
(4) $ \dfrac{1}{d} $ の回転によってはじめてそれ自身と重なる円順列の，
$ \dfrac{1}{d} $ の区画の両端をつなぐことで，総数が $ \dfrac{N}{d} $ 個で，
各色が $ \dfrac{n_1}{d},\ \dfrac{n_2}{d},\ \cdots,\ \dfrac{n_m}{d} $ 個の円順列が得られ，
これは，「はじめてそれ自身と重なる」ことより既約である．
逆に， $ \dfrac{n_1}{d},\ \dfrac{n_2}{d},\ \cdots,\ \dfrac{n_m}{d} $ 個の既約円順列を $ d $ 回重ねることにより，
総数が $ N $ で， $ \dfrac{1}{d} $ の回転によってはじめてそれ自身と重なる円順列が得られる．□
この補題から，
\begin{eqnarray*}
&&f(n_1,\ n_2,\ \cdots,\ n_m)=\sum_{d|g}p\left(\dfrac{n_1}{d},\ \dfrac{n_2}{d},\ \cdots,\ \dfrac{n_m}{d}\right)\\
&&F(n_1,\ n_2,\ \cdots,\ n_m)=N\sum_{d|g}\dfrac{1}{d}p\left(\dfrac{n_1}{d},\ \dfrac{n_2}{d},\ \cdots,\ \dfrac{n_m}{d}\right)
\end{eqnarray*}
が得られる．ここまでは，すべての数値を固定して考えている．
ここで，$a_j=\dfrac{n_j}{g}$とおき，
$F(d)=F\left(da_1,\ da_2,\ \cdots,\ da_m\right)$とする．
また，$p\left(\dfrac{n_1}{d},\ \dfrac{n_2}{d},\ \cdots,\ \dfrac{n_m}{d}\right)$で，$\dfrac{g}{d}$を改めて$d$とおくと，これは$p\left(da_1,\ da_2,\ \cdots,\ da_m\right)$となる．
$d|g$ となる $d$ 全体の和は，$\dfrac{g}{d}$ を改めて $d$ としても変わらないので，
$G(d)=\dfrac{N}{g}dp\left(da_1,\ da_2,\ \cdots,\ da_m\right)$ とおくと，上記第二式は
\[
F(g)=\sum_{d|g}G(d)
\]
となる．これは $g$ を任意の正整数にとってもなり立つ．
メビウスの反転公式の変数 $n$ を $g$ にとることにより，
\[
G(g)=\sum_{d|g}\mu \left(\dfrac{g}{d} \right)F(d)
\]
が得られる．
この式も，$g$ を任意の正整数にとってなり立つ．
それぞれ自然数を変数とする関数の関数等式である．
また上記第一式は
\[
f(n_1,\ n_2,\ \cdots,\ n_m)=\sum_{d|g}p\left(da_1,\ da_2,\ \cdots,\ da_m\right)
\]
となる．
\[
p\left(da_1,\ da_2,\ \cdots,\ da_m\right)
=\dfrac{g}{dN}G(d)
\]
であり，
\[
G(d)=\sum_{e|d}\mu \left(\dfrac{d}{e} \right)F(e)
\]
なので，
\begin{eqnarray*}
f(n_1,\ n_2,\ \cdots,\ n_m)&=&\sum_{d|g}\left\{\dfrac{g}{dN}\sum_{e|d}\mu \left(\dfrac{d}{e} \right)
F\left(ea_1,\ ea_2,\ \cdots,\ ea_m\right)\right\}\\
&=&\dfrac{g}{N}\sum_{e|g}\left\{F\left(ea_1,\ ea_2,\ \cdots,\ ea_m\right)\sum_{d:e|d|g} \mu \left(\dfrac{d}{e} \right)\dfrac{1}{d} \right\}\\
&=&\dfrac{g}{N}\sum_{e|g}\left\{F\left(ea_1,\ ea_2,\ \cdots,\ ea_m\right)\sum_{j|\frac{g}{e}} \mu \left(j\right)\dfrac{1}{je} \right\}\\
&=&\dfrac{g}{N}\sum_{e|g}\left\{\dfrac{1}{e}F\left(ea_1,\ ea_2,\ \cdots,\ ea_m\right)\sum_{j|\frac{g}{e}} \mu \left(j\right)\dfrac{1}{j} \right\}
\end{eqnarray*}
ここで，前節のメビウス関数とオイラー関数の関係式を用いると，
\[
\sum_{j|\frac{g}{e}} \mu \left(j\right)\dfrac{1}{j}=\dfrac{e}{g}\varphi\left(\dfrac{g}{e} \right)
\]
となるので，
\begin{eqnarray*}
f(n_1,\ n_2,\ \cdots,\ n_m)&=&\dfrac{1}{N}\sum_{e|g}\varphi\left(\dfrac{g}{e} \right)F\left(ea_1,\ ea_2,\ \cdots,\ ea_m\right)\\
&=&\dfrac{1}{N}\sum_{d|g}\varphi\left(d\right)F\left(\dfrac{n_1}{d},\ \dfrac{n_2}{d},\ \cdots,\ \dfrac{n_m}{d}\right)
\end{eqnarray*}
が得られる．
次: １の 乗根
上: オイラーの関数
前: メビウスの反転公式
Aozora Gakuen