4
$\begingroup$

I ran into a problem in real life that I'm pretty sure has a representation in group theory, but I don't know how.

Suppose you flip a coin four times. The 16 outcomes are:

HHHH
HHHT
...
TTTT

First of all, if you have a finite set S (in this case S={H, T}), what do you call the set of all sequences of length N where each of the N positions is chosen from S?

Given that set, I'm trying to count the number of distinct outcomes if you consider cycles; that is, the identity of a sequence can shift, so that (HHHT) is the same as (HHTH) (everything shifts to the left, and the left-most value shifts to the right-most place).

I believe it should be possible to represent an outcome as an element of a finite group, and the factorizations in that group would give the distinct elements modulo the shift, but I'm not sure where to begin.

This also reminds me of permutation groups, but is different enough that I'm not sure how to use that either.

$\endgroup$
4
$\begingroup$

First of all, if you have a finite set S (in this case S={H, T}), what do you call the set of all sequences of length N where each of the N positions is chosen from S?

There are lots of names for this. First you can just call it $S^N$, which is equivalently the cartesian product $S \times S \times \dots \times S$ of $N$ copies of $S$ or the set of functions $N \to S$. If you have a more combinatorial or computer-science bent you might call it the set of words or strings of length $N$ on the alphabet $S$.

Given that set, I'm trying to count the number of distinct outcomes if you consider cycles

Group theory is involved in this problem, but not the way you suggest. You have a finite set, here $S^N$, which is being acted on by a finite group, here the cyclic group $C_N$ of order $N$, and you want to count the number of orbits of this group action. In this particular case these orbits are sometimes called necklaces.

A general tool for doing this is Burnside's lemma, which tells you that if you have a finite group $G$ acting on a finite set $X$ then the number of orbits is

$$\frac{1}{|G|} \sum_{g \in G} |X^g|$$

where $X^g$ denotes the set of all fixed points of $g$ (elements of $X$ such that $gx = x$) and $|X^g|$ denotes the number of such fixed points.

This particular problem is a nice exercise in using Burnside's lemma; it proves the formula given in the Wikipedia article on necklaces, and a slight generalization of it proves a formula I call the baby Polya enumeration theorem.

$\endgroup$
1
  • $\begingroup$ Wow. This sounds very helpful, but it's going to take me a while to digest. Thank you! $\endgroup$ – Joshua Frank Nov 5 '14 at 21:43

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.