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
*X*^{g}={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*) *|X*^{g}|.

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) |X^{g}|
so we see that |S|=Sum(*g* in *G*) |X^{g}|.

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