How to solve this combinations with repetitions problem using generating functions?

Question

Find the number of solutions to : $$x_1 + x_2 + x_3 + x_4 + x_5 = 10$$ where none of the variables can be the number $3$.

I can solve this with Inclusion-Exclusion Principle, but I really love solving this kind of problem with generating functions. I did not manage to solve it with generating functions , this is my try:

I have $5$ variables. None of them can be the number $3$. Need to find : coefficient of $${x^{10}}$$ so:

• $x_1$ can be : $0 , 1 , 2, 4 ,5 , 6, \ldots$ to infinity, that means:

$$1 + x + {x^2} + {x^4} + {x^5} + {x^6} + .....$$ and this is relevant for all of the five variables so thats means total: $${(1 + x + {x^2} + {x^4} + ...)^5}$$

but I can't find the generating function of this series. I tried to multiply the series by $x$ and then subtract the original series from the multiplied one $$\begin{array}{l}1 + x + {x^2} + {x^{{4^{}}}} + ...\\ - {\rm{ }}x + {x^2} + {x^3} + {x^4} + ...\end{array} $$ and I get: $${\left( {\frac{{1 - {x^3}}}{{1 - x}}} \right)^5} $$

but the final solution after I'm using binomial expansion is $1$, and that's not correct.

Can I get help please?

Thanks.

Answer 1

Note that $$ \frac{1-x^3}{1-x} = 1+x+x^2 $$ so in $(1+x+x^2)^5$ you are counting only the solutions with $0 \le x_i \le 2$ of which there is in fact only one.

Note that $$ (1-x)\sum_{i\ne 3} x^i = \sum_{i\ne 3} x^i - \sum_{i\ne 0,4} x^i = 1 + x^4 - x^3 $$ So we are left with $$ \left(\frac{1 - x^3 + x^4}{1-x}\right)^5 $$ Now do your expansion again.

---

Addendum: We have, $$ (1-x^3+x^4)^5 = \sum_{i+j+k = 5} \frac{5!}{i!j!k!} (-1)^jx^{3j+4k} $$

Answer 2

You can also use Inclusion–exclusion principle.

Without the restriction $x_i\neq 3$ you have $$\binom{10+5-1}{10}$$ solutions.

Now you need to check how many bad cases you have. Denote the set of all solutions with $x_i=3$ by $A_i$. Your bad cases are $$A_1\cup A_2\cup A_3\cup A_4\cup A_5.$$ Can you take it from here?

Answer 3

You can express your close-to-geometric sum as the difference between sums, i.e.

$$f(x)=\sum_{k\ge 0} x^k -x^3=\frac{1}{1-x}-x^3=\frac{1-x^3+x^4}{1-x}$$

Then we have

$$F(x)=\left(\frac{1-x^3+x^4}{1-x}\right)^5=\sum_{j\ge0}\binom{j+4}{4}x^j\cdot\sum_{a+b+c=5}\binom{5}{a,b,c}(-1)^bx^{3b+4c}$$

and equating coefficients we have that $10=j+3b+4c\ \to j=10-3b-4c$ and $j,b,c\ge 0$ and $b+c\le 5\ \to c\le 5-b$. So

$$[x^{10}]F(x)=\sum_{b+c\le 5}\binom{14-3b-4c}{4}\binom{5}{5-b-c,b,c}(-1)^b$$

You can simplify this sum seeing that $14-3b-4c\ge 4$ and so on.

Alternatively you can take the $[x^{10}]$ coefficient from the Maclaurin series of $F(x)$ using some CAS.