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?

  • $\begingroup$ the problem for case $\lambda=(k,s)$ is intersting by itself. $\endgroup$ – Radmir Jan 8 '16 at 11:09

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.