1
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$ Oct 5 at 20:59
  • $\begingroup$ Exactly , I'll add it in the post $\endgroup$
    – YV558
    Oct 5 at 21:02
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I believe it should be $22-3k-j$ in your first equation. $\endgroup$ Oct 5 at 22:09
  • 1
    $\begingroup$ @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.$ $\endgroup$ Oct 5 at 22:11
  • $\begingroup$ Ah, sure. I overlooked that the number of free variables also decreases. Thanks for clarifying. $\endgroup$ Oct 5 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.