1
$\begingroup$

Here's an example of what I mean by permutations in a closed loop:

A necklace is to be made by threading four identical black beads and four identical white beads onto a string which is closed into a loop. How many different patterns can be made?

What I tried to do to solve this problem was: $4\times 3\times 2\times 1$ (permutations of black beads) multiply with $4\times 3\times 2\times 1$ (permutations of white beads)

However, I discovered that because these beads are in a closed loop (if you visualize this) so...

(W = white beads B = Black beads) WWWBWBBB will be the same as WWWBBBWB or WWWWBBBB = WWWBBBBW

I know I can count all of these by myself (which I did, there are 8 patterns in total), but is there a algebraic way to tackle this sort of problem?

$\endgroup$
1
  • $\begingroup$ Wait if the beads are identical, then why does the permutation of the black/white beads matter? Should it not be simply $8 \choose 4$ ways? Why are you multiplying the permutations? $\endgroup$ – Aarony Jamesys Jul 1 '20 at 5:39
1
$\begingroup$

Yes this is called the Burnside Lemma see :

How to use burnside lemma?

To use this you need a little group theory. Basically you have the set of all possible necklaces (without identifying those that are the same up to rotation). Then identifying necklaces if they are the same up to cyclic permutation is the same as making a cyclic group acting on your set of necklaces :

Two necklaces being the same "up to cyclic permutation" are said to be in the same orbit modulo the group acting. This divides the set of necklaces into orbits. The "patterns" you are referring to is exactly one orbit.

Finally Burnside's lemma is exactly giving a formula for the number of orbits. I will let you see the details in the link or wiki page or just google Burnside's lemma.

$\endgroup$
0
$\begingroup$

Here is a little example of how to use Burnside's Lemma on this problem(I had this problem as well).

There are $16$ possible symmetry groups for an $8$-sided geometrical shape, or also known as an octagon. These include $8$ rotational symmetry groups and $8$ reflection symmetry groups.

Here is an example of the symmetry groups of a square.

A square example from Wikipedia

An orbit of any permutation $x$ is simply all of the possible permutations after applying the symmetry groups. Your question, therefore, can simply be converted to counting the number of orbits.

Using Burnside's lemma , we know we can simply take the average of fixed points for every element in the symmetry group.

For the id, all possible arrangements are fixed, hence we have $8 \choose 4 $ $=70$

  • Rotation of $(1, 7)$ units, we see that all beads must have the same color, hence it is impossible.

  • Rotations of $(2,6)$, we have $2$ $4$-beads groups that have same color, leaving $2$ possibilities.

  • Rotations of $(3,5)$, gives $2$ $3$-beads groups with same colour and a $2$-bead group with same color. Impossible.

  • Rotations of $4$ gives $4$ same-color pairs, leaving $4 \choose 2$ $=6$ ways.

  • Reflection with no fixed points creates $4$ same-color pairs, leaving $6$ ways.

  • Reflexion with fixed points leaves $3$ same-color pairs, giving us $3 \choose 2$$\cdot2=6$ ways

In total, we have our answer as: $\frac{70\cdot1+2\cdot2+6+6\cdot4+6\cdot4}{16}=\frac{128}{16}=8$

$\endgroup$

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.