数酸

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

重複円順列の公式

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

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

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

 

{ \frac{2k\pi}{n} }の時計回りの回転を{ k }度回転と呼ぶことにします。

バーンサイドの補題を適用すると、{ T(k) }で{ k }度回転で不変な配置の総数として

{\displaystyle f(n; a_1,a_2,...,a_r) =\frac{1}{n} \sum_{k=1}^{n} T(k) }

 

バーンサイドの補題の証明は別の記事で

soratobipenguin.hatenablog.com

 

{ n }の約数{ k }については、{ a_1,a_2,...,a_r }の公約数でないときは{ T(k)=0 }であり公約数であるときは

{\displaystyle T(\frac{n}{k})=\binom{\frac{n}{k}}{  \frac{a_1}{k}, \frac{a_2}{k},...,\frac{a_r}{k}   } }

 

{ k }度回転で不変な配置というのは{ {\rm gcd}(k,n) }度回転で不変な配置と等しいことに注意しましょう。

 

{\displaystyle \sum_{k=1}^{n}T(k)=\sum_{m|n} T(m)\#\{j; {\rm gcd}(j,n)=m \} }

{\displaystyle =\sum_{m|n} T(m)\phi(\frac{n}{m})=\sum_{k|n} T(\frac{n}{k})\phi(k) }

{ \phi(k) } はオイラー関数、つまり{ k }と互いに素な{ k }以下の正整数の総数です。

 以上から

重複円順列の公式

{ C }を{ (n,a_1,a_2,...,a_r) }の公約数の集合とすると

{\displaystyle f(n; a_1,a_2,...,a_r)=\frac{1}{n} \sum_{k \in C} \phi(k) \binom{\frac{n}{k}}{  \frac{a_1}{k}, \frac{a_2}{k},...,\frac{a_r}{k}   }  }

 

例.　赤玉、青玉、黄玉をそれぞれ４つ、計１２コ円形に並べる場合の総数は

{\displaystyle f(12;4,4,4)=\frac{1}{12} \sum_{k \in \{1,2,4\}} \phi(k) \binom{\frac{12}{k}}{  \frac{4}{k}, \frac{4}{k},\frac{4}{k}   }=2896  }