# What is the coefficient of $x^{18}$ in the expansion of $(x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})^{4}$?

How to approach this type of question in general?

1. How to use binomial theorem?
2. How to use multinomial theorem?
3. Are there any other combinatorial arguments available to solve this type of question?
• See related problem. Jan 8, 2015 at 5:20
• What could be simpler than $6^4$ multiplications? Jan 8, 2015 at 5:51

We really seek the coefficient of $x^{14}$, factoring out an $x$ from each term in the generating function. Then observe that:

$(1 + x + x^{2} + x^{3} + x^{4} + x^{5}) = \frac{1-x^{6}}{1-x}$

Now raise this to the fourth to get: $f(x) = \left(\frac{1-x^{6}}{1-x}\right)^{4}$.

We have the identities:

$$(1-x^{m})^{n} = \sum_{i=0}^{n} \binom{n}{i} (-1)^{i} x^{mi}$$

And:

$$\frac{1}{(1-x)^{n}} = \sum_{i=0}^{\infty} \binom{i + n - 1}{i} x^{i}$$

So we expand out the numerator and denominator, picking terms of $x^{14}$. Note that we are multiplying the numerator expansion by the denominator expansion.

$$\binom{14 + 4 - 1}{14}x^{14} - \binom{4}{1} \binom{8 + 4 - 1}{8} x^{14} + \binom{4}{2} \binom{2 + 4 - 1}{2} x^{14}$$

• @aes Thanks for the catch! Sorry for the careless mistake. :-) Jan 8, 2015 at 5:45

Hint: the coefficient of $x^{18}$ should be exactly the number of partitions $(i, j, k, l)$ of 18 with $1 \leq i,j,k,l \leq 6$.

• Put another way, the answer is: the number of partitions of 18 into 4 parts where each part can come from $\{1,2,3,4,5,6\}$ and repetitions are allowed. In general you can think of them like this, with some minor tweaks depending on the powers. Jan 8, 2015 at 4:39
• Partitions, perhaps? Jan 8, 2015 at 4:47
• Multi-index :-) Jan 8, 2015 at 4:48
• Right. It is not exactly the answer and partition is a correct description. Jan 8, 2015 at 4:52