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

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.

Thanks.

• Is there some purpose for all the comments in the source? It is slightly inconvenient to see it flash by. – quid Jul 6 '15 at 10:08
• so remove all my explanations ? I want it to be comfratble to read. I wrote what I tried for solving it. – idan di Jul 6 '15 at 10:11
• Not the explanations! The lines starting with '%...' in the source! – martini Jul 6 '15 at 10:11
• I mean as @martini said this stuff % MathType! MTEF!2!1!+- % feaagKart1ev2a aatCvAUfeBSjuyZL2yd9gzLb vyNv2Ca erbuLwBLn % hiov2DGi1 BTfMBaeXatL xBI9gBaerbd9wDYLwz YbItLDharqqtubsr % 4rNCHbGeaGqiV u0Je9sqqrpepC0xbb L8F4rqqrFfpeea0xe9 Lq-Jc9 – quid Jul 6 '15 at 10:12
• this is how you seeing my messege ? – idan di Jul 6 '15 at 10:13

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?

• I'm trying to solve with this approach. so S0 = |u| = all the solution for this problem which is what you wrote . so now x1 have three balls for example then I've left with 0 0 0 0 0 0 0 (7) balls and 4 cells so -> 000 | | | | so this is D(4,7) and I have totall 5 like this so s1 = |A| +|B|+|C|+|D|+|E| = 5 * D(4,7) ? am I in the right direction ? – idan di Jul 6 '15 at 13:33
• Yes, and now you need to compute $|A_i\cap A_j|$ and to notice that there are $\binom{5}{2}$ pairs. – Ofir Schnabel Jul 7 '15 at 8:23
• yes. I solved it yestarday. thanks – idan di Jul 7 '15 at 17:18

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.

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}$$

• I know to solve this $$\frac{1}{{{{(1 - x)}^5}}} = {(1 - x)^{ - 5}} % MathType!MTEF!2!1!+- % feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaSaaaeaaca % aIXaaabaGaaiikaiaaigdacqGHsislcaWG4bGaaiykamaaCaaaleqa % baGaaGynaaaaaaGccqGH9aqpcaGGOaGaaGymaiabgkHiTiaadIhaca % GGPaWaaWbaaSqabeaacqGHsislcaaI1aaaaaaa!4292!$$ – idan di Jul 6 '15 at 10:21
• but how to solve the trinomial $${(1 - x)^{ - 5}}*{(1 - {x^3} + {x^4})^5} % MathType!MTEF!2!1!+- % feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaig % dacqGHsislcaWG4bGaaiykamaaCaaaleqabaGaeyOeI0IaaGynaaaa % kiaacQcacaGGOaGaaGymaiabgkHiTiaadIhadaahaaWcbeqaaiaaio % daaaGccqGHRaWkcaWG4bWaaWbaaSqabeaacaaI0aaaaOGaaiykamaa % CaaaleqabaGaaGynaaaaaaa!4537!$$ – idan di Jul 6 '15 at 10:23
• Added somehing @idandi – martini Jul 6 '15 at 12:03
• i+j+k = 5 means that whenever 1 = 0 so, j=1, k = 4 ? and vice versa ? I thought it will be simpler with generating functions. I guess its more practical solveing it with another method – idan di Jul 6 '15 at 12:59