Alternativa prueba combinatoria combinatorio identidad

Question

Tengo una pregunta con respecto a la combinatoria. Estoy supone que debe mostrar el siguiente combinatoria de identidad: $\sum_{r=0}^n\binom{n}{r}\binom{m+r}{n}=\sum_{r=0}^n\binom{n}{r}\binom{m}{r}2^r$.

El algebraicas manera es considerar el coeficiente de $t^m$ en la expansión de $(1+t)^n(1-t)^{-(n+1)}$. Para $r\in\{0,1,\cdots,n\}$, tenemos que el coeficiente de $t^{n-r}$ en la expansión de $(1+t)^n$ a ser igual a $\binom{n}{r}$, y el coeficiente de $t^{m+r-n}$ en la expansión de $(1-t)^{-(n+1)}$ a ser igual a $\binom{m+r}{n}$. Mediante la adición y de la multiplicación de los principios de esta muestra que el coeficiente de $t^m$ en la expansión de $(1+t)^n(1-t)^{-(n+1)}$ será igual a $\sum_{r=0}^n\binom{n}{r}\binom{m+r}{n}$.

Por otro lado, se nota que $(1+t)^n(1-t)^{-(n+1)}=(1+\frac{2t}{1-t})^n(1-t)^{-1}=\sum_{r=0}^n\binom{n}{r}2^rt^r(1-t)^{-(r+1)}$. Como el coeficiente de $t^{m-r}$ es igual a $\binom{m}{r}$, esto implica que el coeficiente de $t^m$ en la expansión de $(1+t)^n(1-t)^{-(n+1)}$ es igual a $\sum_{r=0}^n\binom{n}{r}\binom{m}{r}2^r$.

Lo que estoy pensando, es pensar en una manera de demostrar esta identidad, sin el uso de la binomial generalizada de la serie. Yo estaba tratando de pensar en una combinatoria método para resolver este problema. En particular, yo estaba tratando de demostrar que la combinatoria de identidad de la siguiente manera:

En primer lugar, dejar que nos dará una clase de $n$ varones y una clase de $m$ de las niñas, donde $n\leq m$. Elegir un equipo de $A$ $r$ de los niños, y elegir un equipo de $B$ $r$ de las niñas, y, finalmente, elegir cualquier subconjunto (puede estar vacío) de los niños de $A$ a limpiar el salón de clases, donde $r\in\{0,1,\cdots,n\}$. Para cada valor de $r$, vemos que hay $\binom{n}{r}$ opciones para $A$, $\binom{m}{r}$ opciones para $B$, y posteriormente se $2^r$ maneras de elegir un subconjunto de $A$. De esta manera obtenemos el número de maneras de hacerlo, a ser igual a la expresión en el lado derecho de la identidad.

Lo que estoy luchando, aunque, es ser capaz de contar el número de maneras en una forma que se me dé la expresión en el lado izquierdo de la identidad. He intentado en primer lugar, para elegir a los niños a limpiar el salón de clases antes de la elección de los conjuntos de $A$$B$, pero terminé con algunos desordenado expresión que no parece cerca de igualar la expresión en el lado izquierdo.

Me gustaría saber si hay otra manera de mirar este método (o podría haber estado perdiendo de algo), o si hay algún otro método combinatorio (o cualquier otro método algebraico que no implican el uso de la binomial generalizada de la serie) que uno podría pensar de mostrar el deseo de identidad.

Answer 1

Un enfoque de uso común binomio identidades: $$ \begin{align} \sum_{r=0}^n\binom{n}{r}\binom{m+r}{n} &=\sum_{r=0}^n\binom{n}{r}\sum_{k=0}^n\binom{m}{k}\binom{r}{n-k}\tag{1}\\ &=\sum_{k=0}^n\binom{m}{k}\sum_{r=0}^n\binom{n}{r}\binom{r}{n-k}\tag{2}\\ &=\sum_{k=0}^n\binom{m}{k}\sum_{r=0}^n\binom{n}{n-k}\binom{k}{r-n+k}\tag{3}\\ &=\sum_{k=0}^n\binom{m}{k}\binom{n}{k}2^k\tag{4} \end{align} $$ Explicación:
$(1)$: $\sum\limits_{k=0}^n\binom{m}{k}\binom{r}{n-k}=\binom{m+r}{n}$
$(2)$: cambiar el orden de la suma de
$(3)$: $\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$
$(4)$: $\sum\limits_{k=0}^n\binom{n}{k}=2^n$

Answer 2

En efecto, los dos números son iguales a $D_{m,n}$, que es el llamado Delannoy número de $(m \times n)$-red. Se define como el número de caminos de $(0,0)$ $(m,n)$utilizando los pasos $(0,1), (1,0)$$(1,1)$.

LHS: Clasificar las rutas por el número de $(1,1)$-pasos. Si hay $r$ diagonal pasos, entonces necesitamos $m+n-r$ pasos en total (de los cuales, $r$ son diagonales pasos) y tenemos $m+n-2r$ no-diagonal pasos (de los cuales, $n-r$ $(0,1)$- pasos). Eso te dará una idea de cómo ir sobre la muestra que $LHS=D_{m,n}$.

RHS: Esperemos que no es inteligente manera de contar el número de caminos de una manera diferente, mostrando que $RHS=D_{m,n}$.

Alternativamente, tal vez uno (algebraica) enfoque podría ser para mostrar que ambas expresiones se satisface la relación de recurrencia $$D_{m,n}=D_{m,n-1}+D_{m-1,n}+D_{m-1,n-1}$$

con condición inicial $D_{0,0}=1$.

(De esta manera se sigue trivialmente a partir de la definición de $D_{m,n}$. Sólo la condición del tipo de la última etapa.)