Burnside's Lemma and Stirling Numbers of the First Kind

Question

I've seen that $n!=\displaystyle\sum_{p=0}^n s(n, p)n^p$, where $s(n, p)$ are the signed Stirling Numbers of the First Kind, whose absolute values count the number of permutations in $S_n$ which have $p$ cycles in their cycle decomposition. Of course, this means that $n!=\displaystyle\sum_{p=0}^n \lvert s(n, p)\rvert $. So how do the signs and the $n^p$ come in for the second formula? It strongly resembles something that would come from Burnside's Lemma and the Polya Enumeration Theorem, but I'm not exactly sure how those apply, since there are usually not negative numbers in the sum when you use those Theorems.

Answer 1

EDIT: exponential formula vs Burnside.

Answer 2

Consider how $S_n$ acts on the set of colorings of $\{1,\dots, n\}$ in $x$ colors.

The orbit of a coloring corresponds to the unordered set of colors in the coloring, thus the number of orbits, counted directly, is

$$ \binom{x+n-1}{n}=\frac{1}{n!}(x)^n, $$

which is also known as the number of $n$-combinations with repetitions.

On the other hand, due to Burnside lemma, the number of orbits is the average number of fixed points:

$$ \frac{1}{n!} \sum\limits_{k=1}^n |s(n, k)| x^k, $$

as the number of fixed points for a permutation with $k$ cycles is $x^k$. From this, we get

$$ (x)^n = \sum\limits_{k=1}^n |s(n, k)|x^k, $$ which is the property that we needed to show for unsigned Stirling numbers. Then, changing $(x+k)$ to $(x-k)$ in the product fixes the signs for signed Stirling numbers. I'm not sure how to get signed version from the Burnside's lemma directly though...