8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Substituting $y_1=x_1+8$ means that, since $0<x_1<8$, you have the restriction $8 < y_1 < 16$, so I don't see how your substitution would help... $\endgroup$ – 5xum Feb 10 '16 at 13:10
  • $\begingroup$ You could try using the inclusion-exclusion principle to reduce the problem into one that only requires counting the number of solutions to similar equations, but without the upper bounds. $\endgroup$ – Yiyuan Lee Feb 10 '16 at 13:17
7
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ How is it equation (3) has more solutions, $680$, than equation (2), $455$? Shouldn't applying another constraint reduce the number of solutions? $\endgroup$ – Eric Towers Feb 10 '16 at 17:56
  • $\begingroup$ @EricTowers I applied the constraints $x_1 < 7$ and $x_2 < 5$ separately. There are fewer solutions with $x_1 \geq 8$ (equation 2) than their are solutions with $x_2 \geq 6$ (equation 3). I handled the case when both constraints were applied simultaneously in equation 4, which is why it has fewer solutions than either equation 2 or equation 3. $\endgroup$ – N. F. Taussig Feb 10 '16 at 19:40
9
$\begingroup$

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$$

$\endgroup$
  • 2
    $\begingroup$ It would be good to include some suggestions as to how to efficiently compute the relevant coefficient. $\endgroup$ – Yiyuan Lee Feb 10 '16 at 13:16
  • $\begingroup$ It's also much easier if you don't stop at $20$ for the other terms... $\endgroup$ – Thomas Andrews Feb 10 '16 at 13:42
  • 2
    $\begingroup$ I'm always amused at how this approach magically matches the inclusion-exclusion. The expansion of $(1-x^8)(1-x^6)$ is of that inclusion-exclusion form, and the coefficients of $(1-x)^{-4}$ count the "unrestricted solutions" to the original equation. $\endgroup$ – Thomas Andrews Feb 10 '16 at 13:47
  • 1
    $\begingroup$ I found this solution quite beautiful. Several enlightened steps ... Starting with reinterpreting a number theoretic question into a question of binomial theorem. Multiplying and dividing by a factor to convert a series of terms to just two terms using GP, making a product of four terms to a simple product of two. Well, done. $\endgroup$ – user230452 Feb 10 '16 at 23:49
  • 1
    $\begingroup$ @user230452 The expansion of $(1-x)^{-n}$ is $1+nx+\frac{n(n+1)}{2!}x^2+\cdots$. It could be observed that the coefficient of $x^n$ followed a pattern: it is given by $\binom{n+3}{n}$ $\endgroup$ – GoodDeeds Feb 11 '16 at 1:56
7
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.