Burnside's Lemma - Proof

Proof

The proof uses the orbit-stabilizer theorem and the fact that X is the disjoint union of the orbits:

\begin{align} \sum_{g \in G}|X^g| &= |\{(g,x)\in G\times X \mid g\cdot x = x\}| = \sum_{x \in X} |G_x| = \sum_{x \in X} \frac{|G|}{|Gx|} \\ &= |G| \sum_{x \in X}\frac{1}{|Gx|} = |G|\sum_{A\in X/G}\sum_{x\in A} \frac{1}{|A|} = |G| \sum_{A\in X/G} 1 \\ &= |G| \cdot |X/G|. \end{align}

Read more about this topic:  Burnside's Lemma

Famous quotes containing the word proof:

    “O, popular applause! what heart of man
    Is proof against thy sweet, seducing charms?”
    —William Cowper (1731–1800)

    “There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
    —Herman Melville (1819–1891)

    “From whichever angle one looks at it, the application of racial theories remains a striking proof of the lowered demands of public opinion upon the purity of critical judgment.”
    —Johan Huizinga (1872–1945)