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

binomial-coefficientscombinatoricscontest-mathprobabilitysummation

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.

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