# proof of counting theorem

Let $N$ be the cardinality of the set of all the couples $(g,x)$ such that $g\cdot x=x$. For each $g\in G$, there exist $\operatorname{stab}_{g}(X)$ couples with $g$ as the first element, while for each $x$, there are $|G_{x}|$ couples with $x$ as the second element. Hence the following equality holds:

 $N=\sum_{g\in G}\operatorname{stab}_{g}(X)=\sum_{x\in X}|G_{x}|.$

From the orbit-stabilizer theorem it follows that:

 $N=|G|\sum_{x\in X}\frac{1}{|G(x)|}.$

Since all the $x$ belonging to the same orbit $G(x)$ contribute with

 $|G(x)|\frac{1}{|G(x)|}=1$

in the sum, then $\sum_{x\in X}1/|G(x)|$ precisely equals the number of distinct orbits $s$. We have therefore

 $\sum_{g\in G}\operatorname{stab}_{g}(X)=|G|s,$

which proves the theorem.

Title proof of counting theorem ProofOfCountingTheorem 2013-03-22 12:47:07 2013-03-22 12:47:07 n3o (216) n3o (216) 5 n3o (216) Proof msc 20M30