In general, we have a finite group $G$ [[Group action|acting]] on a finite set $X$ and we want to know $\#(X/G)$, the number of distinct orbits in $X$ under the action of $G$. For $x\in X$, the orbit of $x$ is given by $\text{Orb}_{G}(x) = \{ g*x \mid g\in G \}$, where $*$ denotes the group action, and the *stabiliser* of $x$ is given by $\text{Stab}_{G}(x) = \{ g \in G \mid g*x = x \}$. Recall the *[[Orbit-Stabilizer Theorem|orbit-stabiliser theorem]]* which asserts that $\#\text{Orb}_{G}(x)\cdot \#\text{Stab}_{G}(x) = G$. This can be seen as follows. The multiplicity of $x$ in the multiset of elements $g*x$, $g\in G$, is exactly $\#\text{Stab}_{G}(x)$. Moreover, all elements of this multiset have the same multiplicity since $h*(g*x)=(hg)*x$, $g,h\in G$, gives a natural bijection between $\text{Stab}_{G}(x)$ and $\text{Stab}_{G}(g*x)$. Since the cardinality of this multiset is $\#G$ we have indeed that $\#\text{Orb}_{G}(x)\cdot \#\text{Stab}_{G}(x) = \#G$. Furthermore, the size of union of the $\#(X\text{/}G)$ disjoint multisets is just $\#G \cdot \#(X\text{/}G)$ and is the same as the sum of the multiplicities of the elements of $X$ so $\begin{align} \#G \cdot \#(X\text{/}G) &= \sum_{x\in X} \sum_{\substack{g \in G \\ g*x = x}} 1 \\ &= \sum_{g\in G} \sum_{\substack{x\in X \\ g*x = x}} 1 \\ \end{align}$giving the following formula for $\#(X/G)$. > [!NOTE] Lemma > Let $G$ be a finite group acting on a finite set $X$ and $X/G$ denote the set of orbits in $X$ under the action of $G$. Then $\# (X \text{/} G) = \frac{1}{\# G} \sum_{g\in G} \#\text{Fix}(g)$where $\text{Fix}(g)=\{ x\in X \mid g*x=x \}$, the set of elements in $X$ fixed by $g$. Most textbook applications of Burnside’s lemma involve problems like colouring the vertices and edges of polygons or the vertices and faces of polyhedra. This is because the orbits in these cases clearly correspond to the objects we aim to count. However, this relation can be more complex like in the following example. We revisit the problem of enumerating subsets of $⟦2025⟧$ whose sum is divisible $5$. Consider the following permutation of $⟦2025⟧$: $\rho := \begin{pmatrix}1& 2 & \dots & 5 \end{pmatrix}\begin{pmatrix}6 & 7 & \dots & 10\end{pmatrix}\cdots \begin{pmatrix}2020 &\dots & 2025\end{pmatrix}.$Let $G$ be the cyclic group generated by $\rho$ which notably has order $5$. Naturally, $G$ acts on $2^{⟦2025⟧}$, the set of subsets of $⟦2025⟧$, by $\rho^{k}* S = \{ \rho^{k}(s) \mid s\in S \}, \quad S\in 2^{⟦2025⟧}, k\in \mathbb{Z}.$For example, here are some orbits in $2^{⟦2025⟧}$ under the action of $G$ $\left\{ \begin{array}{c} \\ \{ 1,2,3,4,5 \} \\ \ \end{array} \right \}, \quad \left\{ \begin{array}{c} \{ 1 \}, \\ \{ 2 \}, \\ \{ 3 \}, \\\{ 4 \}, \\ \{ 5 \} \end{array} \right \}, \quad \left\{ \begin{array}{c} \{ 1,2,3,4,10 \}, \\ \{ 2,3,4,5,6 \}, \\ \{ 3,4,5, 1,7 \}, \\\{ 4, 5, 1,2, 8 \}, \\ \{ 5, 1, 2, 3, 9 \} \end{array} \right \}. $By definition, $\rho$ fixes the $405$ subsets $\{ 1,2,3,4,5 \}, \{ 6,7,8,9,10 \}, \dots, \{ 2020, \dots, 2025 \}$, as well as their unions, of which there are $2^{405}$. Notably, all such subsets have sums divisible by $5$. Any other subset must have an orbit of size $5$ since it doesn't fully contain at least one of the cycles in $\rho$ and this property remains true after each application of $\rho$. For subsets $S$ that are not fixed by $\rho$, applying $\rho^k$ to $S$ increases the sum, modulo $5$, by $k\cdot\#S$. This leads to two cases: - If $\#S\equiv 0 \mod{5}$ then all five sets in $\operatorname{Orb}_{G}(S)$ have the sum modulo $5$. Note that there are equally many such orbits for each congruence class modulo $5$ since we can permute as follows: apply $\begin{pmatrix}i & i+1 &\cdots & i+4\end{pmatrix}$ to $S$ where $i$ is the least element of $S$. For example, $\{ 1,2,3,4,10 \}\mapsto \{ 2,3,4,5,10 \} \mapsto \{ 3,4,5,1,10 \} \mapsto \{ 4,5,1,2,10 \}\mapsto \{ 5,1,2,3,10 \}$. After each permutation, we add a non-multiple of $5$ to the sum so we get representatives that have distinct sums modulo $5$. - If $\# S \not \equiv 0 \mod{5}$ then again the first five multiples of $\#S$ are distinct modulo $5$ which means that exactly one set in this orbit will have sum divisible by $5$. Like this, we see that there are $\# (2^{⟦2025⟧}\text{/}G)$ many subsets of $⟦2025⟧$ whose sum is divisible $5$. Burnside's lemma yields $\# (2^{⟦2025⟧}\text{/}G) = \frac{1}{5}(2^{2025}+4\cdot 2^{405})$since $\operatorname{Fix}(\text{Id})= 2^{⟦2025⟧}$; $S\in \operatorname{Fix}(\rho)$ implies $S\in \operatorname{Fix}(\rho^2)$; like we argued earlier $S \not \in \text{Fix}(\rho)$ implies $S \not \in \text{Fix}(\rho^2)$ so $\operatorname{Fix}(\rho)=\operatorname{Fix}(\rho^{2})=\operatorname{Fix}(\rho^{3})=\operatorname{Fix}(\rho^{4})$. # References ^[1] Bogart, K. P. (1991). An Obvious Proof of Burnside’s Lemma. _The American Mathematical Monthly_, _98_(10), 927–928. https://doi.org/10.1080/00029890.1991.12000812.