How can I show that k and n being integers


the following is true using a combination proof.

I am not sure how to do this. on the right hand side you have the set of n object and you are and out of the set (2n-1) object you chose n-1 and multiply by the set n.

On the right hand you chose a out n of object one item a k and square it and then multiply by this k object. For as many k item you have.

But how is it shown they equal?


Here it goes:
Suppose there are $2n$ people, divided in two groups of $n$. We want to choose the same number of people $k$ ($1\leq k\leq n$) from both groups to play against each other in a match. For the first team, from the ones who play, we choose a leader. If we sum over all possibilities for $k$, we get the left hand side: $$ \sum_{k=1}^nk\binom{n}{k}^2 $$ We can also choose first pick a leader from the first $n$ people in $n$ ways. Then, we pick $n-1$ from the remaining $2n-1$ people. From the first half, we pick those people who will play and from the second half, we pick those people who won't play. Suppose we pick $k-1$ people from the first $n-1$ people. Then, $k$ people will play for the first team and $n-(n-1-(k-1))=k$ people will play for the second team. Thus, we count the same number of events as before. This yields the equality: $$ \sum_{k=1}^nk\binom{n}{k}^2=n\dbinom{2n-1}{n-1} $$

  • $\begingroup$ yes this makes perfecto sense but who are the 2n-1 people from which n-1 people are chosen are they one of the groups of the 2n people. $\endgroup$ – Fernando Martinez Feb 21 '14 at 22:54
  • $\begingroup$ @FernandoMartinez, the $2n-1$ people are just the $2n$ people, except the leader, who is already chosen at that point. $\endgroup$ – Ragnar Feb 21 '14 at 23:32

$\sum_{k=1}^nk\dbinom{n}{k}^2=\sum_{k=1}^nk\dbinom{n}{k}\dbinom{n}{n-k}$ is the number of ways of ways of choosing a set of $n$ balls from two collections A and B of $n$ of identical balls, and declaring a ball taken from A as a 'good' ball.Where the $k$-th term in the summation in LHS corresponds to the case: $k$ balls picked from A and $n-k$ picked from B, and choosing one of $k$ balls taken from A as the good ball.

The same thing can be done by first choosing a good ball from A in $n$ ways and choosing remaining $n-1$ balls from total $2n-1$ balls left in collections A and B, after removal.Which can be done in $n\dbinom{2n-1}{n-1}$ ways.


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.