La generación de la función con los números de Stirling del segundo tipo

Question

Es muy fácil demostrar que:

$$\sum_k \left\{k\atop n\right\}z^k=\frac{z^n}{(1-z)(1-2z)...(1-nz)}$$

Pero la generación de esta función se ve muy bonita, así que mi pregunta es: ¿esta identidad tiene algunas simples combinatoria interpretación?

Answer 1

Sí, esta ecuación tiene una combinatoria de interpretación.

El número de $\left\{k\atop n\right\}$ cuenta el número de particiones de la linealmente conjunto ordenado $\mathbf k=\{1, \dots, k\}$ a $n$ no vacía de subconjuntos. Vamos a ver cómo uno puede pensar de una partición. A continuación, puedes ver la partición de $\mathbf{15}$ a $4$ no vacía de subconjuntos (el orden lineal que va de izquierda a derecha).

Los datos de esta partición es equivalente a los siguientes datos:

Aquí, una línea vertical que se inserta justo antes de un nuevo color se encuentra cuando va de izquierda a derecha. Los colores fueron ordenados por su orden de aparición:

$$\text{Red}<\text{Blue}<\text{Green}<\text{Pink}$$

y fueron asignados los números de $0,1,2,3$ respectivamente. Ahora, la observación de que los datos de la anterior descomposición también es equivalente a los datos del diagrama de

debido a que el oscurecida números son sólo $0,1,2,3$ en orden de ocurrencia. La inicial de la partición puede ser completamente reconstruido a partir de este último diagrama. Voy a dejar a usted para comprobar que esta descomposición de los rendimientos de la supuesta identidad de potencia de la serie.

Answer 2

En aras de la exhaustividad damos una prueba algebraica de esta identidad. En primer lugar vamos a adoptar la notación estándar, en los coeficientes binomiales y los números de Stirling es usualmente $n$ que los índices del tamaño del conjunto de particiones, por lo que su identidad se convierte en $$G(z) = \sum_{n\ge k} {n \llave k} z^n = \frac{z^k}{(1-z)(1-2z)\cdots(1-kz)}$$ es decir, el ordinario de la generación de la función de el número de particiones de $n$ etiquetado de elementos en $k$ no vacía de subconjuntos. Esto es inusual, ya que normalmente sería asociar los números de Stirling del segundo tipo con exponencial en lugar de ordinario la generación de funciones.

Primero usamos la inducción para demostrar que $$\frac{z^k}{(1-z)(1-2z)\cdots(1-kz)} = \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\elegir j} \frac{1}{1-jz}.$$ Establecimiento $k=1$ da $$\frac{z}{1-z} = -1 + \frac{1}{1-z}$$ que tiene trivialmente. Ahora el uso de la inducción obtenemos que $$\frac{z^{k+1}}{(1-z)(1-2z)\cdots(1-kz)(1-(k+1)z)} = \frac{z}{1-(k+1)z} \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\elegir j} \frac{1}{1-jz}.$$ Pero tenemos $$\frac{z}{1-(k+1)z} \frac{1}{1-jz} = \frac{1}{k+1-j} \frac{1}{1-(k+1)z} - \frac{1}{k+1-j} \frac{1}{1-jz}$$ como se ve fácilmente porque $$\frac{1}{k+1-j} (1-jz-(1-(k+1)z)) = \frac{1}{k+1-j} (k+1-j)z = z.$$ Volviendo a la suma de la inducción de este modo, obtener $$\frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\elegir j} \frac{1}{k+1-j} \left(\frac{1}{1-(k+1)z} - \frac{1}{1-jz}\right).$$ Ahora lo tratan los dos términos que aparecen en la diferencia en la suma de turno. Para el primer término, que no depende de $j$, se obtiene que el coeficiente de $1/(1-(k+1)z)$ es $$\frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\elegir j} \frac{1}{k+1-j} = \frac{1} {k(k+1)!} \sum_{j=0}^k (-1)^{k-j} {k+1\elegir j} \\ = - \frac{1} {k(k+1)!} \sum_{j=0}^k (-1)^{k+1-j} {k+1\elegir j} = - \frac{1} {k(k+1)!} \left(- (-1)^{k+1-(k+1)} {k+1\elegir k+1}\right) = \frac{1} {k(k+1)!}.$$ Para el segundo término tenemos la suma $$- \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\elegir j} \frac{1}{k+1-j} \frac{1}{1-jz} = - \frac{1} {k(k+1)!} \sum_{j=0}^k (-1)^{k-j} {k+1\elegir j} \frac{1}{1-jz} \\ = \frac{1} {k(k+1)!} \sum_{j=0}^k (-1)^{k+1-j} {k+1\elegir j} \frac{1}{1-jz}.$$ Sumando las dos contribuciones obtenemos $$\frac{1} {k(k+1)!} \sum_{j=0}^k (-1)^{k+1-j} {k+1\elegir j} \frac{1}{1-jz} + \frac{1} {k(k+1)!} \frac{1}{1-(k+1)z}$$ que es $$\frac{1}{(k+1)!} \sum_{j=0}^{k+1} (-1)^{k+1-j} {k+1\choose j} \frac{1}{1-jz}.$$ Esto completa la prueba por inducción.

Ahora vamos a ampliar el racional término en la suma en una serie infinita, llegar $$\frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\elegir j} \frac{1}{1-jz} = \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\elegir j} \sum_{n\ge 0} j^n z^n\\ = \sum_{n\ge 0} z^n \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\elegir j} j^n.$$

Pero tenemos $$ \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} {k\elegir j} j^n = {n\llave k}$$ por definición, completando así la prueba.