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:

    “If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
    —Thomas Jefferson (1743–1826)

    “He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”
    —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)