Generating Functions - Counting how many solutions for an exact $x^n$

Question

Having trouble with this problem:

$$ x_1+x_2+x_3+x_4+x_5+x_6 = 13 $$ $$ x\ne 3 $$

Thanks in advance for any further help.

Being able to get to this point: $$\begin{split} f(x) &= (x^0+x^1+x^2+x^4+x^5+\cdots)^6\\ &= [(-x^3)+{x^0+x^1+x^2+(x^3)+x^4+x^5+\cdots}]^6\\ &= \left[{(-x^3)} + \frac{1}{(1-x)}\right]^6\\ &=\left[ \frac{-x^3(1-x)+1}{(1-x)}\right]^6\\ &=\left[\frac {x^4-x^3+1}{1}\cdot\frac {1}{1-x}\right]^6\\ &=(x^4-x^3+1)^6 \frac {1}{(1-x)^6}\\ \end{split}$$

Now if I long divide $(x^4-x^3+1)$ with $(1-x)$ I get $[(-x^3 + \frac {1}{1-x}) (1-x)]^6 $ thus: $$\begin{split} f(x)&=\left(\frac {1}{1-x} -x^3\right)^6 \frac {(1-x)^6}{(1-x)^6}\\ &=\left(\frac {1}{1-x} -x^3\right)^6\\ \end{split}$$

That's where I get stuck, honestly.

Answer 1

It seems the coefficient needs to be manually extracted. Using the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ we obtain

\begin{align*} \color{blue}{[x^{13}]}&\color{blue}{\left(\frac{1}{1-x}-x^3\right)^6}\\ &=[x^{13}]\sum_{k=0}^6\binom{6}{k}\frac{(-1)^kx^{3k}}{(1-x)^{6-k}}\\ &=\binom{6}{0}[x^{13}]\frac{1}{(1-x)^6}-\binom{6}{1}[x^{10}]\frac{1}{(1-x)^5}+\binom{6}{2}[x^7]\frac{1}{(1-x)^4}\tag{1}\\ &\qquad-\binom{6}{3}[x^4]\frac{1}{(1-x)^3}+\binom{6}{4}[x^{1}]{(1-x)^2}\\ &=\binom{6}{0}\binom{-6}{13}(-1)^{13}-\binom{6}{1}\binom{-5}{10}(-1)^{10}+\binom{6}{2}\binom{-4}{7}(-1)^7\\ &\qquad-\binom{6}{3}\binom{-3}{4}(-1)^4+\binom{6}{4}\binom{-2}{1}(-1)^1\tag{2}\\ &=\binom{18}{5}-6\binom{14}{4}+15\binom{10}{3}-20\binom{6}{2}+15\binom{2}{1}\tag{3}\\ &=8\,568-6\,006+1\,800-300+30\\ &\,\,\color{blue}{=4\,092} \end{align*}

Comment:

• In (1) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

• In (2) we select the coefficient $[x^k]$ from the binomial series expansion $[x^k](1-x)^{-\alpha}=[x^k]\sum_{n=0}^{\infty}\binom{-\alpha}{n}=\binom{-\alpha}{k}(-1)^k$.

• In (3) we use the binomial identity $\binom{-p}{q}(-1)^q=\binom{p+q-1}{p-1}$.

Answer 2

The P.I.E approach needs to prepare some "ingredients".

There are solutions containing $4$ "bad" $x$'s, $3, 2, 1$ or none "bad" $x$'s.

The numbers involved are the following :

$$ {6\choose 4}{2\choose 1} = 30$$ $$ {6\choose 3}{6\choose 2} = 300$$ $$ {6\choose 2}{10\choose 3} = 1800$$ $$ {6\choose 1}{14\choose 4} = 6006$$ $$ {6\choose 0}{18\choose 5} = 8568$$

For example in $ {6\choose 2}{10\choose 3} $, $ {6\choose 2} $comes by requiring to have at least two bad $x$'s, which can be any two of the six $x$'s and ${10\choose 3} $ comes from stars and bars, while placing $13-3-3$ items in $4$ slots = $ {7+4-1\choose 4-1} $

This solution was not required, but the "coincidence" is worth noting.