# Burnside's Lemma and the inclusion-exclusion principle.

Let $$G=\lbrace g_i,i=1,\dots,|G|\rbrace$$ be a finite group acting on a finite set $$S$$. Denote by $$\mathcal{O}$$ the set of orbits of $$S$$ induced by the action.

Now, by the inclusion-exclusion principle, we get:

\begin{alignat}{1} \left| \bigcup_{i=1}^{|G|}\operatorname{Fix}(g_i)\right| &= \sum_{k=1}^{|G|}(-1)^{k+1}\sum_{1 \le j_1<\dots

Since each $$s \in S$$ is fixed at least by group's unit $$e$$, it is:

$$\left| \bigcup_{i=1}^{|G|}\operatorname{Fix}(g_i)\right|=|S| \tag 2$$

Further, for Burnside's Lemma:

$$\sum_{m=1}^{|G|}|\operatorname{Fix}(g_m)| = |\mathcal{O}||G| \tag 3$$

so that $$(1)$$ can be rewritten as:

$$|\mathcal{O}||G|-|S| = \sum_{k=2}^{|G|}(-1)^k\sum_{1 \le j_1<\dots

For the special case $$G=\operatorname{Sym}(S)$$, equation $$(4)$$ reads ($$n=|S|$$):

$$n[(n-1)!-1] = \sum_{k=2}^{n!}(-1)^k\sum_{1 \le j_1<\dots

Does $$(4)$$ have some interpretation? Can $$(5)$$ be directly verified by deploying RHS multiple intersections in this special case?