Find the coefficient of $x^{19}$ in the expression $(x+1)(x+2)(x+3)\cdots (x+400)$

Question

Find the coefficient of $x^{19}$ in the expression $(x+1)(x+2)(x+3)\cdots (x+400)$

I have no clue how to start. Any kind of help will be appreciated.

Answer 1

If you multiply together all the terms, you'll get a sum. Think of each term in this sum as a $400$ letter long word, where the $j$th letter is either an $x$ or the number $j$ (for $1\leq j \leq 400)$. You can of course simplify this expression into the form of $l \cdot x^k$ where k and l is some numbers.

Now, for example the only way to get $x^{400}$ in this sum is to choose $x$ from each pair of parentheses to get the $xx...xx$, a $400$ letter long word.

So how can you get a word which simplifies into the form of $l\cdot x^{19}$? Well if you choose $x$ from exactly $19$ terms and choose the numbers from the other $400-19$, you'll get such a term. And it's not hard to see that this is the only way to do so.

So what's going to be the coefficient? If you add up the coefficients of all the appropriate terms from the sum(ie. of the form $l\cdot x^{19})$, then you get the following: with $S=\{1,...,400\}$

$a_{19} = \sum_{I \subseteq S \text{ and } |I| = 19} \prod_{i \in S \setminus I}(i)$ If you multiply together all the terms, you'll get a sum. Think of each term in this sum as a $400$ letter long word, where the $j$th letter is either an $x$ or the number $j$ (for $1\leq j \leq 400)$. You can of course simplify this expression into the form of $l \cdot x^k$ where k and l is some numbers.

Now, for example the only way to get $x^{400}$ in this sum is to choose $x$ from each pair of parentheses to get the $xx...xx$, a $400$ letter long word.

So how can you get a word which simplifies into the form of $l\cdot x^{19}$? Well if you choose $x$ from exactly $19$ terms and choose the numbers from the other $400-19$, you'll get such a term. And it's not hard to see that this is the only way to do so.

So what's going to be the coefficient? If you add up the coefficients of all the appropriate terms from the sum(ie. of the form $l\cdot x^{19})$, then you get the following: with $S=\{1,...,400\}$

$a_{19} = \sum_{I \subseteq S \text{ and } |I| = 19} \prod_{i \in S \setminus I}(i)$

Also note that all the numbers in this sum are nonnegative and the tiniest one is $381!$

So the coefficient is at least - and in fact much more, than - $\binom{400}{19}381!$, therefore for all purposes it is incomputable by hand.