Prueba combinatoria para series de números de Stirling y coeficientes binomiales

Question

Estoy luchando con la siguiente pregunta de un trabajo para un curso de introducción a la combinatoria.

Demostrar, por medio de una combinatoria argumento, que el siguiente se tiene: \begin{aligned} {n+1 \brace k+1}&=\sum_{r=k}^{n}\binom{n}{r} {r \brace k} \end{aligned}

El uso de la identidad familiar

\begin{equation} {n \brace k}={n-1 \brace k-1}+k{n \brace k-1} \end{equation}

Soy capaz de mostrar de forma algebraica que

\begin{equation} {n+1 \brace k+1}=\sum_{m=k}^{n}(k+1)^{n-m}{m \brace k}. \end{equation}

En hacer esto, yo esperaba ser capaz de introducir los coeficientes binomiales con el fin de determinar si la definición recursiva de la número de Stirling del segundo tipo sería conducente a una prueba algebraica. Por desgracia, la exponencial términos se mantuvo incluso después de la sustitución de

\begin{equation} (k+1)^{n-m}=\sum_{i=1}^{n-m}\binom{n-m}{i}k^{i} \end{equation}

que podría dar la definición:

\begin{equation} {n+1 \brace k+1}=\sum_{m=k}^{n} \left[ \sum_{i=1}^{n-m}\binom{n-m}{i}k^{i} \right] {m \brace k} \end{equation}

Por supuesto, si yo había sido un éxito, yo esperaba para convertir este conocimiento en una modificación de la combinatoria de la prueba para el recursiva de identidad, $S(n,k)=S(n-1,k-1)+kS(n-1,k)$ (donde hay dos casos: uno en el que $n$ es un singleton y el otro en el cual $n \in A$ donde $|A|>1$).

Si alguien tiene recomendaciones o sugerencias en cuanto a cómo llevar a cabo la combinatoria de prueba (o incluso la algebraicas, que estoy personalmente curiosidad), les agradecería mucho la ayuda!

Gracias

Answer 1

Empezar por la composición de la demanda utilizando las convenciones estándar. Buscamos mostrar que $${n+1 \brace k+1} = \sum_{m=k}^n {n\choose m} {m\brace k}.$$

La combinatoria de la prueba es muy sencilla. El lado izquierdo es el número de particiones de un conjunto de $n+1$ distinguibles elementos en $k+1$ indistinguibles de los subconjuntos. (Permutación de grupo $S_{k+1}$ y no el posicionamiento en el subconjuntos: un conjunto de conjuntos.) El lado derecho cuenta la misma estadística. Supongamos que tenemos una partición en $k+1$ subconjuntos y el elemento con la etiqueta $n+1$ ha pasado a un subconjunto de tamaño $n-m+1$. (Hay $n-m$ otros elementos de este subconjunto.) Entonces debemos escogido $m$ elementos de los otros $n$ artículos para el otro $k$ subconjuntos y particiones de los $m$ elementos en $k$ subconjuntos, dando una contribución de $${n\choose m} {m\brace k}.$$ La suma cuenta todos los posibles total subconjunto de los tamaños de los subconjuntos que no contengan $n+1$, a partir de $k$ debido a que ninguno de los subconjuntos puede estar vacío.

La prueba algebraica utiliza exponencial funciones de generación. Recordemos que las particiones en subconjuntos tienen las siguientes combinatoria especificación: $$\mathfrak{P}(\mathfrak{P}_{\ge 1}(\mathcal{Z})).$$ Esto implica inmediatamente que la generación de la función de los números de Stirling del segundo tipo es $$ G(z, u) = \exp(u(\exp(z)-1)).$$ Ahora tenemos $${n+1 \llave k+1} = (n+1)! [z^{n+1}] [u^{k+1}] \exp(u(\exp(z)-1)) \\= (n+1)! [z^{n+1}] \frac{(\exp(z)-1)^{k+1}}{(k+1)!}.$$ Este último término es $$(n+1)! \frac{1}{n+1} [z^n] \left(\frac{(\exp(z)-1)^{k+1}}{(k+1)!}\right)'\\ = n! [z^n] \frac{(k+1)(\exp(z)-1)^k}{(k+1)!} \exp(z) = n! [z^n] \exp(z) \frac{(\exp(z)-1)^k}{k!}.$$ Expandiendo el producto de los dos exponenciales este rendimientos $$n! \sum_{m=0}^n \frac{1}{(n-m)!} [z^m] \frac{(\exp(z)-1)^k}{k!} = \sum_{m=0}^n \frac{n!}{m! (n-m)!} m! [z^m] \frac{(\exp(z)-1)^k}{k!} \\= \sum_{m=0}^n \frac{n!}{m! (n-m)!} {m \llave k} = \sum_{m=k}^n {n\elegir m} {m \llave k}.$$

Observar que la combinatoria y la prueba algebraica son muy similares.