Finding all the possibilities of solutions to an equation

given the following equation:

$$x_1+x_2+x_3+x_4+x_5=18$$

I need to find the number of solutions given the fact that

$$\forall i , x_i\geq 0 , x_i\neq 3 , x_i\neq 4$$

I tried to use generating functions by finding the coefficient of $$x^{18}$$ in the expression $$(\frac{1}{1-x}-x^3-x^4)^5$$

but I got stuck. What should I do?

Thanks in advance!

• Just to clarify: $x_i$ are non-negative integers and "$x_i \neq 3,4$" means $x_i\neq 3$ and $x_i\neq 4$? Oct 5 at 20:59
• Exactly , I'll add it in the post Oct 5 at 21:02

1 Answer

Let $$A$$ be the set of all solutions to the equation, no conditions. Let $$A_i$$ be the set of such solutions where $$x_i=3$$ or $$x_i=4.$$

Given a subset $$\{i_1 of $$\{1,2,3,4,5\}$$ then, when $$k<5$$:

$$\left|\bigcap_{m=1}^k A_{i_m}\right|=\sum_{j=0}^{k}\binom kj \binom{22-4k-j}{4-k}$$ where $$j$$ iterates over how many $$x_{i_m}=4.$$

When $$k=5,$$ there are $$\binom{5}3.$$

When $$k=4,$$ the sum is $$2^4.$$ This is because $$22-4k-j\geq0,$$ so the complex binomial is always $$1,$$ and you are just summing $$\sum_{j=0}^4\binom 4j=2^4.$$

When $$k=3,$$ the sum is:

$$\sum_{j=0}^3\binom 3j (10-j)=10\cdot 2^3-3\sum_j\binom{2}{j-1}=80-12=68.$$

Then by inclusion-exclusion, $$|A\setminus (A_1\cup \cdots \cup A_5)|=\\\binom54 2^4-\binom53-68\binom53+\sum_{k=0}^2 (-1)^{k}\binom5k\sum_{j=0}^{k}\binom{k}{j}\binom{22-4k-j}{4-k}$$

So that is down to $$6$$ terms. Still a pain, but easier.

Alternatively, write your generating function as:

$$\left(1+x+x^2+\frac{x^5}{1-x}\right)^5.$$ You can expand this with binomial theorem:

$$\sum_{k=0}^5\binom5k\frac{x^{5k}(1+x+x^2)^{5-k}}{(1-x)^k}$$ You only need $$k=0,1,2,3$$ to get $$18.$$

Noting that $$1-x^3=(1-x)(1+x+x^2)$$ you can rewrite this as: $$\frac{\sum_{k=0}^5\binom5k \sum_{j=0}^{5-k}(-1)^j\binom{5-k}jx^{5k+3j}}{(1-x)^5}$$

So you get: $$\sum_{k=0}^5\binom5k\sum_{j=0}^{5-k}(-1)^j\binom{5-k}j \binom{22-5k-3j}{4}$$

You are still going to get a double sum.

Here $$k$$ represents the number of $$x_i>4.$$

The interior sum is an inclusion-exclusion sum to count how many solutions to $$x_1+\cdots+x_5=18-5k$$ where a particular subset of size $$5-k$$ have the values $$0,1,2.$$

The interior sum is zero for $$k=4,5,$$ since $$22-5k<4$$ in those cases. But that only reduced the number of terms by $$3.$$

• I believe it should be $22-3k-j$ in your first equation. Oct 5 at 22:09
• @AndreasLenz It’s the number of ways to write $18-3k-j$ as the sum of $5-k$ numbers, so it is $$\binom{18-3k-j+(5-k)-1}{(5-k)-1}.$$ So we get an extra $-k.$ Oct 5 at 22:11
• Ah, sure. I overlooked that the number of free variables also decreases. Thanks for clarifying. Oct 5 at 22:12