Demostración combinatoria de una identidad numérica de Stirling.

Question

Considere la identidad $$\sum_{k=0}^n (-1)^kk!{n \brace k} = (-1)^n$$ donde ${n\brace k}$ es un número de Stirling del segundo tipo. Esto recuerda ligeramente a la identidad binomial $$\sum_{k=0}^n(-1)^k\binom{n}{k} = 0$$ que esencialmente afirma que el número de subconjuntos pares de un conjunto es igual al número de subconjuntos Impares.

Ahora hay una prueba fácil de la identidad binomial usando diferencias simétricas para biyectar entre subconjuntos pares e Impares. Me pregunto si existe una interpretación combinatoria análoga para los números de Stirling. El término $k!{n\brace k}$ cuenta el número de particiones del conjunto de un $n$ elemento establecido en $k$ las piezas pedidas. ¿Quizás haya algo que relacione las particiones ordenadas de impar con las particiones ordenadas pares?

Como nota añadida, existe una identidad similar $$\sum_{k=1}^n(-1)^k(k-1)!{n\brace k}=0$$ También se agradecería una interpretación combinatoria de ésta.

Answer 1

¿Quizás haya algo que relacione las particiones ordenadas de impar con las particiones ordenadas pares?

Sí que la hay. Intentemos construir una involución $T_n$ , mapeando particiones ordenadas impar de $n$ -elemento puesto en par y viceversa: si la partición tiene parte $\{n\}$ , moverte $n$ en la parte anterior; de lo contrario, mueve $n$ en una nueva parte separada.

Ejemplo: $(\{1,2\},\{\mathbf{5}\},\{3,4\})\leftrightarrow(\{1,2,\mathbf{5}\},\{3,4\})$ .

Esta involución no está definida en particiones de la forma $(\{n\},\ldots)$ pero para estas particiones se puede utilizar la involución anterior $T_{n-1}$ y así sucesivamente.

Ejemplo: $(\{5\},\{4\},\{1,2\},\{\mathbf{3}\})\leftrightarrow(\{5\},\{4\},\{1,2,\mathbf{3}\})$ .

Al final sólo la partición sin par será $(\{n\},\{n-1\},\ldots,\{1\})$ . Así que nuestra involución (definida recursivamente) da una prueba biyectiva de $\sum_{\text{k is even}}k!{n \brace k}=\sum_{\text{k is odd}}k!{n \brace k}\pm1$ (véase. 1 , 2 ).

Actualización. En cuanto a la segunda identidad, la involución $T_n$ ya está definida en todas las particiones ordenadas cíclicamente, por lo que $\sum_{\text{k is even}}(k-1)!{n \brace k}=\sum_{\text{k is odd}}(k-1)!{n \brace k}$ .

---

P.D. No puedo resistirme a añadir que $k!{n \brace k}$ es el número de $(n-k)$ -caras de una dimensión $n$ -politopo convexo, permutoedro (el casco convexo de todos los vectores formado por la permutación de las coordenadas del vector $(0,1,2,\ldots,n)$ ). Así que $\sum(-1)^{n-k}k!{n \brace k}=1$ ya que es la característica de Euler de un politopo convexo.

Answer 2

En aras de la exhaustividad, incluyo un tratamiento mediante funciones generadoras. La función generadora exponencial de los números de Stirling del segundo tipo es $$ G(z, u) = \exp(u(\exp(z)-1))$$ para que $$ {n \brace k} = n! [z^n] \frac{(\exp(z) - 1)^k}{k!}.$$ De ello se desprende que $$\sum_{k=0}^n (-1)^k k! {n \brace k} = n! [z^n] \sum_{k=0}^n (1-\exp(z))^k = n! [z^n] \sum_{k=0}^\infty (1-\exp(z))^k,$$ donde la última igualdad se produce porque la serie para $(1-\exp(z))^k$ comienza en el grado $k.$ Pero esto es sólo $$ n! [z^n] \frac{1}{1-(1-\exp(z))} = n! [z^n] \exp(-z) = (-1)^n,$$ mostrando el resultado.

Answer 3

No son interpretaciones combinatorias, pero son sencillas.

La ecuación que define a Números Stirling del segundo tipo es $$ \sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}\binom{x}{k}k!=x^n\tag{1} $$ Es decir, los números de Stirling del segundo tipo indican cómo escribir monomios como una combinación de factoriales descendentes (o polinomios combinatorios ).

Observando que $\displaystyle\binom{-1}{k}=(-1)^k$ y el ajuste $x=-1$ rinde $$ \begin{align} \sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}(-1)^kk!= \sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}\binom{-1}{k}k!=(-1)^n \end{align} $$

---

Desde $\displaystyle\binom{x}{k}=\binom{x-1}{k-1}\frac{x}{k}$ y $\begin{Bmatrix}n\\0\end{Bmatrix}=0$ for $n\ge1$, we can rewrite $(1)$ as $$ \sum_{k=1}^n\begin{Bmatrix}n\\k\end{Bmatrix}\binom{x-1}{k-1}(k-1)!=x^{n-1}\tag{2} $$ Configurar $x=0$ rinde $$ \sum_{k=1}^n\begin{Bmatrix}n\\k\end{Bmatrix}(-1)^{k-1}(k-1)!=0^{n-1} $$ donde $0^0=1$ para el caso $n=1$ .