| 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.
| 
