1
$\begingroup$

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<j_k \le |G|}\left|\bigcap_{l=1}^{k}\operatorname{Fix}(g_{j_l}) \right| \\ &= \sum_{m=1}^{|G|}|\operatorname{Fix}(g_m)| + \sum_{k=2}^{|G|}(-1)^{k+1}\sum_{1 \le j_1<\dots<j_k \le |G|}\left|\bigcap_{l=1}^{k}\operatorname{Fix}(g_{j_l}) \right| \tag 1 \end{alignat}

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<j_k \le |G|}\left|\bigcap_{l=1}^{k}\operatorname{Fix}(g_{j_l}) \right| \tag 4$$

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<j_k \le n!}\left|\bigcap_{i=1}^{k}\operatorname{Fix}(g_{j_i}) \right| \tag 5$$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.