Cómo empezar la prueba combinatoria de $\sum_{k=1}^n k \binom nk^2 = n \binom{2n-1}{n-1}$

Question

La pregunta dice que hay que dar una prueba combinatoria para:

$$\sum_{k=1}^{n}k{n \choose k}^2 = n{{2n-1}\choose{n-1}}$$

Sinceramente, no tengo ni idea de cómo empezar. Quiero hacer una prueba de recuento en dos direcciones, mirando el LHS y el RHS ¿correcto? Cualquier ayuda sería muy apreciada.

Answer 1

Tenemos un grupo de $2n$ personas, $n$ femenino y $n$ hombre. Queremos seleccionar un comité de $n$ personas, incluida una presidenta.

Podemos seleccionar primero la silla. Hay $n$ formas de hacerlo. Para cada una de estas formas, hay $\binom{2n-1}{n-1}$ formas de elegir el resto del comité. Así, hay $n\binom{2n-1}{n-1}$ formas de elegir un comité con una presidenta.

Ahora contamos el número de comités con una presidenta en un diferentes manera. El comité tendrá un total de $k$ mujeres, donde $k$ oscila entre $1$ a $n$ y $n-k$ los hombres.

Podemos seleccionar $k$ mujeres y $n-k$ hombres en $\binom{n}{k}\binom{n}{n-k}$ formas. Para cada una de estas formas, la Cátedra puede ser elegida entre las $k$ mujeres en $k$ maneras. Así, hay $k\binom{n}{k}\binom{n}{n-k}$ formas de hacer un comité con $k$ mujeres, incluida una presidenta, y $n-k$ los hombres.

Por último, hay que tener en cuenta que $\binom{n}{n-k}=\binom{n}{k}$ y la suma de todos los $k$ de $1$ a $n$ . El número de comisiones con presidenta es $\sum_{k=1}^n k\binom{n}{k}^2$ .