Determine how many integer solutions to the inequality $x_1+x_2+…+x_5\lt 110$

combinatoricsinclusion-exclusion

where $3\lt x_i\le 29, i=1,2$ and $10\le x_j\le 40, j=3,4.$

my work:

$x_1+x_2+…+x_6=110$ where $0\lt x_i-3\le 26, i=1,2$ and $1\le x_j-9\le 31, j=3,4$ and $0\lt x_6$

The number of solutions of the Eq. is the same as the number of the nonnegative integer solution of

$y_1+y_2+…+y_6=110-[3+3+9+9+1]=85$ where $0\lt y_i=x_i-3\le 26, i=1,2$ and $0\lt y_j=x_j-9\le 31, j=3,4$ and $0\lt y_6$

now I know that I have to get the total number of solutions and exclude the cases where $y_1,y_2\gt 26$ and $y_3,y_4\gt31 $

and this is the problem. I don't know how to do it. it's not like I'll keep assuming every case, so is there an effective way to do this.

Best Answer

This can be done with generating functions, as suggested by JMoravitz in a comment, and it's quite possible to do it with a pencil, though you'll probably want to use a calculator to do the arithmetic; I certainly did.

First, to understand the comment, note that $x_1$ and $x_2$ are each represented by the polynomial $$x^4+x^5+x^6+\dots+x^{29}.$$ This is because $4\leq x_1,x_2\leq29$. Similarly, $x_3$ and $x_4$ are each represented by the polynomial $$x^{10}+x^{11}+\dots+x^{40}.$$ Finally, $x_5$ and $x_6$ are each represented by the polynomial $$1+x+x^2+\dots+x^{109}$$ Since the sum is to be $109$, neither $x_5$ nor $x_6$ can be more than $109$, and they must be $\geq0$.

To multiply these $6$ polynomials, we choose a term from each polynomial, multiply them together, and add up the products over all choices of terms. The coefficients in the polynomials are all $1$, so the coefficient of $x^n$ in the product, for some natural number $n$, is just the number of ways to pick one term from each polynomial such that the sum of their exponents is $n$. When $n=109$, this is just the solution to our problem. For example, the solution $x_=20,x_2=14,x_3=30,x_4=30,x_5=15,x_6=0$ corresponds to choosing the terms $x^{20},x^{14},x^{30},x^{30},x^{15},1$ from the polynomials, in order.

Now it's just a matter of figuring out the coefficient of $x^{109}$ without multiplying the polynomials.

I'll use the notation $[x^n]p(x)$ to mean the coefficient of $x^n$ in the formal power series $p(x)$. We want $$c=[x^{109}]\left(x^4+\cdots+x^{29}\right)^2 \left(x^{10}+\cdots+x^{40}\right)^2 \left(1+x+x^2+\cdots\right)^2 $$ Note that we don't need an upper bound on the $x_5$ and $x_6$. It doesn't matter if we include exponents $>109$ in the polynomial, because they won't contribute anything to the coefficient of $x^{109}$ in the product. As you'll see, this simplifies the calculation, because we have two fewer factor of the numerator this way.

Then, using the formula for a geometric series,$$ \begin{align} c&=[x^{109}]\left(x^4-x^{30}\right)^2 \left(x^{10}-x^{41}\right)^2(1-x)^{-6}\\ &=[x^{81}]\left(1-x^{26}\right)^2 \left(1-x^{31}\right)^2 \sum_{n=0}^\infty\binom{-6}{n}(-x)^n\\ &=[x^{81}](1-2x^{26}+x^{52})(1-2x^{31}+x^{62}) \sum_{n=0}^{81}(-1)^n\binom{n+5}{5}(-x)^n\\ &=[x^{81}](1-2x^{26}-2x^{31}+x^{52}+4x^{57}+x^{62}) \sum_{n=0}^{81}\binom{n+5}{5}x^n\\ \end{align}$$
since we may ignore terms of degree $>81$.

We just need to pick out the terms in the product that result in a term of degree $81.$ We have $$ \binom{86}{5}-2\binom{60}5-2\binom{55}5+\binom{34}5+4\binom{29}5+\binom{24}5=17,741,536 $$