3
$\begingroup$

I am interested to know if there's a way to calculate the number of (rotation agnostic) necklaces that can be produced from different colored beads, each color with its own quantity.

For instance, if I have a 3 red beads, 2 green beads and 1 blue bead, I can produce 10 distinct necklaces (see attached image).

However, other than constructing all the necklaces and counting them (which is what I did), how can I arrive at the number of distinct necklaces that can be produced with the given beads?

Note, I am looking for a general solution, where the number of colors, and the quantity of beads in each color can be given freely.

Can you help?

enter image description here

EDIT:

It appears that I figured out a formula that works for the majority of cases. It fails however when the quantity of all the beads has a common denominator.

\frac{(a_1+a_2+\ \cdots\ +\ a_n-1)!}{a_1!\ \bullet\ a_2!\ \bullet\cdots\ \bulleta_n!}

So this works, unless I have 2 of each bead, or 3 of each bead. Or 2 and 4 of each bead, etc.

Can't figure out how to solve for that case though..

$\endgroup$
10
  • 1
    $\begingroup$ In this case: place the blue one (that fixes the rotation). You now have $5$ slots. Place the red ones. $\binom 53=10$. $\endgroup$
    – lulu
    Jan 10, 2022 at 21:39
  • 1
    $\begingroup$ Side note: I don't see colors very well, but it seems to me that one of your pictures (second from the left in the bottom row) has only one green bead. $\endgroup$
    – lulu
    Jan 10, 2022 at 21:49
  • 1
    $\begingroup$ Phew. I only gave myself a $50-50$ shot at being right about that. Red-green can be just a question of mood. $\endgroup$
    – lulu
    Jan 10, 2022 at 21:54
  • 2
    $\begingroup$ Oh, there is, sort of...the links I proposed reference the Poyla Enumeration Theorem, which is at the heart of problems like this. There is a generating function approach you can use, which is sketched here. $\endgroup$
    – lulu
    Jan 10, 2022 at 22:03
  • 2
    $\begingroup$ Burnside's lemma and Polya's enumeration theorem can be applied to this type of problem. $\endgroup$
    – N. F. Taussig
    Jan 10, 2022 at 22:03

1 Answer 1

Reset to default
2
$\begingroup$

To use the Pólya enumeration theorem we first need to weight the beads so that the given bead distribution is the only way to make the combined weight from an arbitrary selection of however many beads are in the necklace. One way that works here is to have weight-$0$ red, weight-$2$ green and weight-$3$ blue beads, since $7$ can only be written as $3+2+2+0+0+0$. This leads to a certain generating function $$f(t)=1+t^2+t^3$$ We now need the cycle index polynomial, which here is $$Z_{C_6}(t_1,t_2,t_3,t_6)=\frac16(t_1^6+2t_6+2t_3^2+t_2^3)$$ Then the desired count is the $t^w$ coefficient of $Z$ with the $t_i$ argument assuming a value of $f(t^i)$, where $w$ is the total weight of beads under the given weighting. Here we get $$[t^7]Z(f(t),f(t^2),f(t^3),f(t^6))=10$$ as expected.

The contrived weights above were to keep things simple for a first explanation – $f$ does not have to be single-variable, and the colours need not be numbers; they can be vectors of integers. We can assign red, green and blue weights of $(0,0),(1,0),(0,1)$ respectively, then clearly the desired distribution of weights corresponds only to $(2,1)$ and $$f(t,u)=1+t+u$$ The $f$ put in the $t_i$ argument of $Z$ now has all its arguments to the $i$th power, and in this case we have the answer as $$[t^2u]Z(f(t,u),f(t^2,u^2),f(t^3,u^3),f(t^6,u^6))=10$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .