1

The value of $\displaystyle \sum^{10}_{k=0}\binom{20+k}{20}\cdot \binom{20-k}{10}$

Using $\displaystyle \binom{n}{r}=\binom{n}{n-r}$

So we have $\displaystyle \sum^{10}_{k=0}\binom{20+k}{k}\cdot \binom{20-k}{10-k}=\binom{40}{10}$

(Above using $2$ way counting ,

we have total $40$ students and we have to select $10$ students)

But answer given as $\displaystyle \binom{41}{10}$

Please have a look on that problem

Priti Bisht
  • 421

2 Answers2

4

Their answer is right.

Consider the bijection: Choose $31$ from $41$ objects. The location of the $21$st object (at location $21+k$) splits the rest into a selection of $20$ objects from the first $20+k$ and a selection of $10$ from the last $20-k$. Similarly, a selection of the latter sort can be subsumed into a selection of $31$ from $41$ objects.

Alternatively, $1/(1-z)^{n+1}=\sum_{k=0} ((n+k)Cn )x^k$, so the first binomial is the coefficients of $z^k$ in $1/(1-z)^{21}$, the second of $z^{10-k}$ in $1/(1-z)^{11}$, and the total sumproduct is the coefficient of $z^{10}$, which gives that you want the coefficient of $z^{10}$ of $1/(1-z)^{32}$ which gives $(32+10-1)C31=41C10$.

Eric
  • 6,348
  • +1 : Wow. Nice answer. – user2661923 Dec 19 '23 at 07:38
  • For what its worth, it took me a few moments to visualize the Stars and Bars computation that led to the conclusion in the last sentence of your posting; and I am extremely familiar with Stars and Bars. You might wish to add a couple of paragraphs to the end of your answer, explaining the computation of the coefficient of $~z^{10}.$ – user2661923 Dec 19 '23 at 07:43
  • I just used the formula from the first sentence of the paragraph for the generating function of $1/(1-z)^{n+1}$. It’s $z^{10}$ because $10=k+(10-k)$. There’s no combinatorial reasoning in the second argument, although I am taking the generating function of $1/(1-z)^{n+1}$ for granted which I suppose you could prove with either Stars and Bars or just induction. – Eric Dec 19 '23 at 13:07
1

Here we have a Chu-Vandermonde Identity in disguise.

We obtain: \begin{align*} \color{blue}{\sum^{10}_{k=0}\binom{20+k}{k}\binom{20-k}{10-k}} &=\sum^{10}_{k=0}\binom{-21}{k}\binom{-11}{10-k}\tag{1}\\ &=\binom{-32}{10}\tag{2}\\ &\,\,\color{blue}{=\binom{41}{10}}\tag{3} \end{align*} and the claim follows.

Comment:

  • In (1) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ twice.

  • In (2) we apply the Chu-Vandermonde identity.

  • In (3) we apply the binomial identity used in (1) again.

Markus Scheuer
  • 108,315