Elementary Combinatorial Proofs using group action 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]$.
 A: 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.  
A: 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.$$
A: 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.
