He visto que $n!=\displaystyle\sum_{p=0}^n s(n, p)n^p$ , donde $s(n, p)$ son los Números Stirling de Primera Clase con signo, cuyos valores absolutos cuentan el número de permutaciones en $S_n$ que tienen $p$ en su descomposición cíclica. Por supuesto, esto significa que $n!=\displaystyle\sum_{p=0}^n \lvert s(n, p)\rvert $ . Entonces, ¿cómo los signos y la $n^p$ ¿entrar en la segunda fórmula? Se parece mucho a algo que vendría del Lemma de Burnside y del Teorema de Enumeración de Polya, pero no estoy exactamente seguro de cómo se aplican, ya que normalmente no hay números negativos en la suma cuando se usan esos Teoremas.
Respuesta
¿Demasiados anuncios?
Esta observación es correcta y podemos utilizar el Teorema de Enumeración de Polya para evaluar estas dos sumas. Tenemos por la definición del índice de ciclo del grupo simétrico $Z(S_n)$ que representa el operador operador de conjuntos múltiples no etiquetados $\mathfrak{M}$ que
$$\sum_{p=1}^n \left[n\atop p\right] u^p = n! Z(S_n)(u,u,u,\cdots).$$
Recordemos la función generadora ordinaria de $Z(S_n)$ que es
$$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).$$
Ahora los números de Stirling con signo del primer tipo vienen dados por $$(-1)^{n+p} \left[n\atop p\right].$$
Esto da la función generadora $$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).$$
Se puede demostrar que es el OGF del índice del ciclo $Z(P_n)$ del conjunto operador $\mathfrak{P}$ y tenemos
$$H(z) = \sum_{n\ge 0} Z(P_n) z^n.$$
Ahora se deduce que $$\sum_{p=1}^n (-1)^{n+p} \left[n\atop p\right] u^p = n! Z(P_n)(u,u,u,\cdots).$$
Por lo tanto, la cantidad que se evalúa es $$n! Z(P_n)(n,n,n,\cdots).$$
Esto es $$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!,$$
como se ha reclamado.
Del mismo modo, obtenemos para la primera suma $$n! Z(S_n)(1,1,1,\cdots)$$
que es $$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!,$$
también como se ha reclamado.
Este último resultado es una fórmula clásica que puede utilizarse para calcular muchas estadísticas de permutaciones aleatorias. Representa la especie etiquetada
$$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z}) + \mathfrak{C}_{=2}(\mathcal{Z}) + \mathfrak{C}_{=3}(\mathcal{Z}) + \cdots).$$
