Find the coefficient of $x^{18}$ in $(x + x^2 + x^3 + x^4 + x^5)(x^2 + x^3 + x^4 +\cdots)^5 $

Question

Find the coefficient of $x^{18}$ in $$(x + x^2 + x^3 + x^4 + x^5)(x^2 + x^3 + x^4 +\cdots)^5 $$

This is the first time coming across a generating function question and am not quite sure how to solve this and am looking for some help, thanks!

Answer 1

You can rewrite your expression as $x^{11}(1+x+x^2+x^3+x^4)(1+x+x^2+x^3+x^4+\ldots)^5$ so you are looking for the coefficient of $x^7$ in $$(1+x+x^2+x^3+x^4)(1+x+x^2+x^3+x^4+\ldots)^5$$ This is the number of ways to write $7$ as the sum of six nonnegative integers with the first being at most four. Stars and bars gives you the number without the restriction on the first as ${12 \choose 5}$. Now subtract off the number of ways to express $2,1,0$ as five nonnegative integers, so we have $${12 \choose 5}-{6 \choose 4}-{5 \choose 4}-{4 \choose 4}$$

Answer 2

Edit: So it looks like this could have been done much easier by factoring first. I'll leave this answer here in the event that this may be useful to someone with a related problem

Well we can get $x^{18}$ in our equation whenever we multiply terms together who's exponents will add to $18$. The left part of the equation will add in $1,2,3,4,5$ so we need to find the coefficients on the left side who's terms are $x^{17}, x^{16}, x^{15}, x^{14}, x^{13}$

Now to find each coefficient, we need to find all the sets of $5$ numbers in $[2,k]$ that sum to our exponents listed prior. I'll do $13$, for example. $$ 13 = 2+2+2+2+5 $$ $$ 13 = 2+2+2+3+4 $$ $$ 13 = 2+2+3+3+3 $$ Those are (hopefully I missed none), all the sums that sum to our exponent. now since these 13's can be got by multiplying any order of these terms, we need to see how many combinations these have by using the formula $\frac{n!}{k_1!k_2!...k_n!}$ so, $$ 2+2+2+2+5 \rightarrow \dfrac{5!}{4!1!} = 5 $$ $$ 2+2+2+3+4 \rightarrow \dfrac{5!}{3!1!1!} = 20 $$ $$ 2+2+3+3+3 \rightarrow \dfrac{5!}{2!3!} = 10 $$

So summing this up we get that $5+20+10=35$, therefore the coefficient in front of our term becomes $35x^{13}$. When we finally multiply that out by the right side to get $x^5\cdot35x^{13} = 35x^{18}$.

Now in order to finish the problem, you must apply this process to $x^{14}, x^{15}, x^{16}, x^{17}$, and sum their respective coefficients. Good luck!

Answer 3

Your expression can be rewritten as $$x(1+x+x^2+x^3+x^4)\cdot (x^2(1+x+x^2+x^3+\cdots)) ^5$$ $$=x(1+x+x^2+x^3+x^4)\cdot x^{10}(1+x+x^2+x^3+\cdots) ^5$$ $$=x^{11}(1+x+x^2+x^3+x^4)\cdot (1+x+x^2+x^3+\cdots) ^5$$ The two expressions in the brackets are finite and an infinite GP respectively. Hence by formula for sum of GP we have $$=x^{11}\cdot \left(\frac {1-x^5}{1-x}\right). \left(\frac {1}{1-x}\right) ^5$$ $$=x^{11}.\left (\frac {1-x^5}{(1-x)^6}\right) $$ $$=\left (\frac {x^{11}-x^{16}}{(1-x)^6}\right) $$ Now using the negative binomial series we need to find coefficient of $x^7$ and $x^2$ because we already have $x^{11} $ and $x^{16}$ in the numerator.

So using negative binomial series we get the answer as $$\binom {12}{5}- \binom {7}{2}=771$$