¿Cómo demostrar la igualdad $\sum_{j=0}^n (x)^j (-1)^{n-j} \left\{{n \atop j}\right\} = x^n$?

Question

¿Cómo probar $$\sum_{j=0}^n (x)^j (-1)^{n-j} \left\{{n \atop j}\right\} = x^n,$ $ donde $(x)^j=x(x+1)...x(x+j-1)$ y $\left\{{n \atop j}\right\}$ son un número de Stirling de segunda especie?

Answer 1

Para quitar el $(-1)^{n-j}$ término que sustituya $x$ $-x$ y probar

$$x^n = \sum_{j=0}^n \left\{ { n \atop j } \right\} (x)_j , \quad (1)$$

donde $(x)_j = x(x-1)(x-2) \cdots (x-j+1)$ $(x)_0 = 1.$

Procedemos por inducción. Tenga en cuenta que $(1)$ es cierto para $n=0$, por lo que tomamos $n>0$ y asumen $(1)$ es cierto para $n-1.$

$$\begin{align*} x^n &= x \cdot x^{n-1} \\ &= x \sum_{j=0}^{n-1} \left\{ { n-1 \atop j } \right\} (x)_j \\ &= \sum_{j=0}^{n-1} \left\{ { n-1 \atop j } \right\} (x)_j (x-j + j) \\ &= \sum_{j=0}^{n-1} \left\{ { n-1 \atop j } \right\} (x)_{j+1} + \sum_{j=0}^{n-1} j \left\{ { n-1 \atop j } \right\} (x)_j \\ &= \sum_{j=1}^n \left\{ { n-1 \atop j-1 } \right\} (x)_j + \sum_{j=0}^{n-1} j \left\{ { n-1 \atop j } \right\} (x)_j \\ &= \sum_{j=0}^n \left\{ { n \atop j } \right\} (x)_j. \end{align*}$$

La última igualdad se sigue de la recurrencia de la relación de los números de Stirling del segundo tipo:

$$ \left\{ { n \cima j } \right\} = \left\{ { n-1 \la cima j-1 } \right\} + j \left\{ { n-1 \la cima j } \right\}.$$

Answer 2

El uso de la definición! (Nota podemos demostrar que la ecuación (1) que aparece en Derek respuesta).

Los números de Stirling, $\displaystyle \left\{ { n \atop k } \right\}$ el número de formas de partición de $n$ elementos en $k$ no vacía de subconjuntos:

Deje $\displaystyle x$ ser cualquier entero positivo $\displaystyle \gt n$.

Que nos permiten contar el número de maneras de elegir un $\displaystyle n$-tupla $\displaystyle (a_1, a_2, \dots, a_n)$, mediante la selección de las $\displaystyle a_i$ $\{1,2, \dots, x\}$ con reemplazo.

El total de posibilidades es $\displaystyle x^n$.

Ahora el recuento de las mismas, contando tuplas con exactamente $\displaystyle j$ distintos colores, y sumando variación $\displaystyle j$$\displaystyle 0$$\displaystyle n$.

Ya que la identidad es un polinomio en a $\displaystyle x$, y se satisface a través de un número infinito de números enteros $\displaystyle x$, esto es cierto incluso si $\displaystyle x$ es algo complejo.

Answer 3

Hay una simple, pero no es muy conocida fórmula en la fila sumas de dinero para el número de triángulos que se pueden aplicar aquí. Yo creo que es debido a Neuwirth. Supongamos que tenemos un triángulo de números de $R(n,k)$ $R(0,0) = 1$ e,$n \geq 1$, la satisfacción de $$R(n,k) = (\alpha (n-1) + \beta k + \gamma) R(n-1,k) + (\alpha' (n-1) + \beta' (k-1) + \gamma') R(n-1,k-1).$$ Hay varios interesantes número de triángulos que son casos especiales, tales como los coeficientes binomiales y los dos tipos de números de Stirling.

De todos modos, la fórmula es que el si $\beta + \beta' = 0$ $$\sum_{k=0}^n R(n,k) = \prod_{i=0}^{n-1} \left((\alpha + \alpha')i + \gamma + \gamma'\right).$$

Es fácil comprobar que $R(n,k) = \left\{ { n \atop k } \right\} x^{\underline{k}}$ satisface la anterior recurrencia con $\beta = 1, \beta' = -1, \gamma' = x$ y todos los demás parámetros $0$. Así, la fila de la fórmula de la suma de los rendimientos de Derek reformulación del problema (Eq. (1)):

$$\sum_{k=0}^n \left\{ { n \atop k } \right\} x^{\underline{k}} = \prod_{i=0}^{n-1} x = x^n.$$

Answer 4

Los números de Stirling del segundo tipo representan el marcado de la combinatoria de las especies $$\mathcal{Q} = \mathfrak{P}(\mathcal{U}\;\mathfrak{P}_{\ge 1}(\mathcal{Z})).$$ Esto implica inmediatamente que la bivariante de generación de la función de estos números es $$Q(z,u) = \exp(u(\exp(z)-1)).$$

Por lo tanto, tenemos $${n\brace j} = n! [z^n] [u^j] \exp(u(\exp(z)-1)).$$ Esto le da la siguiente expresión para la suma: $$ \sum_{j=0}^n x^{(j)} (-1)^{n-j} {n\llave j} = (-1)^n n! [z^n] \sum_{j=0}^n (-1)^j x^{(j)} [u^j] \exp(u(\exp(z)-1)) \\= (-1)^n n! [z^n] \sum_{j=0}^n (-1)^j x^{(j)} \frac{(\exp(z)-1)^j}{j!} = (-1)^n n! [z^n] \sum_{j=0}^n (-1)^j {x+j-1\elegir j} (\exp(z)-1)^j.$$ Ahora observe que podemos extender la suma de los infinitos términos desde $(\exp(z)-1)^j$ produce términos en $z$ con exponente mayor que $n$ al $j>n$ que no contribuyen a $[z^n]$, dando $$(-1)^n n! [z^n] \sum_{j=0}^\infty (-1)^j {x+j-1\choose j} (\exp(z)-1)^j.$$ Utilizando el binomio de Newton esto se convierte en $$(-1)^n n! [z^n] \frac{1}{(1-(1-\exp(z)))^x} = (-1)^n n! [z^n] \exp(-zx) = (-1)^n n! (-1)^n \frac{x^n}{n!} = x^n, \quad\text{QED.}.$$