TITLE: Elementary Combinatorial Proofs using group action
QUESTION [16 upvotes]: 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]$.

REPLY [2 votes]: 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.
{"set_name": "stack_exchange", "score": 16, "question_id": 1212972}