How many possibilities with $x_1+x_2+x_3=20$ and some restrictions on the x's?

Question

Given is $$ x_1+x_2+x_3=20$$ with $$ x_1\in\{4,5,6\}\cup\{10,11,12\} \\ 0\leq x_2 \leq 8 \\ 5 \leq x_3 \leq 10.$$

I know this has something to do with inclusion-exclusion. I was thinking the following. Let \begin{align}y_1&=x_1-4 \\ y_2 &= x_2 \\ y_3 &= x_3-5\end{align}

I know this is right for $x_2$ and $x_3$, however I'm not sure for $y_1$. If I know what this should be, I know how to use the inclusion exclusion function. Can someone help me with the $y_1$? Thanks!

Answer 1

One (and maybe cumbersome, if done by hand) approach doing it, would be to compute and check the coefficient of $x^{20}$ of the product:

$$(x^4 + x^5 + x^6+ x^{10} + x^{11}+ x^{12}) *(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8 ) * ( x^5+x^6+x^7+x^8+x^9 +x^{10}) $$

Answer 2

I'd treat this as two separate problems.

First, let $y_1 = x_1 - 4, y_2 = x_2, y_3 = x_3-5$ and count solutions to $y_1 + y_2 + y_3 = 11$ subject to $0 \le y_1 \le 2$ (which is equivalent to $4 \le x_1 \le 6$), $0 \le y_2 \le 8$, $0 \le y_2 \le 3$.

Then, let $y_1 = x_1-8, y_2 = x_2, y_3 = x_3-5$ to find those solutions where $10 \le x_1 \le 12$; I'll leave it to you to write out the details.

Answer 3

The generating function is $$(x^4+x^{10})(1+x+x^2)(1+x+\cdots +x^8)(x^5+\cdots+x^{10})$$

Which can be simplified as $$\frac{x^9(1+x^6)(1-x^3)(1-x^9)(1-x^6)}{(1-x)^3}$$

or:

$$x^9\frac{(1-x^3)(1-x^9)(1-x^{12})}{(1-x)^3}=x^9\frac{1-x^3-x^9+x^{15}+x^{21}-x^{24}}{(1-x)^3}$$

But $$\frac{1}{(1-x)^3}=\sum_{i=0}^{\infty}\binom{i+2}{2}x^i$$

Hence the coefficient of $x^n$ in your original expression is:

$$\binom{n-7}{2}-\binom{n-10}{2}-\binom{n-16}{2}+\binom{n-22}{2}+\binom{n-28}{2}-\binom{n-31}{2}$$

---

It's useful to see how the $(1+x^6)(1-x^6)=1-x^{12}$ plays out in a counting argument.

You can write the question is:

$$20 = 4+y_0+y_1+x_2+5+y_3$$

where $y_0=0,$ or $6$, and $0\leq y_1<3$, $0\leq x_2<9$ and $0\leq y_3<6$.

But if you let $y_4=y_0+y_3$, then we get that $0\leq y_4\leq 11$ and any such $y_4$ determines a unique pair $y_0$ and $y_3$. So this becomes a question of counting solutions to:

$$20 = 4+y_1+x_2+5+y_4$$

with the condition that $0\leq y_1<3, 0\leq x_2<8,0\leq y_4<12$.

Answer 4

Put $x_3=5+x_3'$. Then we have to solve $$x_2+x_3'=15-x_1\tag{1}$$ under the constraints $$0\leq x_2\leq8,\qquad 0\leq x_3'\leq5\tag{2}$$ and the given conditions on $x_1$. The latter together with $(1)$ are equivalent to$$x_2+x_3'\in\{3,4,5,9,10,11\}\ .\tag{3}$$ Drawing a figure in the $(x_2,x_3')$-plane one easily counts the number $N$ of lattice points lying in the rectangle $(2)$ and satisfying $(3)$ as $$N=4+5+6+5+4+3=27\ .$$