Find the coefficient of $x^{30}$ in the following polynomial $(1+x+x^2+x^3+x^4+x^6)^6$

Question

How do we find the coefficient of $x^{30}$ in the following polynomial $(1+x+x^2+x^3+x^4+x^6)^6$

My approach is as follows: $$1+x+x^2+x^3+x^4+x^5+x^6=\frac{1-x^7}{1-x}$$

hence $$\begin{align}1+x+x^2+x^3+x^4+x^6&=\frac{1-x^7}{1-x}-x^5\\&=(1-x^7-x^5+x^6)(1-x)^{-1}\end{align}$$

$$(1+x+x^2+x^3+x^4+x^6)^6=(1-x^7-x^5+x^6)^6(1-x)^{-6}.$$ It is getting complicated.

Answer 1

Consider the equation $a_1+a_2+a_3+a_4+a_5+a_6 = 30$ where $a_i$ are non-negative integers with a value at most 6. Also, none of the $a_i$ can be $5$.

Following are some hints to find the no. of solutions:

Let $m$ denote the no. of $a_i$s which are exactly 6. Is $m=0$ possible?

How many solutions for $m=1$ do you get? (Don't forget the factor of $\binom{6}{1}$). Also remember that other variables cannot be more than 5.

This can be managed by expanding $(1+x+x^2+x^3+x^4)^5 = (x^5-1)^5(x-1)^{-5}$

Proceeding similarly, find the no. of solutions for $m=2,3,4,5$.

In the end, you should get $\boxed{71}$.

Not an easy calculation, at any rate.

Answer 2

let's say one term is $$\frac{6!}{n_0!n_1n_2!n_3!n_4!n_5!n_6!}1^{n_0}x^{n_1}(x^2)^{n_2}(x^3)^{n_3}(x^4)^{n_4}(x^5)^{n_5}(x^6)^{n_6}$$ you need some terms that $$n_1+2n_2+3n_3+4n_4+5n_5+6n_6=30$$and $$n_0+n_1+\cdots+n_6=6$$

Answer 3

Continuing after this step, $$(1+x+x^2+x^3+x^4+x^6)^6=(1-x^7-x^5+x^6)^6(1-x)^{-6}.$$

Coefficient of $x^n$ in $(1-x)^{-r}$ is (n+r-1)C(r-1)

Now look at powers of the first bracket and accordingly select a power from the second bracket:

Say I take 1 from the first bracket, this means I need $x^{30}$ from $(1-x)^{-r}$ which is (30+6-1)C(6-1) = (35)C(5) and so on.

Your final answer should be 71.

Answer 4

You have already gotten algebraic and combinatorial answers. I will provide a computational/analysis inspired answer.

In engineering language this is the iterated / accumulated convolution with the kernel [1,1,1,1,1,0,1]. So you can just straight forwardly calculate just like a convolution 6 times and look at position 30.

In octave code:

k=[1,1,1,1,1,0,1];l=1;for i=1:6;l=conv(l,k,'full');endfor;l(31)

Or you can for example use the convolutional theorem of the Fourier transform and calculate the power on the Fourier coefficients.

k=[1,1,1,1,1,0,1];k2=[k,zeros(1,25)];ifft2(fft2(k2).^6)(31)

Answer 5

Write as $(x^2+1)^6(x^4+x+1)^6$

To form the $x^{30}$ term we can take

1. $x^{12}$ term from the first expansion and $x^{18}$ from the second expansion In the second expansion $x^{18}$ is obtained by choosing the $x^4$ term from some $4$ brackets and $x$ from the remaining $2$. So the contribution is $\displaystyle \binom{6}{0} \times \binom{6}{4} = 15$

2. $x^{10}$ from the first and $x^{20}$ from the second. Thats $\displaystyle \binom{6}{1} \times \binom{6}{5} = 36$ by choosing $x^4$ from some $5$ brackets

3. $x^6$ from the first and $x^{24}$ from the second which is clearly $\displaystyle \binom{6}{3} = 20$

Hence the coefficient will be $15+36+20=71$