How many necklaces can we create?

[mathmari]

Hey!

I want to find how many different necklaces we can create with $m$ symmetric beads if we have $k$ colours. Burnside's Formula is the following: $$\text{ # orbits } =\frac{1}{|G|}\sum_{g\in G} X (g)$$

In this case $G$ is the group of the permutations of the symmetric beads, or not? (Wondering)

And $X(g)$ is the number of elements that $g$ leaves unchanged, right? But how can we find this number in this case? Could you give me a hint? (Wondering)

 

[I like Serena]

Hey!

I want to find how many different necklaces we can create with $m$ symmetric beads if we have $k$ colours. Burnside's Formula is the following: $$\text{ # orbits } =\frac{1}{|G|}\sum_{g\in G} X (g)$$

In this case $G$ is the group of the permutations of the symmetric beads, or not? (Wondering)

And $X(g)$ is the number of elements that $g$ leaves unchanged, right? But how can we find this number in this case? Could you give me a hint? (Wondering)

Hey mathmari! (Smile)

Yes. We have $G=D_m$. (Thinking)

Suppose we have $m=4$ beads and $k=2$ colors.
Then a possible necklace is $ABAB$.
If we rotate all beads by 2, we get the same necklace.
So we have found that $r^2$ leaves $ABAB$ unchanged.

Suppose we rotate the beads by one ($r$).
Which necklace configurations will turn out the same then? (Wondering)

 

[mathmari]

We have $G=D_m$. (Thinking)

Does it stand because when we rotate or reflect the necklace we will have the same necklace? (Wondering)

Suppose we have $m=4$ beads and $k=2$ colors.
Then a possible necklace is $ABAB$.
If we rotate all beads by 2, we get the same necklace.
So we have found that $r^2$ leaves $ABAB$ unchanged.

Suppose we rotate the beads by one ($r$).
Which necklace configurations will turn out the same then? (Wondering)

If we rotate all beads by one, we get $BABA$, or not? (Wondering)

 

[I like Serena]

Does it stand because when we rotate or reflect the necklace we will have the same necklace? (Wondering)

Yes.
Rotating the necklace means the beads are in a different spot, but it's indeed still the same necklace.
And we can't "reflect" the necklace in the real world, but we can put it upside down, which happens to correspond to a reflection. (Thinking)

If we rotate all beads by one, we get $BABA$, or not? (Wondering)

Yes.
And even though it's the same necklace, we consider this a different configuration.
So a rotation of 1 bead does not leave the necklace ABAB unchanged. (Thinking)

 

[mathmari]

Rotating the necklace means the beads are in a different spot, but it's indeed still the same necklace.
And we can't "reflect" the necklace in the real world, but we can put it upside down, which happens to correspond to a reflection. (Thinking)

What do you mean by "a different spot" ? (Wondering)

So, every group at which the elements are the same after a rotation or a reflection is equal to the dihedral group? (Wondering)

And even though it's the same necklace, we consider this a different configuration.
So a rotation of 1 bead does not leave the necklace ABAB unchanged. (Thinking)

Why do we consider this a different configuration? (Wondering)

 

[I like Serena]

What do you mean by "a different spot" ? (Wondering)

So, every group at which the elements are the same after a rotation or a reflection is equal to the dihedral group? (Wondering)

Why do we consider this a different configuration? (Wondering)

A different spot is a different spatial location.
So the following are 2 different spatial configurations that represent the same necklace.
[textdraw]
B A A B
A B B A
B A A B[/textdraw]

And yes, if we freely allow rotations and allow turning the object upside down, we're talking about a dihedral group.
If the object cannot be turned upside down, we're talking about a cyclic group (rotations). (Nerd)

 

[mathmari]

A different spot is a different spatial location.
So the following are 2 different spatial configurations that represent the same necklace.
[textdraw]
B A A B
A B B A
B A A B[/textdraw]

And yes, if we freely allow rotations and allow turning the object upside down, we're talking about a dihedral group.
If the object cannot be turned upside down, we're talking about a cyclic group (rotations). (Nerd)

Ah ok... (Thinking)

So, we have that $|G|=|D_m|=2m$, right? (Wondering) How can we find in general how many elements leave $g$ unchanged? (Wondering)

 

[I like Serena]

So, we have that $|G|=|D_m|=2m$, right? (Wondering) How can we find in general how many elements leave $g$ unchanged? (Wondering)

Right.
Before we get to the general method, let's try to find a spatial configuration that is unchanged if we rotate it by one bead.
Can you find one? (Wondering)

Suppose we pick the first bead to be $A$.
If we rotate it to the right by one bead, that means the second bead also has to be $A$ doesn't it? (Wondering)

 

[mathmari]

Suppose we pick the first bead to be $A$.
If we rotate it to the right by one bead, that means the second bead also has to be $A$ doesn't it? (Wondering)

Why? I got stuck right now... (Wondering)

 

[I like Serena]

Why? I got stuck right now... (Wondering)

Suppose we start with $A...$.
If we rotate it by 1 bead we get $.A..$.
Since it is supposed to be the same spatial configuration, that means we need to have $AA..$.
Then, if we rotate it by 1 bead, we get $.AA.$.
In turn that means our necklace needs to be $AAA.$.
Repeating the argument, we get $AAAA$. (Thinking)

In short, if we start with a first bead of $A$, and if we want the necklace to be unchanged under $r$, the necklace needs to be $AAAA$.
Alternatively, if we start with $B$, the necklace needs to be $BBBB$. (Thinking)

 

[mathmari]

Suppose we start with $A...$.
If we rotate it by 1 bead we get $.A..$.
Since it is supposed to be the same spatial configuration, that means we need to have $AA..$.
Then, if we rotate it by 1 bead, we get $.AA.$.
In turn that means our necklace needs to be $AAA.$.
Repeating the argument, we get $AAAA$. (Thinking)

In short, if we start with a first bead of $A$, and if we want the necklace to be unchanged under $r$, the necklace needs to be $AAAA$.
Alternatively, if we start with $B$, the necklace needs to be $BBBB$. (Thinking)

Ah ok... I see... (Thinking)

So, all the necklaces at which all the beads have the same colour, are unchanged under one rotation, $r$, right? (Wondering)
There are $k$ such necklaces, or not? (Wondering) So, all the necklaces at which there are two different colours such that at one position there is one of the two colours, then at the next position it has the other colour and at the next the first that I referred and so on, are unchanged under the rotation by two beads, $r^2$, right? (Wondering)
There are $k^2$ such necklaces, or not? (Wondering) When we continue, all the necklaces at which there are $i$ different colours such that at the first $i$ positions there is a different colour of the $i$ ones, this sequence of coulours is repeted at the rest of the necklace, are unchanged under the rotation by $i$ beads, $r^i$, right? (Wondering)
There are $k^i$ such necklaces, or not? (Wondering)

 

[I like Serena]

So, all the necklaces at which all the beads have the same colour, are unchanged under one rotation, $r$, right? (Wondering)
There are $k$ such necklaces, or not? (Wondering)

Yes. (Nod)

So, all the necklaces at which there are two different colours such that at one position there is one of the two colours, then at the next position it has the other colour and at the next the first that I referred and so on, are unchanged under the rotation by two beads, $r^2$, right? (Wondering)
There are $k^2$ such necklaces, or not? (Wondering)

When $m=4$ we have indeed $k^2$ such necklaces.

However, suppose $m=5$.
We start again with A...
Unchanged under $r^2$ means the third bead must also be A, so we have A.A..
Next is A.A.A, followed by AAA.A, and finally AAAAA. (Worried)

 

[mathmari]

When $m=4$ we have indeed $k^2$ such necklaces.

However, suppose $m=5$.
We start again with A...
Unchanged under $r^2$ means the third bead must also be A, so we have A.A..
Next is A.A.A, followed by AAA.A, and finally AAAAA. (Worried)

So, that what I wrote in post #11 holds when $m$ is even, right?

Suppose $m=7$.
We start again with A...
Unchanged under $r^2$ means the third bead must also be A, so we have A.A...
Next is A.A.A.., followed by A.A.A.A, and finally AAAAAAA.

That means that when $m$ is odd the necklace that is unchanged under $r^2$ has to have all the beads of the same colour, or not? (Wondering)

 

[I like Serena]

Yep. (Nod)

 

[mathmari]

I did some examples and I think that when $m$ is odd the necklace that is unchanged under $r^i$, for all $i$, has to have all the beads of the same colour, or not? (Wondering)

 

[I like Serena]

I did some examples and I think that when $m$ is odd the necklace that is unchanged under $r^i$, for all $i$, has to have all the beads of the same colour, or not? (Wondering)

What about $m=9$ and $r^3$? (Wondering)

 

[mathmari]

What about $m=9$ and $r^3$? (Wondering)

We have the following:

$A..A..A..$

In that case, the necklace shouldn't have all the beads in the same colour so that it stays unchanged under $r^3$.

The necklace is of the form:

$ABCABCABC$

right? (Wondering)

 

[I like Serena]

Yep. (Nod)

 

[mathmari]

Yep. (Nod)

So, only when $m$ is odd and $i$ is even we have that the necklace has to have all the beads of the same colour so that it is unchanged under the rotation $r^i$, or not? (Wondering)

 

[I like Serena]

So, only when $m$ is odd and $i$ is even we have that the necklace has to have all the beads of the same colour so that it is unchanged under the rotation $r^i$, or not? (Wondering)

How about $m=8$ and $i=3$? (Wondering)

 

[mathmari]

How about $m=8$ and $i=3$? (Wondering)

In that case we have $$A..A..A. \rightarrow AAAAAAAA$$ so all beads have to have the same colour. So, when $m$ is even and $i$ is odd or when $m$ is odd and $i$ is even, all the beads have to have the same colour so that the necklace is unchanged under the rotation $r^i$, or not? (Wondering)

 

[I like Serena]

In that case we have $$A..A..A. \rightarrow AAAAAAAA$$ so all beads have to have the same colour. So, when $m$ is even and $i$ is odd or when $m$ is odd and $i$ is even, all the beads have to have the same colour so that the necklace is unchanged under the rotation $r^i$, or not? (Wondering)

How about $m=5$ and $i=3$? (Wondering)

All beads need to have the same color if the rotation cycles through all beads.
That is, if the rotation generates $C_m$.
It's the case if $m$ and $i$ are co-prime. (Thinking)

 

[mathmari]

How about $m=5$ and $i=3$? (Wondering)

In this case we have the following:

$A..A. \rightarrow AAAAA$

All beads need to have the same color if the rotation cycles through all beads.
That is, if the rotation generates $C_m$.
It's the case if $m$ and $i$ are co-prime. (Thinking)

What do you mean by "the rotation cycles through all beads" ? (Wondering)

Is $C_m$ a cycle of length $m$ ? (Wondering)

Why do $m$ and $i$ have to be co-prime? (Wondering)

 

[Deveno]

In this case we have the following:

$A..A. \rightarrow AAAAA$


What do you mean by "the rotation cycles through all beads" ? (Wondering)

Is $C_m$ a cycle of length $m$ ? (Wondering)

Why do $m$ and $i$ have to be co-prime? (Wondering)

If $m$ and $i$ share a common divisor $d$, than a pattern that repeats every $d$ beads will be preserved by a rotation of $i$ places. For example, if you have an eight bead necklace, colored:

$ABABAB$

Then a rotation by two beads still gives you:

$ABABAB$.

I want to add, that the general formula, even for the somewhat simple case of $m$ beads and $k$ colors, is going to be horrendous, as the configuraton space has cardinality $m^k$, which is going to be large unless $m$ and $k$ are very small integers. Counting the colorings preserved for $12$ beads, with just $4$ colors means we have to partition a set of $20,736$ elements, and counting the colorings preserved by an arbitrary rotation, for example, is not going to be a trivial task (classifying them by "types" is somewhat easier-but extending that to the entire configuration space is going to take a little bit of arithmetic).

 

[I like Serena]

In this case we have the following:

$A..A. \rightarrow AAAAA$

What do you mean by "the rotation cycles through all beads" ? (Wondering)

Is $C_m$ a cycle of length $m$ ? (Wondering)

Why do $m$ and $i$ have to be co-prime? (Wondering)

$C_m$ is the cyclic group of $m$ elements.
It's the same as $Z_m$ or $\mathbb Z/m\mathbb Z$.
Any integer that is coprime with $m$ generates $Z_m$. (Nerd)

Consider the necklace to have positions $0, 1, 2, ..., m-1$ in $\mathbb Z/m\mathbb Z$.
Then the rotation $r^i$ on the bead at position $0$ corresponds to adding $i \bmod m$ to it.
So if we have $m=5$ beads, start with bead $0$, and repeatedly apply $r^3$ to it, we get the sequence:
$$0, 3, 1, 4, 2, 0, ... \pmod 5$$
In other words, we pass through all beads. (Thinking)

More generally, as http://mathhelpboards.com/members/deveno/ explained, if $\gcd(m,i)=d$, we won't pass through all beads, but the beads we do reach are at distance $d$ of each other.
That leaves us room to pick $d$ colors.
So with $k$ different colors, there are $k^{\gcd(m,i)}$ necklaces that are unchanged by the rotation $r^i$. (Thinking)

 

[mathmari]

If $m$ and $i$ share a common divisor $d$, than a pattern that repeats every $d$ beads will be preserved by a rotation of $i$ places.

More generally, as http://mathhelpboards.com/members/deveno/ explained, if $\gcd(m,i)=d$, we won't pass through all beads, but the beads we do reach are at distance $d$ of each other.
That leaves us room to pick $d$ colors.
So with $k$ different colors, there are $k^{\gcd(m,i)}$ necklaces that are unchanged by the rotation $r^i$. (Thinking)

(Thinking) (Thinking) I have to rethink about it... So, in total $\sum_{i=1}^mk^{\gcd (m,i)}$ necklaces stay unchanged by the rotation $r^i, 1\leq i\leq m$ ? (Wondering)

 

[I like Serena]

I have to rethink about it... So, in total $\sum_{i=1}^mk^{\gcd (m,i)}$ necklaces stay unchanged by the rotation $r^i, 1\leq i\leq m$ ? (Wondering)

Yes.
Next we can consider what reflections will do.
After that we can apply Burnside's lemma.
Each orbit corresponds to a unique necklace. That is, we consider 2 necklaces equivalent (the same) if there is a dihedral transformation that transforms the one into the other. (Thinking)

 

[mathmari]

Next we can consider what reflections will do.

How can we find the reflections? (Wondering)
Could you give me some hints? (Wondering)

 

[I like Serena]

How can we find the reflections? (Wondering)
Could you give me some hints? (Wondering)

Consider the necklaces of 5 beads.
We begin again with A...
If we flip the necklace upside down along the central vertical line (reflection $s$), we get ...A
To ensure the necklace is unchanged, we need A...A (Thinking)

 

[mathmari]

Consider the necklaces of 5 beads.
We begin again with A...
If we flip the necklace upside down along the central vertical line (reflection $s$), we get ...A
To ensure the necklace is unchanged, we need A...A (Thinking)

The second bead and the last but one should also be of the same colour, right? (Wondering)

 

[I like Serena]

The second bead and the last but one should also be of the same colour, right?

Right.
So we have AB.BA

 

[mathmari]

Right.
So we have AB.BA

So for that reflection there are $k^{\lceil \frac{m}{2}\rceil}$ necklaces that stay unchanged, or not? (Wondering)

 

[I like Serena]

So for that reflection there are $k^{\lceil \frac{m}{2}\rceil}$ necklaces that stay unchanged, or not? (Wondering)

Yeap.
The axis of symmetry always goes through either 0, 1, or 2 beads.
In all those cases we get $\lceil \frac{m}{2}\rceil$ choices for the color. (Nod)

 

[mathmari]

The axis of symmetry always goes through either 0, 1, or 2 beads.

When the number of beads is odd the axis of symmetry goes through $1$ bead and when the number of beads is even the axis of symmetry goes through $2$ beads, right? (Wondering)

When goes the axis of symmetry through $0$ beads? (Wondering)

 

[I like Serena]

When the number of beads is odd the axis of symmetry goes through $1$ bead and when the number of beads is even the axis of symmetry goes through $2$ beads, right? (Wondering)

When goes the axis of symmetry through $0$ beads? (Wondering)

Take a look at $D_6$:
View attachment 5402

The axis of symmetry of $s$ in this picture goes through $2$ beads.
The axis of $rs$ goes through $0$ beads. (Thinking)