The Necklace Problem

The Necklace Problem (Background Theory)

The Problem: How many distinct necklaces can be made with a bunch of beads of varying colors if there is no clasp, i.e. rotations and reverse orientations (reflections) are equivalent.

Background Definitions: (largely assembled from Wikipedia information)

An equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i.e., if the relation is written as ~ it holds for all a, b and c in X that

1. (Reflexivity) a ~ a

2. (Symmetry) if a ~ b then b ~ a

3. (Transitivity) if a ~ b and b ~ c then a ~ c

For an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a:

[a] = { x X | x ~ a }

The notion of equivalence classes is useful for constructing sets out of already constructed ones. The set of all equivalence classes in X given an equivalence relation ~ is usually denoted as X / ~ and called the quotient set of X by ~. This operation can be thought of (very informally indeed) as the act of "dividing" the input set by the equivalence relation, hence both the name "quotient", and the notation, which are both reminiscent of division.

In cases where X has some additional structure preserved under ~, the quotient becomes an object of the same type in a natural fashion; the map that sends a to [a] is then an epimorphism.

· Any function f : X → Y defines an equivalence relation on X by x ~ y iff f(x) = f(y). The equivalence class of x is the set of all elements in X which get mapped to f(x), i.e. the class [x] is the inverse image of f(x). This equivalence relation is known as the kernel of f.

A group (G, * ) is a nonempty set G together with a binary operation * : G × G → G, satisfying the group axioms below. "a * b" represents the result of applying the operation * to the ordered pair (a, b) of elements of G. The group axioms are the following:

· Associativity: For all a, b and c in G, (a * b) * c = a * (b * c).

· Identity element: There is an element e in G such that for all a in G, e * a = a * e = a.

· Inverse element: For all a in G, there is an element b in G such that a * b = b * a = e, where e is the identity element from the previous axiom.

You will often also see the axiom

· Closure: For all a and b in G, a * b belongs to G.

Obviously, equivalency classes and groups are closely related:

· Given a group G and a subgroup H, we can define an equivalence relation on G by x ~ y iff xy^-1 H. The equivalence classes are known as right cosets of H in G; one of them is H itself. They all have the same number of elements (or cardinality in the case of an infinite H). If H is a normal subgroup, then the set of all cosets is itself a group in a natural way.

· Every group can be partitioned into equivalence classes called conjugacy classes.

The symmetric group on a set X, denoted by S_X or Sym(X), is the group whose underlying set is the set of all bijective functions from X to X, in which the group operation is that of composition of functions, i.e., two such functions f and g can be composed to yield a new bijective function f o g, defined by (f o g)(x) = f(g(x)) for all x in X. Using this operation, S_X forms a group. The operation f o g is also written as simply fg .

Of particular importance is the case of a finite set X = {1,...,n}, which we write as S_n. The elements of S_n are called permutations; there are n! of them. The group S_n is abelian if and only if n ≤ 2.

Subgroups of S_n are called permutation groups.

A permutation group is a group G whose elements are permutations of a given set M, and whose group operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself); the relationship is often written as (G,M). If M is any finite or infinite set, then the group of all permutations of M is often written as Sym(M).

The application of a permutation group to the elements being permuted is called its group action; it has applications in both the study of symmetries and combinatorics.

The notion of a group action is that every element of the group "acts" like a bijective map (or "symmetry") on some set. In this case, the group is also called a permutation group (especially if the set is finite or not a vector space) or transformation group (especially if the set is a vector space and the group acts like linear transformations of the set). A permutation representation of a group G is a representation of G as a group of permutations of the set (usually if the set is finite), and may be described as a group representation of G by permutation matrices, and is usually considered in the finite-dimensional caseit is the same as a group action of G on an ordered basis of a vector space.

There is a nice collection of examples of these at the Wikipedia site http://en.wikipedia.org/wiki/Group_action.

Orbits and stabilizers

Consider a group G acting on a set X. The orbit of a point x in X is the set of elements of X to which x can be moved by the elements of G. The orbit of x is denoted by Gx:

$Gx = \left\{ g\cdot x \mid g \in G \right\}$

The defining properties of a group guarantee that the set of orbits of X under the action of G form a partition of X. The associated equivalence relation is defined by saying x ~ y iff there exists a g in G with g·x = y. The orbits are then the equivalence classes under this relation; two elements x and y are equivalent iff their orbits are the same, i.e. Gx = Gy.

The set of all orbits of X under the action of G is written as X/G, and is called the quotient of the action; in geometric situations it may be called the orbit space.

If Y is a subset of X, we write GY for the set { g·y : y $\in$ Y and g $\in$ G}. We call the subset Y invariant under G if GY = Y (which is equivalent to GY Y). In that case, G also operates on Y. The subset Y is called fixed under G if g·y = y for all g in G and all y in Y. Every subset that's fixed under G is also invariant under G, but not vice versa.

Every orbit is an invariant subset of X on which G acts transitively. The action of G on X is transitive if and only if all elements are equivalent, meaning that there is only one orbit.

For every x in X, we define the stabilizer subgroup of x (aka the isotropy subroup -- and actually a subroup of G) as the set of all elements in G that fix x:

$G_x = \{g \in G \mid g\cdot x = x\}$

This is a subgroup of G, though typically not a normal one. The action of G on X is free if and only if all stabilizers are trivial. The kernel N of the homomorphism G → Sym(X) is given by the intersection of the stabilizers G_x for all x in X.

Orbits and stabilizers are not unrelated. For a fixed x in X, consider the map from G to X given by g |-> g·x. The image of this map is the orbit of x and the coimage is the set of all left cosets of G_x. The standard quotient theorem of set theory then gives a natural bijection between G/G_x and Gx. Specifically, the bijection is given by hG_x |-> h·x. This result is known as the orbit-stabilizer theorem.

If G and X are finite then the orbit-stabilizer theorem, together with Lagrange's theorem, gives

$|Gx| = [G\,:\,G_x] = |G| / |G_x|$

This result is especially useful since it can be employed for counting arguments.

Note that if two elements x and y belong to the same orbit, then their stabilizer subgroups, G_x and G_y, are isomorphic. More precisely: if y = g·x, then G_y = gG_x g⁻¹.

A result closely related to the orbit-stabilizer theorem is Burnside's lemma:

$\left|X/G\right|=\frac{1}{\left|G\right|}\sum_{g\in G}\left|X^g\right|$

where X^g is the set of points fixed by g. This result is mainly of use when G and X are finite, when it can be interpreted as follows: the number of orbits is equal to the average number of points fixed per group element.