6
$\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.

$\endgroup$
9
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Can you briefly describe how you thought this story up? I'm simply curious. $\endgroup$ – Benjamin Dickman Nov 5 '12 at 3:12
  • $\begingroup$ Why is it $n-k$ males instead of $2n - k$ males? $\endgroup$ – atb Nov 5 '12 at 3:15
  • $\begingroup$ @alexthebake: You are trying to select $n$ people in total, so since there already $k$ females, there must be $n-k$ males. $\endgroup$ – wj32 Nov 5 '12 at 3:16
  • 1
    $\begingroup$ @alexthebake: Because we are making a committee of $n$ people. If we have $k$ females, we must have $n-k$ males. $\endgroup$ – André Nicolas Nov 5 '12 at 3:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.