next up previous 次: 1の $n$乗根 上: オイラーの関数 前: メビウスの反転公式

円順列への反転公式の応用

 メビウスの反転公式の一つの応用として,円順列の総数を求める一般的方法を導くことができる.  これは,VISUAL数学を目指して の中の「全順列,全射,円順列の総数−反転公式および和集合の要素数に関する公式の利用」にもある.

  $ 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*} が得られる.


next up previous 次: 1の $n$乗根 上: オイラーの関数 前: メビウスの反転公式
Aozora Gakuen