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:

- $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}$.
- $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.

## Best Answer

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}$