1

Consider the question of making necklaces by arranging n distinguishable beads on a string. Assume that once all $n$ beads are placed on the string its ends are carefully knotted so the knot cannot be seen and the beads are equally spaced on the string. Regard two necklaces are equivalent if when both are placed on the table. A person can pick up one of the necklaces, move it around in space, and put it back down so that it exactly matches other necklaces.

Describe this as an equivalence relation on some set. What size blocks of necklaces occur? How many non equivalent necklaces can be constructed using $n$ distinguishable beads?

Verify explicitly that your relationship of equivalent necklaces is reflexive, symmetric, and transitive, and so is an equivalence relation.

equivalence relations is much easier for me when they are written in notations. I tried to relate to the symmetric group $S_n$. For example, when $n=3$ there are $n!$ elements in that group, non equivalent elements are $(1,2),(13),(23)$ right?

user102239
  • 83
  • I suspect the main difficulty here is defining exactly what the relation is, not verifying that it is an equivalence relation. I would define a necklace as an $n$-tuple, and say that two necklaces are equivalent if one is mapped to the other under the action of the dihedral group. In any case, the dihedral group is going to be involved somehow. – Jack M Oct 30 '13 at 22:49

1 Answers1

0

You need to think about what group of symmetries is relevant to the geometry of the necklace. The equally spaced beads on a circular string will make up a regular n-gon, and you will be able to rotate and flip it in space before you set it back down. This corresponds to the dihedral group of $2n$ elements, $D_n$, acting on some given necklace. Now try to set up your equivalence relation in terms of this group action using the set of all possible necklaces of $n$ distinct beads.

Once you have the equivalence relation worked out and verified you can use the group action to help count the distinct classes of necklaces.

Ryan Vitale
  • 1,890