Prueba ${{n+m+1}\brace m}=\sum_{k=0}^mk{{n+k}\brace k}$ via doble contabilización

Question

Quiero mostrar a través de una doble contabilización argumento de que$${{n+m+1}\brace m}=\sum_{k=0}^mk{{n+k}\brace k}$$for $m,n\in\Bbb, N$ (where $0\en\Bbb N$).

Tenga en cuenta que ${{n}\brace k}$ es un número de Stirling del segundo tipo (es decir, el número de particiones de $[n]:=\{1,2,\ldots,n\}$ a $k$ bloques). Estoy empezando a hacer la doble contabilización de las pruebas, así que sólo quiero para asegurarse de que estoy haciendo este derecho. Me gustaría alguna opinión acerca de mi prueba: si es correcto o no, ¿cuáles son algunas de las mejoras que podría hacer, etc. Aquí está mi prueba:

Sabemos que ${{n+m+1}\brace m}$ es el número de maneras de partición de la $[n+m+1]$ a $m$ bloques. Ahora nos centramos en el $n+k+1$ elemento $[n+m+1]$ algunos $0\leq k\leq m$. Cada elemento del pasado $n+k+1$ ponemos en su propio bloque de la partición, el cual representa el $(n+m+1)-(n+k+1)=m-k$ de los bloques. Dividimos la primera $n+k$ elementos en el resto de la $k$ bloques en ${{n}\brace k}$ maneras. A continuación, introducimos el elemento $n+k+1$ en uno de estos $k$ bloques (que se puede hacer en $k$ formas). Por lo tanto, no se $k{{n+k}\brace k}$ formas de dividir el conjunto de con $m$ bloques con nuestra selección de $k$. Nos suma sobre todas las posibilidades de $k$ a cuenta de todas las opciones de la $n+k+1$ elemento para obtener el ${{n+m+1}\brace m}=\sum_{k=0}^mk{{n+k}\brace k}$ total de particiones de $[n+m+1]$ a $m$ bloques.

Gracias de antemano por cualquier comentario. Si tienes otra manera de probar esto que me encantaría ver eso.

Answer 1

Para el recuento doble argumento de que yo pondría algo como esto. Supongamos que partición de $n+m+1$ etiquetado de elementos en $m$ conjuntos. Ahora vamos a $n+q+1$ ser el valor mínimo para que todos los elementos de la etiqueta de $n+q+2$ $n+m+1$residir en singleton conjuntos. Esto le da a $m-q$ los embarazos únicos. Aquí tenemos claramente ha $q\ge 1$ (al $q=0$ obtenemos $m$ los embarazos únicos que no deja nada para cubrir los elementos de a $n+1$) así como $q\le m$ ($q=m$ es el top caso de que $n+m+1$ no es un singleton). Tenga en cuenta también que $n+q+1$ es en una partición que contiene al menos un elemento adicional o no habría sido mínima. Por lo tanto, la partición de los elementos desde el extremo inferior (la cadena de singleton es el extremo superior) es un partición de $n+q+1$ a $q$ elementos con $n+q+1$ no ser un singleton. Esto significa que se obtiene una partición ordinaria de $n+q$ en $q$ elementos cuando se retire $n+q+1$ de su partición. Hay ${n+q\brace q}$ de estos y tenemos $q$ posibilidades de $n+q+1,$ dar la fórmula

$${n+m+1\brace m} = \sum_{q=1}^m q {n+q\brace q}.$$

Para una prueba algebraica, el uso de la inducción de partida en $m=1$ donde nos encontramos

$${n+2\brace 1} = 1 \times {n+1\brace 1}$$

que tiene por la inspección. Suponiendo que tiene de $m$ que tenemos en la inducción paso

$${n+m+1\abrazadera m} + (m+1){n+m+1\llave de m+1} = \sum_{q=1}^{m+1} p {n+q\llave q}.$$

La izquierda es sólo el fondo de Stirling número de recurrencia y obtenemos

$${n+m+2\llave de m+1} = \sum_{q=1}^{m+1} p {n+q\llave q}$$

como se desee.