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:

    “There is no better proof of a man’s being truly good than his desiring to be constantly under the observation of good men.”
    —François, Duc De La Rochefoucauld (1613–1680)

    “When children feel good about themselves, it’s like a snowball rolling downhill. They are continually able to recognize and integrate new proof of their value as they grow and mature.”
    —Stephanie Martson (20th century)

    “The proof of a poet is that his country absorbs him as affectionately as he has absorbed it.”
    —Walt Whitman (1819–1892)