Evaluate:${30 \choose 0}{20 \choose 10}+{31 \choose 1}{19 \choose 10}+{32 \choose 2}{18 \choose 10}+\ldots +{40 \choose 10}{10 \choose 10}$

Question

Evaluate:$\displaystyle{30 \choose 0}{20 \choose 10}+{31 \choose 1}{19 \choose 10}+{32 \choose 2}{18 \choose 10}+\ldots +{40 \choose 10}{10 \choose 10}$.

After seeing the hint, I got the solution.

Coeff of $x^{11}$ in $(1-x)^{-11} \times (1-x)^{-31} = {51 \choose 10}$.

I didn't find this approch very "natural", I've never done a question requiring to consider negative index of binomial expansion before. I can understand that this gives the required answer, on expanding the binomial series, but not able to get a "feel" as to how to logically deduce the original Question to this. Could anyone please provide a motivation on how to think of this idea/ any other alternative solution to this question?

Answer 1

I like combinatorial proof more than generating function.

Imagine choosing $41$ numbers from $1,...,51$. The possible $11$th lowest number is $i=11,...,21$. First, pick $10$ numbers from $1,...,i-1$ and then $30$ numbers from $i+1,...,51$.

$$ \binom{51}{41}=\sum_{i=11}^{21}{\binom{51-i}{30}\binom{i-1}{10}} $$

Answer 2

When facing this kind of problems, what I will do is put this into a family.

For your example, I would first write it as $$\sum_{m + n = 50}\binom{m}{30}\binom{n}{10}.$$

There are then three parameters involved here: $50$, $30$, $10$. I then replace them with variables:$$S(t, a, b)=\sum_{m + n = t}\binom{m}{a} \binom{n}{b}.$$

Now we can apply all kinds of mechanisms to solve this. Here I choose the generating function approach, viewing $a, b$ as parameters and write:$$F_{a, b}(X) = \sum_t S(t, a, b) X^t.$$

I then proceeds to transform the formula: \begin{eqnarray}F_{a, b}(X) &=& \sum_t\sum_{m + n = t}\binom m a\binom n b X^t\\ &=& \sum_m \sum_n\binom m a\binom n b X^{m + n}\\ &=& \left(\sum_m\binom m a X^m\right)\left(\sum_n\binom n b X^n\right)\\ &=& X^a(1 - X)^{-(a + 1)}\cdot X^b(1 - X)^{-(b + 1)}\\ &=& X^{a + b} (1 - X)^{- (a + b + 2)}. \end{eqnarray}

Therefore we get $S(t, a, b) = \binom{t + 1}{a + b + 1}$.