Calculate $\sum_{k=1}^{10}k{{10}\choose{k}}{{20}\choose{10-k}}$

Question

I've been given the task of calculating: $$\sum_{k=1}^{10}k{{10}\choose{k}}{{20}\choose{10-k}}$$

I've tried to start with what I'm familiar with - $\sum_{k=0}^{10}{{10}\choose{k}}{{20}\choose{10-k}}$. I've tried adding the value of $k=0$ to the sum, which is $0{{10}\choose{0}}{{20}\choose{10}} = 0$ and then subtracting it to get the equality: $$\sum_{k=1}^{10}{{10}\choose{k}}{{20}\choose{10-k}} = \sum_{k=0}^{10}{{10}\choose{k}}{{20}\choose{10-k}} - 0$$

Combinatorically, this is equal to ${30}\choose{10}$.

However, I'm stuck with that $k$ which is in the beginning of each value of the sum: $\sum_{k=1}^{10}\color{red}{k}{{10}\choose{k}}{{20}\choose{10-k}}$. I just can't seem to find a way to solve this algebraically, or combinatorically. I feel like I'm missing something really basic here but I can't point the finger to what it may be. Suggestions are greatly appreciated!

Answer 1

$$\sum_{k=1}^{10}k\binom{10}{k}\binom{20}{10-k} = 10\sum_{k=1}^{10}\binom{9}{k-1}\binom{20}{10-k} \stackrel{k\mapsto j+1}{=} 10\sum_{j=0}^{9}\binom{9}{j}\binom{20}{9-j} $$ equals $10\binom{29}{9}$ by Vandermonde's identity.

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} & \sum_{k = 1}^{10}k{10 \choose k}{20\choose 10 - k} = \sum_{k = 1}^{10}k{10 \choose k}\bracks{z^{10 - k}}\pars{1 + z}^{20} \\[5mm] = & \ \bracks{z^{10}}\pars{1 + z}^{20}\sum_{k = 1}^{10}{10 \choose k}kz^{k} \\[5mm] = & \ \bracks{z^{10}}\pars{1 + z}^{20}\,z\,\totald{}{z} \sum_{k = 1}^{10}{10 \choose k}z^{k} = \bracks{z^{9}}\pars{1 + z}^{20}\,\totald{\pars{1 + z}^{10}}{z} \\[5mm] = & \ 10\bracks{z^{9}}\pars{1 + z}^{29} = 10{29 \choose 9} = \bbx{100150050} \\ & \end{align}

Answer 3

An alternative using combinatorial proof is quite nice too. You need to choose $10$ people from $10$ adults and $20$ children. Then from these people, one adult is selected as leader.

First Method

Choose some people from the adults, then the rest from the children. Subsequently, select one of the chosen adult to be the leader. The number of way to do this is given by the following:

$$ \sum_{k=1}^{10}k\binom{10}{k}\binom{20}{10-k} $$

Second Method

Simply choose one adult to be the leader first, then choose $9$ people out of the remaining $29$ adults and children combined. The number of way to do this is given by the following:

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

Conclusion

Both first and second method count the same thing. Therefore the two expression must be equal

$$ \sum_{k=1}^{10}k\binom{10}{k}\binom{20}{10-k} = \binom{10}{1}\binom{29}{9} $$

Comments

You may notice that this proof is quite similar to the combinatorial proof of Vandermonde's identity. This is because it's simply a slightly modified one.