Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Did you try induction? –  nikita2 Nov 5 '12 at 3:04
2  
@nikita2: "Combinatorial proof" means no induction. –  wj32 Nov 5 '12 at 3:08
add comment

1 Answer

up vote 7 down vote accepted

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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