Since I didn't feel confident about the subject as read so far, I've tried to deploy it somehow. This way I can go as far as the OST (Corollary 2), but I am stuck with the proof in Lemma 3, which is necessary to get to Burnside's Lemma (Corollary 3).
Could someone give me a hint how to prove the Lemma 3, please?
Driven by the "prototypical action" on a set, namely a permutation of its elements, we define action of the group $G$ on the set $S$ the map:
\begin{alignat*}{1} G \times S &\longrightarrow& S \\ (g,s)&\longmapsto& gs \end{alignat*}
with the following properties:
- $es=s, \forall s \in S$;
- $g(hs)=(gh)s, \forall g,h \in G, \forall s \in S$.
Given $s,t \in S$, we say:
$$t \stackrel{\cdot}{\sim}s \stackrel{(def.)}{\Longleftrightarrow} \exists g \in G \mid t=gs \tag 1$$
By virtue of action's properties, $\stackrel{\cdot}{\sim}$ turns out to be an equivalence relation on $S$. In fact:
- $s \stackrel{\cdot}{\sim} s$, because $s=es$;
- $t\stackrel{\cdot}{\sim}s \Rightarrow t=gs \Rightarrow g^{-1}t=g^{-1}(gs)=(g^{-1}g)s=es=s \Rightarrow s\stackrel{\cdot}{\sim}t$;
- $(t\stackrel{\cdot}{\sim}s) \wedge (s\stackrel{\cdot}{\sim}r) \Rightarrow (t=gs) \wedge (s=hr) \Rightarrow t=g(hr)=(gh)(r) \Rightarrow t\stackrel{\cdot}{\sim}r$.
Thence, $S$ is partitioned into orbits:
$$\mathcal{O}:=S/\stackrel{\cdot}{\sim}=\lbrace O(s), s \in S\rbrace \tag 2$$
where
$$O(s):=[s]_{\stackrel{\cdot}{\sim}}=\lbrace t \in S \mid t\stackrel{\cdot}{\sim}s\rbrace=\lbrace t \in S \mid t=gs, g \in G \rbrace \tag 3$$
Given $s \in S$, distinct group's elements may "move" $s$ to one same element of $S$, and we say:
$$h\stackrel{s}{\sim}g \stackrel{(def.)}{\Longleftrightarrow} hs=gs \tag 4$$
$\stackrel{s}{\sim}$ is an equivalence relation on $G$; in fact:
- $g\stackrel{s}{\sim}g$, because $gs=gs$;
- $h\stackrel{s}{\sim}g \Rightarrow hs=gs \Rightarrow gs=hs \Rightarrow g\stackrel{s}{\sim}h$;
- $(h\stackrel{s}{\sim}g) \wedge (g\stackrel{s}{\sim}k) \Rightarrow (hs=gs) \wedge (gs=ks) \Rightarrow hs=ks \Rightarrow h\stackrel{s}{\sim}k$.
Thence, given $s \in S$, $G$ is partitioned into stabilizers:
$$\mathcal{S}_s:=G/\stackrel{s}{\sim}=\lbrace \mathcal{Stab}_s(g), g \in G\rbrace \tag 5$$
where
$$\mathcal{Stab}_s(g):=[g]_{\stackrel{s}{\sim}}=\lbrace h \in G \mid h\stackrel{s}{\sim}g\rbrace=\lbrace h \in G \mid hs=gs\rbrace \tag 6$$
Lemma 1. The map:
\begin{alignat*}{1} \chi \colon \mathcal{S}_s &\longrightarrow& O(s) \\ \mathcal{Stab}_s(g) &\longmapsto& \chi(\mathcal{Stab}_s(g)):=gs \tag 7 \end{alignat*}
is well-defined and bijective.
Proof.
- Let $h \in \mathcal{Stab}_s(g)$; then, $\chi(\mathcal{Stab}_s(h))=hs=gs=\chi(\mathcal{Stab}_s(g))$, and $\chi$ is well-defined.
- $\chi(\mathcal{Stab}_s(h))=\chi(\mathcal{Stab}_s(g)) \Rightarrow hs=gs \Rightarrow h \in \mathcal{Stab}_s(g)$; but $h \in \mathcal{Stab}_s(h)$, then $\mathcal{Stab}_s(h)=\mathcal{Stab}_s(g)$, and $\chi$ is 1-1.
- By definition of $O(s)$, $\forall t \in O(s), \exists g \in G$ such that $t=gs=\chi(\mathcal{Stab}_s(g))$, and $\chi$ is onto. $\Box$
Lemma 2. $\forall g,h \in G$, the map:
\begin{alignat*}{1} \xi \colon \mathcal{Stab}_s(g) &\longrightarrow& \mathcal{Stab}_s(h) \\ k &\longmapsto& \xi(k) :=hk^{-1}g \tag 8 \end{alignat*}
is bijective.
Proof. Firstly, $\forall k \in \mathcal{Stab}_s(g)$, it is $\xi(k) \in \mathcal{Stab}_s(h) \Leftrightarrow (hk^{-1}g)s=hs$, and this latter holds because $(hk^{-1}g)s=h(k^{-1}(gs))=h(k^{-1}(ks))=h((k^{-1}k)s)=h(es)=hs$. Besides, $\xi(k)=\xi(u)\Rightarrow k=u$, by group properties, and $\xi$ is 1-1. Finally, $\forall v \in \mathcal{Stab}_s(h)$, $v=\xi(gv^{-1}h)$, and $\xi$ is onto. $\Box$
Corollary 1. (Here $|X|$ stands for the cardinality of $X$.) $\forall g \in G$:
$$|\mathcal{Stab}_s(g)|=|\mathcal{Fix}(s)| \tag 9$$
where:
$$\mathcal{Fix}(s):=\lbrace h \in G \mid hs=s\rbrace \tag {10}$$
Proof. By the Lemma 2, $\forall g \in G, |\mathcal{Stab}_s(g)|=|\mathcal{Stab}_s(e)|$, and $\mathcal{Stab}_s(e)$ is precisely $\mathcal{Fix}(s)$. $\Box$
Corollary 2. (Orbit-Stabilizer Theorem.) If $G$ is finite, then:
$$|\mathcal{Fix}(s)||O(s)|=|G|, \forall s \in S \tag {11}$$
Proof. Given $s \in S$, $G$ is partitioned into $|O(s)|$ subsets (by Lemma 1) of $|\mathcal{Fix}(s)|$ elements each (by Corollary 1). $\Box$
For any $g \in G$, we call:
$$\operatorname{Fix}(g):=\lbrace s \in S \mid gs=s \rbrace \tag {12}$$
(EDIT on the basis of the accepted answer and therein comments.)
Lemma 3. If $G$ and $S$ are finite, then:
$$\sum_{g \in G}|\operatorname{Fix}(g)|=\sum_{s \in S}|\mathcal{Fix}(s)| \tag {13}$$
Proof. By $(10)$ and $(12)$:
$$\lbrace \mathcal{Fix}(s) \times \lbrace s \rbrace, s \in S \rbrace = \lbrace (g,s) \in G \times S \mid gs=s \rbrace = \lbrace \lbrace g \rbrace \times \operatorname{Fix}(g), g \in G \rbrace$$
from which $(13)$ follows for $G$ and $S$ finite. $\Box$
Corollary 3. (Burnside's Lemma.) If $G$ and $S$ are finite, then:
$$|\mathcal{O}|=\frac{1}{|G|}\sum_{g \in G}|\operatorname{Fix}(g)| \tag {14}$$
Proof. By $(2)$ and $(11)$:
\begin{alignat}{1} \sum_{s \in S}|\mathcal{Fix}(s)| &= \sum_{O(s) \in \mathcal{O}}\sum_{t \in O(s)}|\mathcal{Fix}(s)| \\ &= \sum_{O(s) \in \mathcal{O}}|\mathcal{Fix}(s)|\sum_{t \in O(s)}1 \\ &= \sum_{O(s) \in \mathcal{O}}|\mathcal{Fix}(s)||O(s)| \\ &= \sum_{O(s) \in \mathcal{O}}|G| \\ &= |G|\sum_{O(s) \in \mathcal{O}}1 \\ &= |G||\mathcal{O}| \tag {15} \end{alignat}
and $(14)$ follows from the Lemma 3. $\Box$
Lemma 3 is the following observation.
Let $[P]$ be the Iverson bracket of $P$, i.e., it is $1$ if $P$ is true, and $0$ if $P$ is false, where $P$ is a statement.
Then observe that $$|\operatorname{Fix}(g)|=\sum_{s\in S} [gs=s],$$ and that $$|\mathcal{Fix}(s)| = \sum_{g\in G} [gs=s].$$
Thus we have $$\sum_{g\in G}|\operatorname{Fix}(g)|=\sum_{g\in G}\sum_{s\in S} [gs=s] = \sum_{s\in S}|\mathcal{Fix}(s)|$$