7
$\begingroup$

The question states to give a combinatorial proof for:

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

Honestly, I have no idea how to begin. I want to do a two-way counting proof, looking at the LHS and the RHS correct? Any help would be greatly appreciated.

  • 0
    See also: [A combinatorial proof of the identity: $\sum_{k=1}^n k \binom{n}{k}^2 = {n}\binom{2n-1}{n-1}$?](https://math.stackexchange.com/q/2561029) and [Combination proof $\sum_{k=1}^nk\binom{n}{k}^2=n\binom{2n-1}{n-1}$](https://math.stackexchange.com/q/685308)2018-06-10

1 Answers 1

10

We have a group of $2n$ people, $n$ female and $n$ male. We want to select a committee of $n$ people, including a female Chair.

We can select the Chair first. There are $n$ ways to do this. For each of these ways, there are $\binom{2n-1}{n-1}$ ways to choose the rest of the committee. Thus there are $n\binom{2n-1}{n-1}$ ways to choose a committee with female Chair.

We now count the number of committees with female Chair in a different way. The committee will have a total of $k$ females, where $k$ ranges from $1$ to $n$, and $n-k$ males.

We can select $k$ females and $n-k$ males in $\binom{n}{k}\binom{n}{n-k}$ ways. For each of these ways, the Chair can be chosen from the $k$ females in $k$ ways. Thus there are $k\binom{n}{k}\binom{n}{n-k}$ ways to make a committee with $k$ females, including a female Chair, and $n-k$ males.

Finally, note that $\binom{n}{n-k}=\binom{n}{k}$, and sum over all $k$ from $1$ to $n$. The number of committees with female Chair is $\sum_{k=1}^n k\binom{n}{k}^2$.

  • 1
    @alexthebake: Because we are making a committee of $n$ people. If we have $k$ females, we must have $n-k$ males.2012-11-05