Number of solutions to 3-variable sums with restrictions

Question

I came across the following problem

1) How many solutions does the equation $x_1+x_2+x_3=8$ have with integers $x_i\ge0$?

There are $9$ possible values for $x_1$. For each of those, there are $9-x_1$ possible values for $x_2$. And for each of those, there is only $1$ possible value for $x_3$. So To find the total number of solutions, we can sum the number of values for $x_2$ over the actual values of $x_1$.

$$ N=\sum_{x_1=0}^{8}(9-x_1)\cdot1=1+2+3+4+5+6+7+8+9=45 $$

The next two problems were identical, but with added restrictions.

2) How many solutions are there for problem (1) if $x_1\ge2$ and $x_3\ge3$?

3) How many solutions are there for problem (1) if $x_1\le2$ and $x_3\le3$?

Noticing that $N$ must not be too big, I found $N=10$ and $N=12$ by writing out tables of valid solutions. I am not a fan of brute force, however, and I am sure there is a better way of doing this, perhaps involving combinations. I did find this, which is a possible duplicate question, but I didn't quite follow the technique for counting solutions using generator functions. Got any hints to point me in the right direction?

Answer 1

Solving the equation $x_1 + x_2 + x_3 = 8$ involves determining how many ways two plus signs can be placed in a list of eight 1's. For instance, the list

$$1 1 1 + + 1 1 1 1 1$$

corresponds to the solution $x_1 = 3, x_2 = 0, x_3 = 5$, while

$$1 + 1 1 1 1 + 1 1 1$$

corresponds to the solution $x_1 = 1, x_2 = 4, x_3 = 3$. The number of such lists that can be formed is

$$\binom{8 + 2}{2} = \binom{10}{2} = \frac{10!}{8!2!} = \frac{10 \cdot 9}{2} = 45$$

To solve the problem $x_1 + x_2 + x_3 = 8$ subject to the restrictions $x_1 \geq 2$ and $x_3 \geq 3$, let

\begin{align*} y_1 & = x_1 - 2\\ y_2 & = x_2\\ y_3 & = x_3 - 3 \end{align*}

Then $x_1 = y_1 + 2$ and $x_3 = y_3 + 3$, so we obtain \begin{align*} y_1 + 2 + y_2 + y_3 + 3 & = 8\\ y_1 + y_2 + y_3 & = 3 \end{align*}

Applying the same method we used above to the equation $y_1 + y_2 + y_3 = 3$ gives

$$\binom{3 + 2}{2} = \binom{5}{2} = 10$$

solutions in the non-negative integers.

To solve the problem $x_1 + x_2 + x_3 = 8$ in the non-negative integers subject to the restrictions $x_1 \leq 2$ and $x_3 \leq 3$, we must subtract the number of solutions in which $x_1 \geq 3$ or $x_3 \geq 4$ from the $45$ solutions of the equation in the non-negative integers. To do so, we subtract the number of solutions in which $x_1 \geq 3$ and the number of solutions in which $x_3 \geq 4$, then add the number of solutions in which both $x_1 \geq 3$ and $x_3 \geq 4$ since those solutions would otherwise be subtracted from the total number of solutions twice.

The number of solutions of the equation $x_1 + x_2 + x_3 = 8$ in which $x_1 \geq 3$ is the number of solutions of the equation \begin{align*} y_1 + 3 + y_2 + y_3 & = 8\\ y_1 + y_2 + y_3 & = 5 \end{align*} in the non-negative integers, which is $$\binom{5 + 2}{2} = \binom{7}{2} = 21$$ The number of solutions of the equation $x_1 + x_2 + x_3 = 8$ in which $x_3 \geq 4$ is the number of solutions of the equation \begin{align*} y_1 + y_2 + y_3 + 4 & = 8\\ y_1 + y_2 + y_3 & = 4 \end{align*} in the non-negative integers, which is $$\binom{4 + 2}{2} = \binom{6}{2} = 15$$ The number of solutions of the equation $x_1 + x_2 + x_3 = 8$ in which $x_1 \geq 3$ and $x_3 \geq 4$ is the number of solutions of the equation \begin{align*} y_1 + 3 + y_2 + y_3 + 4 & = 8\\ y_1 + y_2 + y_3 & = 1 \end{align*} in the non-negative integers, which is $$\binom{1 + 2}{2} = \binom{3}{2} = 3$$ Hence, the number of solutions of the equation $x_1 + x_2 + x_3 = 8$ in the non-negative integers in which $x_1 \leq 2$ and $x_3 \leq 3$ is $45 - 21 - 15 + 3 = 12$.

Answer 2

I definitely favor generating functions.

The way they work is multiplication of powers of $x$ turns into addition of exponents. In this way, you can easily encode partition (summing) problems as multiplications of polynomials.

Your original problem involves asking how many ways you can sum 3 numbers and get 8. So we want to get $x^8$ from $x^j$, $x^k$, $x^\ell$ (that is $x^{j+k+\ell}=x^8$). We should let $j,k,$ and $\ell$ take on values between $0$ and $8$ so $1=x^0,\dots,x^8$ are possibilities for $x^j$ (and so forth). Multiplying out: $$(1+x+\cdots+x^8)(1+x+\cdots+x^8)(1+x+\cdots+x^8) = 1+\cdots+45x^{8}+\cdots$$ This tells us that a power from the first factor times a power from the second factor times a power from the third factor can out to be $x^8$ in 45 different ways. See Wolfram Alpha's Result for the full expansion.

Now it's easy to encode your other problems. What if $x_1\geq 2$ and $x_2 \geq 3$? Well then in the first factor we should remove terms corresponding to $x_1=0$ and $1$ and we should remove terms corresponding to $x_2=0,1,$ and $2$ from the second factor. So we're interested in: $$(x^2+\cdots+x^8)(x^3+\cdots+x^8)(1+x+\cdots+x^8) = 1+\cdots+10x^{8}+\cdots$$ [See Alpha again for the complete expansion.] So the answer is "There are 10 solutions if the first variable is at least 2 and the third is at least 3."

You should easily be able to adapt the method to solve your other problem. :)

Alternatively notice that if $x_1 \geq 2$ and $x_2 \geq 3$ then we can recast this problem as $x_1=x_1'+2$ and $x_2=x_2'+3$ where $x_1',x_2' \geq 0$. Now look for $x_1+x_2+x_3=8$ so $x_1'+x_2'+x_3=3$. Thus the coefficient of $x^3$ in the first expansion is the number of solutions (again it's 10).