Simplifying $10 \binom{29}{0} + 9\binom{30}{1} + 8 \binom{31}{2} + \ldots + 2\binom{37}{8} + 1\binom{38}{9}$

In trying to solve a probability problem from an old math contest: https://artofproblemsolving.com/wiki/index.php/1987_AIME_Problems/Problem_13

I had reduced the crux of the problem to calculating/simplifying$$10 \binom{29}{0} + 9\binom{30}{1} + 8 \binom{31}{2} + \ldots + 2\binom{37}{8} + 1\binom{38}{9},$$which I'm not sure how to simplify further. Could anyone give me a hint? Thanks in advance.

EDIT: Calvin Lin asks me to explain how I got my expression. The total number of ways to order $40$ distinct numbers is $40!$, so that will be our denominator. So let's calculate the numerator. Without loss of generality let our numbers in some order be $1$, $2$, $\ldots$, $39$, $40$. We are counting the total number of configurations where:

1. $r_{20}$ is greater than the other first $29$ numbers i.e. $r_1$, $r_2$, $\ldots$, $r_{18}$, $r_{19}$, $r_{21}$, $r_{22}$, $\ldots$, $r_{29}$, $r_{30}$.
2. $r_{20}$ is less than $r_{31}$.

So $r_{20}$ has to be at least $30$ and is at most $39$. Let's go case by case:

• $r_{20} = 30$: The first $29$ numbers (where is $r_{20}$ omitted) have to be selected from $1$, $2$, $\ldots$, $28$, $29$, hence $29!$ ways to select and order. Then there's $10$ choices for $r_{31}$, and then $9!$ choices for the last $9$ numbers.
• $r_{20} = 31$: The first $29$ numbers (where is $r_{20}$ omitted) have to be selected from $1$, $2$, $\ldots$, $28$, $29$, $30$, hence $30 \cdot 29 \cdots 3 \cdot 2$ ways to select and order. Then there's $9$ choices for $r_{31}$, and then $9!$ choices for the last $9$ numbers.
• And so forth$\ldots$
• $r_{20} = 39$: The first $29$ numbers (where is $r_{20}$ omitted) have to be selected from $1$, $2$, $\ldots$, $37$, $38$, hence $38 \cdot 37 \cdots 11 \cdot 10$ ways to select and order. There's only $1$ choice for $r_{31}$ and that's $r_{31} = 40$, and again there's $9!$ choices for the last $9$ numbers.

So our numerator is$$(29!)(10)(9!) + (30 \cdot 29 \cdots 3 \cdot 2)(9)(9!) + \ldots + (37 \cdot 36 \cdots 10 \cdot 9)(2)(9!) + (38 \cdot 37 \cdots 11 \cdot 10)(1)(9!) = (29!)(9!)\left(10 + 9{{30}\over{1}} + 8{{31 \cdot 20}\over{2 \cdot 1}} + 7{{32 \cdot 31 \cdot 30}\over{3 \cdot 2 \cdot 1}} + \ldots + 1{{38 \cdots 30}\over{9 \cdots 1}}\right) = (29!)(9!)\left(10 \binom{29}{0} + 9\binom{30}{1} + 8 \binom{31}{2} + \ldots + 1\binom{38}{9}\right).$$So the expression we want to calculate/simplify is$$10 \binom{29}{0} + 9\binom{30}{1} + 8 \binom{31}{2} + \ldots + 1\binom{38}{9}.$$Again, any help would be well-appreciated.

So we want the value of $$\sum_{n=0}^9 (10-n)\binom{29+n}{n}$$ Note that $\frac{x}{(1-x)^2}=0+x+2x^2+3x^3+4x^4+\ldots$ and $\frac{1}{(1-x)^{30}}=\sum_{n=0}^\infty \binom{29+n}{n}x^n$. Hence, our desired sum is the coefficient of $x^{10}$ in the cauchy product of the two sequences.

This is the coefficient of $x^{10}$ in $$\frac{x}{(1-x)^2}\cdot \frac{1}{(1-x)^{30}}$$ $$=\frac{x}{(1-x)^{32}}$$ $$=x\sum_{n=0}^\infty \binom{31+n}{n}x^n$$ Hence, the coefficient of $x^{10}$ is $\binom{40}{9}$

Approach 1: Use the Hockey stick identity twice.

First application: It states that $ { 29\choose 0 } + \ldots { 29 + i \choose i } = { 29 + i + 1 \choose i }$.
Second application: Sum up the first application for $ i = 0$ to 9 via the Hockey stick identity again to get $ \sum_{i=0}^9 { 29 + i +1 \choose i } = {40 \choose 9 }$.

Approach 2: Find a combinatorial identity now that you know the expression is "nice".
You could modify the combinatorial identity for Hockey stick identity.

Let us define $b=10$ and $a=30$, then you can obtain a generalized formula:

$$\sum _{i=1}^b i \binom{a+b-i-1}{b-i}=\binom{a+b}{b-1}{\color{lightgrey}{=\frac{\Gamma (a+b+1)}{\Gamma (a+2) \Gamma (b)}}}$$

Here $\Gamma (z)$ is the Euler Gamma function. You may verify it using Mathematica by:

FullSimplify[Sum[i*Binomial[a + b - 1 - i, b - i], {i, 1, b}]];

Inserting your concrete values leads to $273438880$.

An interesting reference might be the paper "Some Formulas for Sums of Binomial Coefficients and Gamma Functions", which deals with connections between the Gamma function and sums of binomial coefficients.