Number of colorings under cyclic permutation.

194 Views Asked by At

Given $\lambda\vdash n$. How many ways to color $n$ beads of chaplet into $l$ colors, such that $\lambda_1$ of $1^{st}$ color, $\lambda_2$ of $2^{nd}$ color, etc. For, examples if $\lambda=(3,2)$, then number of ways is $2$: $$aaabb, aabab$$ Seems that this is well-known problem.

Case $\lambda_l=1$ is easy, the answer for this case is $$\binom {n-1} {\lambda_1,\lambda_2, \cdots, \lambda_{l-1}}$$ by choosing unique bead of $l^{th}$ color as leading bead in chaplet.

Then also reccurence formula (i've got) is different for some cases. Let number of ways for $\lambda $ be $C_{\lambda}$. Then if there any $\lambda_i$ non-divisor of $n$, then $$C_{\lambda}=C_{(n-\lambda_i,\lambda_i)}\cdot\binom {n-\lambda_i} {\lambda_1,\cdots, \lambda_{i-1},\lambda_{i+1}, \cdots, \lambda_{l}} $$ If $\lambda_i$ is divisor of $n$, then reccurence is more complex.

So is there any good formula or something?

1

There are 1 best solutions below

0
On BEST ANSWER

I take you use chaplet for what is called a necklace (rotation symmetries only).

This is a job for Pólya's coloring theory. If there are $r$ colors, we can use the variable $z_i$ to mark the number of beads of color $i$, the generating function for the number of distinguishable colorings under permutation group $G$ of order $n$ is:

$\begin{align} \zeta_G(z_1 + \dotsb + z_r, z_1^2 + \dotsb + z_r^2, \dotsc, z_1^n + \dotsb + z_r^n) \end{align}$

Here $\zeta_G(x_1, \dotsc, x_n)$ is the cycle index of the group. The coefficient of $z_1^{b_1} z_2^{b_2} \dots z_r^{b_r}$ in this is the number of distinguishable colorings when there are $b_i$ beads of color $i$.

You need the cycle index for your group, which is just the cyclic group $C_n$ if there are $n$ beads in all:

$\begin{align} \zeta_{C_n}(x_1, x_2, \dotsc, x_n) = \frac{1}{n} \sum_{d \mid n} \phi(d) \, x_d^{n/d} \end{align}$

No, there is no "simple formula", except for special cases like a prime number of beads.