Quiero probar la siguiente identidad combinatoria:\begin{align}
{n + k \choose k} = \sum \limits_{i=0}^n {n -i +k -1 \choose k -1}.
\end {Alinee el} queremos elegir k de $n+k$.
Quiero usar la identidad siguiente:\begin{align}
{n \choose k} = {n \choose n-k}.
\end {Alinee el} así que tenemos que demostrar que:\begin{align}
{n + k \choose n} = \sum \limits_{i=0}^n {n -i +k -1 \choose n -i}.
\end {Alinee el} de palabras, elegir n de n + k. Yo todavía no puedo averiguar por qué esto es cierto. ¿Algún organismo me puede ayudar?
Respuesta
¿Demasiados anuncios?
Oli
Puntos
89
Tenemos $n+k$ diferentes donas, alineados en una fila. Están etiquetados $D_0$$D_{n+k-1}$. La última $k$ son cubiertas de chocolate. Hay $\binom{n+k}{k}$ formas de elegir los $k$ donas para el desayuno. Que nos permiten contar el número de maneras de hacer la elección de otra manera.
Deje $i$ ser el sello de la izquierda de anillos elegido. A continuación,$i$$0$$n$. Para cualquier $i$, lo que deja a $n-i+k-1$ donas, de la que debemos optar $k-1$. Así que para cualquier $i$, $\binom{n-i+k-1}{k-1}$ formas de hacer la elección. De todas las maneras de escoger el desayuno, agregar de a$i=0$$i=n$.
Comentario: podríamos reformular el ejemplo de uso de la identidad de $\binom{n+k}{k}=\binom{n+k}{n}$ mencionado en la pregunta, pero que es innecesario.
