Burnside's Lemma and Stirling Numbers of the First Kind 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.
 A: This  observation is  correct and  we  may use  the Polya  Enumeration
Theorem to evaluate  these two sums. We have by  the definition of the
cycle  index of  the  symmetric group  $Z(S_n)$  which represents  the
unlabeled multiset operator $\mathfrak{M}$ that
$$\sum_{p=1}^n \left[n\atop p\right] u^p
= n! Z(S_n)(u,u,u,\cdots).$$
Recall the ordinary generating function of $Z(S_n)$ which is
$$G(z) = \sum_{n\ge 0} Z(S_n) z^n
= \exp\left(a_1 z + a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} 
+\cdots\right).$$
Now the signed Stirling numbers of the first kind are given by
$$(-1)^{n+p} \left[n\atop p\right].$$
This gives the generating function
$$H(z)
= \exp\left(- a_1(-z) - a_2 \frac{(-z)^2}{2} - a_3 \frac{(-z)^3}{3}
+\cdots\right)
\\ = \exp\left(a_1 z - a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} 
-\cdots\right).$$
This can be shown to be the OGF of the cycle index $Z(P_n)$ of the set
operator $\mathfrak{P}$ and we have
$$H(z) = \sum_{n\ge 0} Z(P_n) z^n.$$
It now follows that
$$\sum_{p=1}^n (-1)^{n+p} \left[n\atop p\right] u^p
= n! Z(P_n)(u,u,u,\cdots).$$
Therefore the quantity being evaluated is
$$n! Z(P_n)(n,n,n,\cdots).$$
This is
$$n! [z^n] 
\exp\left(n\times\left(z-\frac{z^2}{2}+\frac{z^3}{3}
-\cdots\right)\right)
\\ = n! [z^n] \exp(n\log(1+z))
= n! [z^n] (1+z)^n = n!,$$
as claimed.

Similarly we get for the first sum
$$n! Z(S_n)(1,1,1,\cdots)$$
which is
$$n! [z^n] 
\exp\left(z+\frac{z^2}{2}+\frac{z^3}{3}+\cdots\right)
\\ = n! [z^n] \exp\left(\log\frac{1}{1-z}\right)
= n! [z^n] \frac{1}{1-z} = n!,$$
also as claimed.

This last result is a classic formula that can be used to compute many
statistics of random permutations. It represents the labeled species
$$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z})
+ \mathfrak{C}_{=2}(\mathcal{Z})
+ \mathfrak{C}_{=3}(\mathcal{Z})
+ \cdots).$$
