How many solutions for an equation with simple restrictions

Question

I'm working on an assignment in which I have to count the number of solutions for this particular equation: $$x_1+x_2+x_3+x_4=20$$for non negative integers with $x_1<8 $ and $x_2<6$

I'm aware that this kind of a task isn't that complicated, but I don't get combinatorics in general that well.

So I've tried two following approaches to get this done.

Firstly I tried to substitute the variable x:

$x_1+x_2+x_3+x_4=20 \Leftrightarrow y_1+y_2+y_3+y_4=34$

in which $y_1=x_1+8$ and $y_2=x_2+6$ (casue $x_1=y_1-8$ and $x_2=y_1-6$) Following this approach the total number of possible solutions would be

$${34+3 \choose 3} $$

But I'm not sure if its the right solution.

The second approach is to sum all of the possible values that $x_1$ and $x_2$ could possibly take, also $x_1=0,1,2,3,4,5,6,7$ and $x_2=0,1,2,3,4,5,6$ And then count all the possibilities for each of the variables $${20 -x_1-x_2+1\choose 1}$$ and sum them together like this: $${21\choose 1}+{20\choose 1}+{19\choose 1}+{18\choose 1}+... $$ and so on...

I'm sure I'll get the correct number with this one, but I'm not feeling like summing all of this possibilities. There's got to be a better, more elegant way to deal with this.

My professor gave me a hint that I should do it using the complement.

Answer 1

To determine the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 = 20 \tag{1}$$ in the non-negative integers subject to the restrictions $x_1 < 7$ and $x_2 < 6$, we subtract the number of solutions in which $x_1 > 7$ or $x_2 > 5$ from the number of solutions of the equation.

A particular solution of equation 1 corresponds to the placement of three addition signs in a row of $20$ ones. For instance, $$1 1 1 1 + 1 1 1 1 1 + 1 1 1 1 1 1 + 1 1 1 1 1$$ corresponds to the solution $x_1 = 4$, $x_2 = 5$, $x_3 = 6$, and $x_4 = 5$, while $$+ 1 1 1 1 1 1 1 1 1 + 1 1 1 1 1 1 1 + 1 1 1 1$$ corresponds to the solution $x_1 = 0$, $x_2 = 9$, $x_3 = 7$, and $x_4 = 4$. Thus, the number of solutions of equation 1 is the number of ways three addition signs can be inserted into a row of $20$ ones, which is $$\binom{20 + 3}{3}$$ since we must choose which three of the $23$ symbols ($20$ ones and $3$ addition signs) will be addition signs.

Suppose $x_1 > 7$. Then $y_1 = x_1 - 8$ is a non-negative integer. Substituting $y_1 + 8$ for $x_1$ in equation 1 yields \begin{align*} y_1 + 8 + x_2 + x_3 + x_4 & = 20\\ y_1 + x_2 + x_3 + x_4 & = 12 \tag{2} \end{align*} Equation 2 is an equation in the non-negative integers with

$$\binom{12 + 3}{3} = \binom{15}{3}$$

solutions.

Suppose $x_2 > 5$. Then $y_2 = x_2 - 6$ is a non-negative integer. Substituting $y_2 + 6$ for $x_2$ in equation 1 yields \begin{align*} x_1 + y_2 + 6 + x_3 + x_4 & = 20\\ x_1 + y_2 + x_3 + x_4 & = 14 \tag{3} \end{align*} Equation 3 is an equation in the non-negative integers with

$$\binom{14 + 3}{3} = \binom{17}{3}$$

solutions.

If we subtract the number of solutions of equation 2 and equation 3 from the number of solutions of equation 1, we will have subtracted those solutions in which $x_1 > 7$ and $x_2 > 5$ twice. Thus, we must add the number of solutions in which $x_1 > 7$ and $x_2 > 5$.

Suppose $x_1 > 7$ and $x_2 > 5$. Then $y_1 = x_1 - 8$ and $y_2 = x_2 - 6$ are non-negative integers. Substituting $y_1 + 8$ for $x_1$ and $y_2 + 6$ for $x_2$ in equation 1 yields \begin{align*} y_1 + 8 + y_2 + 6 + x_3 + x_4 & = 20\\ y_1 + y_2 + x_3 + x_4 & = 6 \tag{4} \end{align*} Equation 4 is an equation in the non-negative integers with

$$\binom{6 + 3}{3} = \binom{9}{3}$$

solutions.

By the Inclusion-Exclusion Principle, the number of solutions of equation 1 in the non-negative integers subject to the restrictions that $x_1 < 7$ and $x_2 < 6$ is

$$\binom{23}{3} - \binom{15}{3} - \binom{17}{3} + \binom{9}{3}$$

Answer 2

One way of looking at it is this: The number of ways is just the coefficient of $x^{20}$ in the expansion of $$(1+x+x^2+\cdots+x^7)(1+x+x^2+\cdots+x^5)(1+x+x^2+\cdots+x^{20})^{2}$$

Here, each factor represents a term in your equation (here I have written them in the same order). The powers of $x$ in the factor are the values the corresponding variable can take. I limited the last two factors to a maximum power of $20$ as all the terms are non negative.

Now, the logic behind this is that when you multiply two powers of $x$, the powers add up. The coefficient of $x^{20}$ gives the number of ways you could have multiplied various powers from each factor to get a total power of $20$. Notice that each combination of powers from each factor contributes to an increase of one in the coefficient and also represents a unique solution to your equation. Thus, the coefficient of $x^{20}$ in the binomial expansion gives the desired answer.

Each factor can be simplified by using the formulae for the sum of terms in a geometric progression. Then, the $(1-x)^{-n}$ terms can be expanded using the binomial expansion, after which the coefficient can be found easily.

$$(1+x+x^2+\cdots+x^7)(1+x+x^2+\cdots+x^5)(1+x+x^2+\cdots+x^{20})^{2}=\frac{(1-x^8)(1-x^6)(1-x^{21})^2}{(1-x)^4}$$

So, you need to find the coefficient of $x^{20}$ in the expansion of $$(1-x^8)(1-x^6)(1-x)^{-4}$$ The $(1-x^{21})^2$ term can be ignored, as terms with coefficient higher than $20$ are not of any concern. $$(1-x^8)(1-x^6)(1-x)^{-4}=(1-x^6-x^8+x^{14})(1+4x+10x^2+20x^3+\cdots+84x^{6}+\cdots+455x^{12}+\cdots+680x^{14}+\cdots+1771x^{20}+\cdots+\binom{n+3}{n}x^n+\cdots)$$ The coefficient is thus: $$1771-455-680+84=720$$

Answer 3

The classic way to do this is count the solutions without conditions, then use inclusion-exclusion to deal the cases which violate.

So if $A$ is the set of all non-negative solutions to $x_1+x_2+x_3+x_4=20$, and $A_1$ is the set of such solutions with $x_1\geq 8$ and $A_2$ is the set of solutions with $x_2\geq 6$ then the set you seeking to count is $A\setminus(A_1\cup A_2)$ and:

$$\left|A\setminus(A_1\cup A_2)\right|=|A|-|A_1|-|A_2|+|A_1\cap A_2|$$

By inclusion-exclusion. Now, each of these terms is much easier to compute. For example, $A_1\cap A_2$ is the set of solutions to $x_1+x_2+x_3+x_4=20$ with $x_1\geq 8,x_2\geq 6$, which is equal to the set of non-negative solutions to $y_1+y_2+x_3+x_4=20-14=6$.