3
$\begingroup$

Using Burnside's Lemma find out:

How many different necklaces having $5$ beads can be formed using $3$ different kinds of beads, if we discount :

(a) Both flips and rotations?

(b) Rotations only?

(c) Flips only?

I don't know how to apply this lemma. Have you some solved exercises?

thanks :)

$\endgroup$
4
  • 1
    $\begingroup$ (c) is a bit ambiguous - any rotation is a composition of two flips, so does it mean flips across a given, fixed axis? $\endgroup$
    – anon
    Commented Jan 4, 2013 at 20:31
  • 1
    $\begingroup$ Related questions on our site include at least this (for a Wikipedia link and an example), this for a basic example, and this for some gory details. I vaguely recall that joriki has done an even trickier case, but couldn't find it now. $\endgroup$ Commented Jan 4, 2013 at 20:43
  • $\begingroup$ @Jyrki: Do you mean this question? $\endgroup$
    – joriki
    Commented Feb 3, 2013 at 13:04
  • $\begingroup$ @joriki: Yes!!! $\endgroup$ Commented Feb 3, 2013 at 13:05

1 Answer 1

4
$\begingroup$

First, figure out what the symmetry group $G$ is for each part. For instance, for part (b) we are working with rotations - five of them - so we can say that $G\cong C_5$, the cyclic group of order $5$.

Then, for each element $g\in G$, figure out how many fixed points it has - i.e. the number of configurations which it preserves. Call each value $|X^g|$, or $\mathrm{Fix}(g)$.

Finally, tally these values together, and average i.e. divide out by the number of elements $|G|$.

As an example, with part (b) (the easiest), every nontrivial element $g\in G$ generates the whole group, so we know that if a necklace is fixed by $g$, then each bead must be the same color as every other bead. (Label the beads as numbers $1$-$5$ in order, then observe that $1,g1,g^21,\cdots$ lists out all of the numbers, so each bead must have the same color.) The number of necklaces with each bead the same color is equal to the number of colors, three, and the number of nontrivial elements of $G$ is four. Every necklace is fixed by the trivial element $e\in G$, and there are $3^5$ possible necklaces, so

$$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|=\frac{3^5+4\cdot3}{5}=51$$

is the number of necklaces modulo rotations.

$\endgroup$

You must log in to answer this question.

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