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!
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<i_2<\cdots<i_k\}$ 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.$