I am teaching MAT 412/512 Introduction to Combinatorics this semester. Earlier in the semester, I introduced the Stirling numbers of the second kind, and I did not find a good opportunity to introduce the Stirling numbers of the first kind until I started introducing permutation groups and group actions to build up to the Pólya enumeration theorem.
To my surprise, the timing is actually perfect for the Stirling numbers of the first kind to get introduced after the Pólya enumeration theorem because of the following combinatorial identity.
Theorem. For every natural number n,
x(x+1)(x+2) \dots (x + n - 1) = \sum_{k=0}^n \left[ n \atop k \right]x^k.
Recall that the (unsigned) Stirling number \left[ n \atop k \right] of the first kind is the number of permutations of \{1, 2, \dots, n\} with exactly k cycles. Certainly one can establish the above combinatorial identity by induction via the recurrence:
\left[ n \atop k \right] = (n-1)\left[ {n-1} \atop k \right] + \left[ {n-1} \atop {k-1} \right].
But the inductive proof buries the combinatorial story behind the identity. While I was preparing for the lectures, I rediscovered a different proof using the Pólya enumeration theorem. Let me record it here.
Proof. We first assume that x is an arbitrary positive integer. We count the number of colorings of n identical balls using x colors. Certainly, pre the Pólya enumeration theorem, the number of such colorings is exactly the number of multisets of size n with elements in \{1, 2, \dots, x\}, which is \binom{x+n-1}{n}. Post the Pólya enumeration theorem, the number of such colorings is given by
\frac{1}{n!}\sum_{g\in S_n}x^{c(g)},
where S_n is the symmetry group on \{1, 2, \dots, n\}, and c(g) denotes the number of cycles in the permutation g. The above expression can be rewritten as
\frac{1}{n!}\sum_{k=0}^n \left[ n \atop k \right]x^k.
Up to this point, the combinatorial identity is established for all positive integers x. If the polynomial on the left hand side is not identical to that on the right hand side, then the identity could only hold for at most n many x‘s, which is a contradiction.[qed]