How do I find coefficient of $x^{10}$ in $(1+x+x^2+...+x^6)^3$

Question

Well my actual question was:

Q1. How do I find coefficient of $x^4$ in $(1+x+x^2)^3$

Of course I can enumerate the combinations and quickly realized that its 6: $$\{x.x.x^2,x^2.x.x,x.x^2.x,x^2.x^2.1,1.x^2.x^2,x^2.1.x^2\}$$

But I want to know if there are any neat set of steps with which I can come up with straight combinatorial formula (as I do in below problem), so that I can prepare such formula for higher power problems as stated in the title of the post.

If I take the problem:

Find coefficient of $x^2$ in $(1+x+x^2)^4$

Its easy. I will find that, we have to find coefficient of $x^2$. Here the power is 2 which same as biggest power in series $1+x+x^2$. So instead of $(1+x+x^2)^4$, I will consider $(1+x+x^2+...)^4$

$$(1+x+x^2+...)^4=\frac{1}{(1-x)^4}=\sum_{k=0}^\infty \binom{3+k}{3}x^k$$

So I have to find coefficient of $x^k$ for $k=2$ which is $\binom{3+2}{3}=10$.

However in Q1., power 4 of $x^4$ is bigger than the max power 2 in series. So I cannot consider infinite series (instead of finite) as it will add additional combinations such as $x.1.x^3$

My textbook gives tricky solution for this, such as dividing and multiplying the series with $(1-x)^3$ (which I dont find intuitive) and doing further unintuitive adjustments.

Is there any intuitive or more importantly, works-for-all-problems approach?

Answer 1

$(1+x+x^2)^3 = \left(\frac{1-x^3}{1-x}\right)^3 = (1-x^3)^3 \frac{1}{(1-x)^3} = (1-3x^3 + 3x^6 - x^9)(\sum_{n=}^\infty \binom{n+2}{2}x^n)$ and so we can make the coefficient of $x^4$ from $1 \cdot \binom{4+2}{2}$ and $-3\binom{2+1}{2}$ and this equals $15 - 3\cdot 3 = 6$

Answer 2

The combinatorial way to approach this is to use inclusion-exclusion. You want to count the number of ways to write $10=x_1+x_2+x_3$ with $0\leq x_i\leq 6$.

We know how to count the number of solutions without the restriction - it is $\binom{10+2}{2}$.

Let $A$ be the set of all solutions with no upper bound on the size of the $x_i$.

Let $A_i$ be the solutions in $A$ with $x_i\geq 7$.

Then you want to compute:

$$|A\setminus (A_1\cup A_2\cup A_3)|$$

Which is a standard inclusion-exclusion situation. Since $A_i\cap A_j=\emptyset$ for any $i\neq j$, you get a simple formula:

$$|A\setminus (A_1\cup A_2\cup A_3)|=|A|-|A_1|-|A_2|-|A_3|$$

But the $A_i$ all have the same size, which is the number of solutions to $x_1+x_2+x_3=10-7$ with no restriction on size.

So you get:

$$\binom{10+2}{2}-3\binom{3+2}{2}$$

More generally, for the coefficient of $x^n$ you'd have to add back in the $|A_i\cap A_j|$ and subtract $|A_1\cap A_2\cap A_3|$.

Answer 3

I will use the standard notation $[x^n]\,f(x)$ for denoting the coefficient of $x^n$ in the Taylor series of $f(x)$ centered at the origin. We have:

$$ [x^{10}](1+x+\ldots+x^6)^3 = [x^{10}]\frac{(1-x^7)^3}{(1-x)^3} \tag{1}$$ and the RHS of $(1)$ is simple to compute by convolution, since both the Taylor series of $(1-x^7)^3$ and $\frac{1}{(1-x)^3}$ are well-known: the first one is an instance of the binomial theorem, the latter follows from stars and bars:

$$ \frac{1}{(1-x)^3} = \sum_{n\geq 0}\binom{n+2}{2}x^n \tag{2}$$

and the coefficient of $x^{10}$ in the following product

$$ \left(\sum_{n=0}^{3}\binom{3}{n}(-1)^n x^{7n}\right)\cdot\left(\sum_{n\geq 0}\binom{n+2}{2}x^n\right) \tag{3} $$ is given by the following Cauchy product/convolution: $$ \sum_{n=0}^{1}\binom{3}{n}(-1)^n\binom{(10-7n)+2}{2}=36.\tag{4} $$

This approach can be applied for finding $[x^a](1+x+\ldots+x^b)^c$ too.