Binomial coefficient problem

Question

I still haven't quite realized how to solve binomial coefficient problems like this, can someone show me an elaborated way of solving this?

I need to write this expression in a more simplified way: $\sum_{k=0}^{10} k \pmatrix{10 \\ k}\pmatrix{20 \\ 10-k}$

I'm aware of the binomial identity $\sum_{k=i}^{n-j}\binom{k}{i}\binom{n-k}{j}=\binom{n+1}{j+1}$

Just can't seem to see how to use it.

Many thanks.

Answer 1

$$\sum_{k=0}^{10} k \binom{10}{k}\binom{20}{10-k} = \sum_{k=1}^{10} k \binom{10}{k}\binom{20}{10-k} = \sum_{k=1}^{10} 10 \binom{9}{k-1}\binom{20}{10-k} =\\= 10 \cdot \sum_{r=0}^{9} \binom{9}{r}\binom{20}{9-r}= 10 \cdot \binom{29}{9}.$$

Here I have first omitted the zero term for $k=0$, then used the identity (below), then changed summation variable $r = k-1$, and finally used Vandermonde, as quoted in another answer.

\begin{align}\tag{below} k \cdot \binom{10}{k} &= k \cdot \frac{10 (10 -1) \dots (10-k+1)}{k (k-1) \cdots 2 \cdot 1} \\&= 10 \cdot \frac{(10 -1) \dots (10-k+1)}{(k-1) \cdots 2 \cdot 1} \\&= 10 \cdot \frac{9 \cdot (9-1) \dots (9-(k-1)+1)}{(k-1) \cdots 2 \cdot 1} \\&= 10 \cdot \binom{9}{k-1}. \end{align}

Answer 2

Hint: Use Vandermonde identity:

http://en.wikipedia.org/wiki/Vandermonde%27s_identity

I suppose you can write it as $S =\sum_{k=0}^{r} k\pmatrix{m \\ k}\pmatrix{n \\ r-k}$.

No put r = k-1 and write out the expression which is S'

$ S = r{(m+n-1)\choose r-1}$

Here in this case r = 10, m= 10, and n = 20.

$S = \sum_{k=0}^{10} k \pmatrix{10 \\ k}\pmatrix{20 \\ 10-k} = 10{29\choose9}$

Hopefully this answers the problem.

Thanks

Satish

Answer 3

There are $10$ women and $20$ men. You need to select a team of $10$ and a leader of the team (among the $10$) who is a woman.

By selecting $k$ women, a leader among the $k$, and $10-k$ men, for $k=0,1,\dots,10$, we get your summation.

Another way to count the same thing is:

Select the leader first, and then select 9 remaining members

$$10 \times \binom{29}{9}$$