Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A proof of Burnside's lemma first claims the number of equivalence classes on G, the given set of permutations, $\sigma$'s, to be applied to an object (i.e. a beaded necklace to be colored), is equal to

$\sum_{k\in K}\frac{1}{|O_k|}$. (1)

$k$ is a certain coloring of the object (e.g. a 4-bead necklace with k=bbww means first two are black and last two are white) in the set $K$ of all colorings, and $O_k$ is the orbit set of that $k$.

From here, the proof lets $O_{k_m}=\{k_1, k_2, ...,k_m\}$ for some $k_m$. (2)

$\Rightarrow|O_{k_m}|=m$ ($m$ is the number of 'colors' available; $C=\{$white$, $ black$\}$, $m=2$).

$\Rightarrow O_{k_1}=O_{k_2}=...=O_{k_m}$. (3)

The proof goes on to show that the presented Burnside's Lemma, $\frac{1}{|G|}\sum_{\sigma\in G}|$Inv$(\sigma)|=\sum_{k\in K}\frac{1}{|O_k|}$, where Inv($\sigma$) is the invariant set of $\sigma$.

My questions are about (1),(2),(3):

How was (1) claimed right off the bat? Is there an intuitive reason?

(2) seems to imply that there is a coloring $k_m$ that can become any other coloring via some $\sigma$. Wouldn't this mean that there is only one equivalence class? (3) seems to show this as well. Clearly, there are situations where there is more than one equivalence class..

I don't understand how they are claiming these crucial steps for the proof.

EDIT: Original can be found next to 'download' near the top at Proof is on page 12 of the pdf.

share|cite|improve this question
up vote 0 down vote accepted

Let $|X^g|= \{x \in X \mid g(x) = x \}$ . If you look at $Y:= \{(g,x) \in G \times X \mid g(x) = x \}$ then first $|Y| = \sum_{g \in G} |X^g|$ and $|Y| = \sum_{x \in X} |G_x| = \sum_{x \in X} \frac{|G|}{|G(x)|}$ Because the orbits are a partition of X let $$ X = \bigcup_{i =1}^r X_i = \bigcup_{i=1}^r G(x_i) $$ for representatns $x_i \in X_i$. Then we have $$ |Y| = \sum_{x \in X} \frac{|G|}{|G(x)|} = \sum_{i=1}^r \sum_{x\in X_i} \frac{|G|}{|G(x_i)|} = \sum_{i=1}^r |X_i| \frac{|G|}{|X_i|} = r|G| $$ and thus $$ r|G| = \sum_{g\in G}|X^g|\rightarrow r = \frac 1 {|G|} \sum_{g \in G} |X|^g $$ where $r$ is the number of orbits. I hope this is a bit clearer.

share|cite|improve this answer
Is G(x) the orbit set of x? And is r analog of my m? Sorry, I am pretty new to this stuff.. – James Oct 25 '12 at 19:33
I am not sure about the $m$ eventhough i read the proof. But what he says in (1) is : number of orbits $= r = \sum_{k \in K} \frac 1 {|O_k|}$ but $\frac 1 {|O_k|} = \frac{|G|}{|G_k|}$ so that (1) is $$ \frac{1}{|G|} \sum_{k \in K} |G_k| = \frac 1 {|G|} \sum_{g \in G } |K^g| $$ where $G_k$ the sabilizer is. There you see why these are equivalent. – Epsilon Oct 25 '12 at 21:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.