Elementary Combinatorial Proofs using group action

Question

In trying to prove that the number of spanning trees in $K_5$ is $125$ I adopted the following method:

Let $S$ be the set of all such spanning trees and let $S_5$ act in a natural way on $S$. Now exactly three nonisomorphic spanning trees $T_1=K_{1,4},T_2=P_5,T_3=\text{chair}$ are possible with $\text{Stab}(T_i)=\text{Aut}(T_i)$.

As $|\text{Orbit}(T_i)|=\frac{|S_5|}{|\text{Stab}(T_i)|}$ and as $S$ is a disjoint union of the three orbits so we have: $$|S|=\frac{5!}{4!}+\frac{5!}{2!}+\frac{5!}{2!}=125.$$

This result can be obtained purely by counting arguments as well, but I find the above proof more satisfying. What are some other elementary counting proofs in combinatorics which can be interpreted in terms of group action?

---

Here is another example of the type of results that I am looking for:

The number of ways of choosing $k$ distinct objects out of $n$ where the order matters is $\frac{n!}{(n-k)!}$.

Proof: Suppose $G=S_n$ and $X=\cup_{m=1}^n \{(x_1,\ldots,x_m):x_i\ne x_j\text{ for }i\ne j, x_i\in[n]\}$. The function from $G\times X$ to $X$ defined by $\sigma\cdot (x_1,\ldots,x_m)=(\sigma(x_1),\ldots,\sigma(x_m))$ is clearly a group action.

Let $x=(x_1,\ldots,x_k)\in X$. Then $\mathcal{O}_x$ is precisely the collection of all $k$-tuples from $[n]$ where each coordinate is different. Our proof will be finished if we show that $|\mathcal{O}_x|=\frac{n!}{(n-k)!}$. Note that the permutations which fix $x$ and thereby each $x_i$ are exactly those which permute elements other then $x_1,\ldots,x_k$ and such permutations are precisely $(n-k)!$ in number. So $|G_x|=(n-k)!$. The result now follows by invoking the orbit stabilizer theorem.

A similar result $\tbinom{n}{k}=\frac{n!}{k!(n-k)!}$ can be obtained by letting $X$ to be the set of all $k$-subsets of $[n]$.

Answer 1

There are counting-proof methods for this, but here's the group action proof using Burnside's Lemma:

Suppose we have a $4\times4$ checkerboard with 16 squares. Let $S$ be the set of all colorings with 8 black and 8 white colors. How many different colorings are there?

It is obvious that there are $\binom{16}{8}=12870$ different ways to color the board. To make this interesting, instead suppose that colorings are considered the same if they map to each other using rotations and reflections.

Let $G=\{ e,A,B,C,D,90^\circ,180^\circ,270^\circ\}$ be the group of symmetries where $A$ and $B$ are vertical and horizontal reflections, $C$ and $D$ are diagonal reflections, and $90^\circ,180^\circ,270^\circ$ are the rotations. Then: $$|S^e|=\binom{16}{8}$$ $A$ and $B$ reflect halves, so: $$|S^A|=|S^B|=\binom{8}{4}$$ Since $90^\circ$ and $270^\circ$ project to each quadrant, we get $$|S^{90^\circ}|=|S^{270^\circ}|=\binom{4}{2}$$ Similarly, $180^\circ$ exchanges halves: $$|S^{180^\circ}|=\binom{8}{4}$$ For $C$ and $D$, there are either 0, 2, or 4 black squares along the diagonal. Otherwise, we would reach a contradiction as an odd number of black squares must be split evenly into two halves. Case 1: No black squares on the diagonal. This means there are 4 black squares taking up 6 squares on each half. This gives $\binom{6}{4}$. Case 2: 2 black squares on diagonal. In this case, we have 6 squares left which are split into 3 per half (out of 6 available squares), so we have $\binom{6}{3}$. But there are $\binom{4}{2}$ different ways of arranging the black squares on the diagonal. Thus, for Case 2 we have $\binom{6}{3}\binom{4}{2}$. For Case 3 (4 black squares on diagonal), each side has 6 total squares and 2 black squares, which is $\binom{6}{2}$. Combining the cases, we get: $$|S^C|=|S^D|=\binom{6}{4}+\binom{6}{3}\binom{4}{2}+\binom{6}{2}$$ Applying Burnside's Lemma, $$|S/G|=\frac{1}{|G|}\sum_{g\in G}|S^g|=\frac{1}{8}\left[\binom{16}{8}+3\binom{8}{4}+2\binom{4}{2}+ 2\left[\binom{6}{4}+\binom{6}{3}\binom{4}{2}+\binom{6}{2}\right] \right]$$$$=1674.$$

Answer 2

This argument is due to Golomb.

Let $p$ be a prime, and consider the set of all sequences of length $p$ with elements taken from $\{1, 2, \dots, n\}$. We can view $Z_p$ as acting on these sequences by cyclic rotation (e.g. rotating $12523$ by $2$ yields $23125$). This action partitions the $n^p$ sequences of length $p$ into orbits, including $n$ orbits of size $1$ (the sequences of the form $aa\dots a$, which are fixed by all rotations). The remaining orbits all have size $p$ (since $p$ is prime), and there are $\frac{n^p-n}{p}$ of them.

In particular, $\frac{n^p-n}{p}$ has to be an integer, giving Fermat's Little Theorem.

Answer 3

The scope of potential answers to this question is truly vast. I suggest this MSE Meta Link as an entry point for additional exploration.

By way of enrichment I would like to present another proof that choosing $q$ objects from $m$ distinct objects where the order matters is $$\frac{m!}{(m-q)!}$$ using the Polya Enumeration Theorem (PET). I think this is a pretty example where we see advanced mechanics prove a very simple combinatorial statement.

Using PET we have that the number of choices where order matters is given by $$q! \times \left.Z(P_q)\left(\sum_{p=1}^m X_p\right) \right|_{X_1=X_2=\cdots=1}$$

where $Z(P_q) = Z(A_q)-Z(S_q)$ is the difference between the cycle index of the alternating group and the cycle index of the symmetric group. This cycle index is known in species theory as the set operator $\mathfrak{P}_{=q}.$

Recall the recurrence by Lovasz for the cycle index $Z(P_q)$ of the set operator $\mathfrak{P}_{=q}$ on $q$ slots, which is $$Z(P_q) = \frac{1}{q} \sum_{l=1}^q (-1)^{l-1} a_l Z(P_{q-l}) \quad\text{where}\quad Z(P_0) = 1.$$ This recurrence lets us calculate the cycle index $Z(P_q)$ very easily. In particular we can use it to compute the OGF of $Z(P_q)$ which is $$\sum_{q\ge 0} Z(P_q) z^q = \exp\left(a_1 z - a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} -\cdots\right).$$

This implies that $$\sum_{q\ge 0} Z(P_q)\left(\sum_{p=1}^m X_p\right) z^q \\ = \exp\left(z \sum_{p=1}^m X_p - \frac{z^2}{2} \sum_{p=1}^m X_p^2 + \frac{z^3}{3} \sum_{p=1}^m X_p^3 +\cdots\right).$$

and in particular $$\left.\sum_{q\ge 0} Z(P_q)\left(\sum_{p=1}^m X_p\right) z^q \right|_{X_1=X_2=\cdots =1} = \exp\left(m z - m \frac{z^2}{2} + m \frac{z^3}{3} - \cdots\right).$$

This is $$\exp\left(m\log(1+z)\right) = (1+z)^m.$$

Note however that $$q! \times [z^q] (1+z)^m = q! \times {m\choose q} = \frac{m!}{(m-q)!}$$ thus proving the claim.

I deliberately chose this example for the contrast between the simplicity of the result being proved and the complexity of the machinery that is used.