display | more...
Read the group acting on a set writeup first.

Suppose that we have a finite group G acting on a finite set X. The formula of the title says that the number of orbits for the action is equal to the average number of fixed points for a group element. Let's give some more detail.

If g is an element of the group then Xg={xin X such that gx=x} is the set of points in X that are fixed by g. Here is the formula of the title.

Proposition The number of orbits is (1/|G|) Sum(g in G) |Xg|.

Before we prove the formula we need a lemma about orbits and stabilisers. If x in X it has stabiliser
Stab(x)={g in G : gx=x} and orbit O(x).

Lemma |G|=|Stab(x)|.|O(x)|

Proof of the lemma. Define a function f:G --> O(x) by f(g)=gx. Then it is easy to see that f(g)=f(h) for some g,h in G iff h is in the same coset of Stab(x) in G. Also, f is clearly surjective. Thus f induces a bijection G/Stab(x)--> O(x). and the result follows by counting the elements on both sides and Lagrange's theorem.

Back to the proof of the formula, which is quite easy. Consider the set S of all the pairs (g,x) in GxX such that gx=x. We will count the number of elements in S by two different methods.

Firstly, start off we an orbit of the group, say with s elements. Now each element x in the orbit is fixed by the elements in its stabiliser. The orbit-stabiliser lemma tells us that this stabiliser has |G|/s elements. It follows that each orbit of the action will give us |G| pairs (g,x) with gx=x. Thus we see that |S|=|G|.number of orbits.

On the other hand, for each g in G the number of (g,x) with gx=x is (by definition) |Xg| so we see that |S|=Sum(g in G) |Xg|.

Put these two different ways to count the number of elements of S together and we get the result.

Log in or register to write something here or to contact authors.