10
$\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$
2
  • $\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, 2016 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, 2016 at 13:17

3 Answers 3

12
$\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$
7
  • 2
    $\begingroup$ It would be good to include some suggestions as to how to efficiently compute the relevant coefficient. $\endgroup$
    – Yiyuan Lee
    Feb 10, 2016 at 13:16
  • $\begingroup$ It's also much easier if you don't stop at $20$ for the other terms... $\endgroup$ Feb 10, 2016 at 13:42
  • 3
    $\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$ Feb 10, 2016 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$
    – Saikat
    Feb 10, 2016 at 23:49
  • 2
    $\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, 2016 at 1:56
9
$\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$
2
  • $\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$ Feb 10, 2016 at 17:56
  • 1
    $\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$ Feb 10, 2016 at 19:40
8
$\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$

Not the answer you're looking for? Browse other questions tagged .