How Large is your Penis?

Wednesday, September 1, 2010

Burnside's Counting Formula

Let X be a set and G a group. We define "group action" to be a mapping $$G\times X \to X$$ which satisfies two conditions: (i)ex=x where e is the identity element, (ii)(gg')x=g(g'x).

We define the "stabilizer of x" to be the subgroup $$G_x=\{g\in G: gx=x \}$$. We define the "invariant set under g" to be the subset $$X_g=\{x\in X: gx = x \}$$.

We can also define an equivalence relation on X. We say that x~y if and only if y=gx for some g. It is clear that ~ is an equivalence relation. Thus, we can partition X into disjoint subsets so that any two elements in a subset are related under ~. The equivalence class of x, usually denoated by $$[x] = \{ y\in X :y = gx \}$$ will be now denoated by Gx. This is a good notation because we obtain Gx by forming all multiples of x with g where g is in G. We will define the "orbit of x" to be this equivalence class Gx.

There is a standard result in group theory which states that there is a one-to-one correspondence between the elements of Gx and the cosets of $$(G:G_x)$$. The proof of this important result is very simple. Let $$gG_x$$ be a coset of $$G_x$$ in G. We will define a mapping where its image is $$gx$$ (an element of Gx). Of course, we need to prove this mapping is well-defined. Say that $$g_1G_x = g_2G_x$$ then $$g_1^{-1}g_2 \in G_x\implies g^{-1}_1g_2x = x$$ and so we see immediately that $$g_1x=g_2x$$. In the similar manner one can easily show this mapping is one-to-one and obviously onto. Thus, we have established a bijection between these two sets. The important case for us if when the group and the set are both finite.

Theorem: If G is a finite group acting on a finite set X then $$G = (G:G_x)$$.

The proof of this is immediate. We have just rephrased the condition of being equipotent as sets in terms of their cardinalities. This theorem is an important theorem in group theory which is known as the "orbit-stabalizer theorem". It relates the relationship between the orbits and the stabalizers.

What we are after is a combinatorical result known as "Burnside's Counting Formula". Which is stated in the next theorem.

Theorem: If G is a finite group acting on a finite set then the number of orbits of X is given by $$\frac{1}{G}\sum_{g\in G} X_g$$.

Proof: Let m be the number of orbits. Consider the set of solutions to the equation gx=x. Let n be the number of solutions. If we fix g then there are $$X_g$$ solutions. This means $$n=\sum_{g\in G}X_g$$. However, if we fix x then there are $$G_x$$ solutions. This means $$n=\sum_{x\in X}G_x$$. Equating together we have that $$\sum_{g\in G}X_g=\sum_{x\in X}G_x$$. But by the orbit-stabilizer theorem we know that $$G_x=G/Gx$$. Thus, we get $$\frac{1}{G}\sum_{g\in G}X_g=\sum_{x\in X}\frac{1}{Gx}$$. Write X as a disjoint union $$S_1\cup S_2\cup ... \cup S_m$$ where every $$S_j$$ is an orbit class (which results from the partion of the equivalence relation). Observe that $$\sum_{x\in S_j} \frac{1}{Gx} = 1$$. The reason for this is very simple. If $$x,y\in S_j$$ then clearly $$Gx=Gy$$ so that $$Gx$$ is constant on its orbit class $$S_j$$. While at the same time $$Gx = S_j$$ for all $$x\in S_j$$. Therefore, we are summing $$S_j$$ numbers of values $$\frac{1}{S_j}$$, hence the total value is 1. Now by writing $$\sum_{x\in X} \frac{1}{Gx}$$ as $$\sum_j \sum_{x\in S_j} \frac{1}{Gx} = \sum_j 1 = m$$. It follows that m is equal to the desired formula and this completes the proof. Q.E.D.

The relevance of this formula to combinatorics would be demonstrated later.


  1. Is it true that all orbits have the same number of elements? In any event, thanks for all of the math posts they are very helpful.

  2. "Is it true that all orbits have the same number of elements?":

    No, it is not true. Thank you for the correction. I am not sure why I assumed they had the same number of elements. I fixed up the post above. Just be careful, it should contain | | , values for cardinalities of sets. It just does not because this LaTeX program sucks and is unable to post absolute values.