Looking for Distinct solutions to $x_1+x_2+x_3=100$ such that at least one of them should be greater than 40

Question

For this problem suppose that the $x_i$'s must be non-negative integers, i.e., $x_i∈{0,1,2,⋯}$ for $i=1,2,3$. How many distinct solutions does the following equation have such that at least one of the $x_i$'s is larger than 40? $$x_1+x_2+x_3=100$$ I tried using different methods but I think I got closest with advanced PIE: I thought to do it with complement, such that $20\le x_i \le 40$, because if any of them are less 20 one must be greater than 40. have in the back of your mind that without restrictions there are ${102\choose 2}$ solutions. firstly i took those $20$s and gave to all $x_i$s and got $$x_1+x_2+x_3=40$$ such that $0\le x_i \le20$ and after that did PIE method which gave me $231$ solutions. Lastly, I did what it was asking for $${102\choose 2}-231$$ I think thins answer is too big to be true, so please help me

Answer 1

By complementary counting and generating functions, this is the number of weak compositions of $100$ into $3$ parts (there is a formula in the linked article), minus the coefficient of $x^{100}$ in the expansion of $$(1+x+x^2+\cdots +x^{40})^{3}.$$ See this thread for a general way of computing such a coefficient (the formula in that link can be proven by the principle of inclusion-exclusion). Unfortunately, the overall formula that we get by this method is not closed, and I have not seen a closed form for such a problem anywhere.

Answer 2

There is no problem, your method is correct. Here is another method which gives the same answer.

The number of solutions where $x_1\ge 41$ is the same as the number of solutions to $x_1+x_2+x_3=59$, which is $\binom{61}2$. To account for $x_2$ and $x_3$ as well, you multiply by $3$. However, this double counts the solutions where $x_1\ge 41$ and $x_2\ge 41$. After subtracting these double-counted solutions, the total number is $$ 3\binom{61}2-3\binom{20}{2} $$ You can verify this gives the same answer as your method.

Answer 3

If we denote $x_1=x,\,x_2=y,\,x_3=100-x-y$ then looking at the inequalities plot we realize that all the values fits except for the shaded region $$\begin{cases} x\le 40\\ y\le 40\\ x+y\ge 60 \end{cases}$$
Which occupies $\frac{21^2+21}{2}=231$ of total $\frac{101^2+101}{2}=5151$ of $(x,y)$ values,
thus the answer is $5151-231=4920$.