数酸

数学に関して書き留めておこうと思ったものを気まぐれに。

重複数珠順列の公式

{ r }種類の色({ A_1,A_2,...A_r })の玉がそれぞれ{ a_1,a_2,...,a_r }コで計{ n }コあり、これらを円形に配置する。回転および反転で不変な配置は同一視するとして、その配置の総数を

{ g(n; a_1,a_2,...,a_r) }

とする。これを計算するための一般的な公式を作ります。 

 

重複円順列の公式が前提となります。記号も引き継ぎます。円順列とみたときの総数は簡単に{ f }と書きます。

soratobipenguin.hatenablog.com

 

回転対称に関する部分の和は重複円順列の公式をそのまま使えます。

{ n }本の軸を{ s_1,s_2,...,s_n }として{ s_k }に関して対称な配置の総数を{ S_k }とするとバーンサイドの補題から

{\displaystyle g(n; a_1,a_2,...,a_r) =\frac{1}{2n}(\sum_{k=1}^n T_k + \sum_{k=1}^n S_k)  }

{\displaystyle =\frac{1}{2}f+\frac{1}{2n}\sum_{k=1}^n S_k }

 

軸は{ n }が奇数ならすべて玉を一つ通りますが、偶数なら半数は玉を通らず、もう半数は２つの玉を通ります。 また、{ a_1,a_2,...,a_r}の中に奇数がいくつ含まれているかによって線対称な配置の数の計算は変わってきます。このあたりに注意すれば後は単純な重複順列の問題です。

 

{ a_1,a_2,...,a_r }に含まれている奇数の数を{ d }とし、{ d }のときの

{\displaystyle \frac{1}{n}\sum_{k=1}^n S_k }を{ R_d }と書くことにすると

 

{ R_0=\binom{\frac{n}{2}}{  \frac{a_1}{2}, \frac{a_2}{2},...,\frac{a_r}{2}  } }

{ d=1 }のとき。唯一の奇数を{ a_1 }とすると

{ R_1=\binom{\frac{n-1}{2}}{  \frac{a_1-1}{2}, \frac{a_2}{2},...,\frac{a_r}{2}  } }

{ d=2 }のとき。二つの奇数を{ a_1,a_2 }とすると

{ R_2=\binom{\frac{n}{2}-1}{  \frac{a_1-1}{2}, \frac{a_2-1}{2},\frac{a_3}{2}...,\frac{a_r}{2}  } }

{ d \ge 3 }のときは{ R_d=0 }

 

重複数珠順列の公式

上のように定義した{ R_d }によって

 {\displaystyle  g(n; a_1,a_2,...,a_r) =\frac{1}{2}f+\frac{1}{2}R_d  }