Combinatoria prueba de una ecuación

Question

Me preguntaba si hay una combinatoria prueba de esta ecuación? $$\sum_{k=0}^{n}k \binom{n+k-1}{k} =n \binom{2n}{n+1}$$

Answer 1

Sí. Supongamos que $P_1,P_2,\dots,P_{2n}$ son los miembros de una organización. Queremos escoger un comité de $n+1$ de estos miembros. La persona con el mayor número automáticamente será presidente de la comisión, y queremos seleccionar uno de los restantes $n$ a los miembros a ser el secretario. Hay $\binom{2n}{n+1}$ formas para elegir el comité, y, a continuación, $n$ formas para elegir al secretario, por lo que hay $n\binom{2n}{n+1}$ formas de realizar la tarea.

Ahora el recuento de los comités cuyo presidente es $P_{n+k}$; claramente $k$ debe rango de $1$ a través de $n$. Hay $\binom{n+k-1}{n-1}=\binom{n+k-1}k$ formas para elegir a $\{P_1,\dots,P_{n+k-1}\}$ $n-1$ de los miembros que no son el secretario y el secretario debe ser elegido de entre el resto del $(n+k-1)-(n-1)=k$ de la gente, así que hay $k\binom{n+k-1}k$ formas para elegir el comité, de manera que $P_{n-k}$ es el presidente. Por lo tanto,

$$\sum_{k=0}^nk\binom{n+k-1}k=0+\sum_{k=1}^nk\binom{n+k-1}k=n\binom{2n}{n+1}\;.$$