unique necklace from 6 beads

Question

I'm trying to calculate the number of unique bracelets of length $6$ that can be made from $6$ differently colored beads. A same color bead can be repeated and used as many times as possible as the length permits.

My initial attempt:

I subdivided unique bracelet into certain combinations such as

$AAAAAA$ (where $A$ is the same color bead) which there can only be $6$ unique bracelets. $AAAAAB$ (where $A$ is a color $1$ bead and B is a color $2$ bead) which there can only be $6\cdot5$ ($30$ braclet)

... and so forth, I summarized results in this table:

I ended up with $3267$ unique combinations. Is this a correct calculation?

Also is there a better way to calculate this problem?

Answer 1

Paul Raff gave a formula for both bracelets and necklaces so in my answer, I will provide a general method that you can use for this kind of problem. It works also if you want to colour a cube for example.

As Paul Raff pointed out, you did get mix up between bracelet and necklace so in my answer I will include the answer for both of them.

---

Where did you get it wrong?

It seems to me that you are counting number of ways to colour a bracelet rather than a necklace so I checked your calculation with respect to colouring a bracelet. I would say that the main problem in your counting is that even for each case of the base, you cannot always guarantee to get the final result for that case by multiplying as you did. For example, in the case of $A^2B^2C^2$, we consider two following iterations:

The one on the left gives $\frac{6\cdot5\cdot 4}{3!}=\frac{120}{6}$ ways to choose three colours $A,B,C$, which is what you gave in your table. However, the one on the right gives $\frac{6 \cdot 5 \cdot 4}{2}=\frac{120}{2}$ ways to choose three colours $A,B,C$.

Necklace colouring

You can use Burnside lemma where you can count the number of ways to colour the object by looking at its group of symmetry $G$. For the necklace, the group $G$ can be:

• Two colourings of the necklace are considered the same if from one colouring, we can rotate the necklace to get to the other colouring. There are $5$ possible rotations at angles $60^{\circ}\cdot i \; (i=1,2,3,4,5)$ (not including the do-nothing rotation). Hence, these five rotations are from the mentioned set $G$.
• The "do nothing" action, i.e. we do nothing to the necklace. This is also in $G$.

Let $X$ be the set of all possible colouring for the necklace at a fixed orientation. This follows $|X|=6^6$ as there are $6$ possible colours for each bead.

Now, in Burnside lemma, we essentially want to count number of colourings from $X$ that remains unchanged under actions from $G$. In particular:

• How many colourings in $X$ for the necklace so that it is still the same colouring after we apply $60^{\circ}$ rotation to the necklace? This only happens when all the beads have the same colour. Hence, there are $6$ possible colourings in this case.

• The same question can be asked for $120^{\circ}$ rotation: This happens when three of the beads (each is one bead away from the other) have the same colour and the remaining three beads have the same colour. There are $6$ possible colours for the first three beads and there are $6$ other possible colours for remaining $6$ beads. This gives us $6^2$ possible colourings.

• Similarly, with $180^{\circ}$ rotation, a colouring is fixed under this rotation when any pair of opposite beads have the same colour. There are $6$ ways to colour each pair of opposite beads so there are $6^3$ possible colourings.

• With $240^{\circ}$ rotation, it's the same as $120^{\circ}$ so we have $6^2$ possible colourings. With $300^{\circ}$, it's the same as $60^{\circ}$ so we have $6$ possible colourings.

• With the "do nothing" action then every colouring remains unchanged after this action so there are $6^6$ possible colourings.

The Burnside lemma says that you can add all these numbers up and divide by number of elements of $G$ (which is $6$) to obtain all possible colourings. Hence, the answer for colouring a necklace is $$\frac{6^6 \cdot 1 +6 \cdot 2+ 6^2 \cdot 2+6^3 \cdot 1}{6}=7826.$$

Bracelet colouring

The difference between bracelets and necklaces is in the group of symmetry $G$. In particular, for bracelets, $G$ has some extra elements: Two colourings of the bracelet are considered same if from one colouring, we can reflect the bracelet through a line to obtain the other colouring. There are two types of lines:

• A line connecting two opposite beads (see diagram on the right). There are $3$ pairs of opposite beads so there are three reflections through these types of lines. These actions are in $G$.
• A line dividing the $6$ beads in equal parts (diagram on the left). There are $3$ such lines corresponding to three extra reflections in $G$.

This time $G$ has $12$ elements.

Next, we do the same thing with necklace, i.e. we count number of colourings that remains fixed under these reflections:

• For reflection across axis on the left, any two beads that appear symmetrically through that axis must have same colour. There are $3$ pairs of such beads so there are $6^3$ possible colourings. Since there are three axes of this type so we have $3 \cdot 6^3$.
• For reflection across axis on the right, note that we can freely choose any colour for the beads that pass through the axis while keeping the same colouring of the bracelet when reflecting. Hence, this gives $6^2$ for such two beads, and $6^2$ for $2$ pairs of symmetrical beads. We obtain $6^4$ possible colourings for such axis. As there are three axes of this type so it is $3 \cdot 6^4$.

Now, applying Burnside's lemma, we sum up all these numbers counted for each element in $G$ then we divide by number of elements in $G$ (which is $12$). The final answer is $$\frac{1}{12}\left( 6^6 \cdot 1+6 \cdot 2+ 6^2 \cdot 2+6^3 \cdot 1+6^3 \cdot 3+ 6^4 \cdot 3 \right)=4291.$$

Answer 2

Your title references necklaces, but your content and your examples seemingly talk about bracelets. There's a distinction between the two that's covered in this Wikipedia article, along with a helpful formula.

In short, a bracelet allows two configurations to be equivalent if one reflects to the other (like taking it off your wrist and flipping it around). So the number of bracelets will be at most the number of necklaces, all else being equal.

The number of necklaces with $n$ total beads, created from at most $k$ different types of beads, is

$$N_k(n)=\frac{1}{n}\sum_{d\mid n}\varphi(d)k^\frac{n}{d}$$

Where $\varphi$ is the Totient Function. See this article for an explanation of this formula.

From this, we get the number of bracelets via

$$B_k(n) = \begin{cases} \tfrac12 N_k(n) + \tfrac14 (k+1)k^\frac{n}{2} & \text{if }n\text{ is even} \\[10px] \tfrac12 N_k(n) + \tfrac12 k^\frac{n+1}{2} & \text{if }n\text{ is odd} \end{cases}$$

Putting this all together, the number of necklaces with 6 beads total, using at most 6 unique beads is

$$ N_6(6) = \frac{1}{6}\left( 1 \cdot 6^6 + 1 \cdot 6^3 + 2 \cdot 6^2 + 2 \cdot 6^1\right) = 7826 $$

and the number of bracelets with 6 beads total, using at most 6 unique beads is

$$ B_6(6) = \frac{1}{2} N_6(6) + \frac{1}{4}(7)6^{3} = 4291 $$

It's hard to know where you went astray in your calculations; for one thing, in the $AAAAAA$ scenario there is only one unique necklace/bracelet. No matter which way you turn/rotate it, it always looks the same.

Answer 3

Well, we can do casework on the ways it can be rotated to be unique (which can be $1,2,3,6$).

1) There are $6$ combinations.

2) There are $\frac{6^2-6}2=15$ combinations.

3) There are $\frac{6^3-6}3=70$ combinations.

6) There are $\frac{6^6-6-6^2-6^3+12}6=7735$ combinations.

The total number of combinations are $7735+70+15+6=\boxed{7826}.$