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.