# Count the number of integer solutions to $x_1+x_2+\cdots+x_5=36$

How to count the number of integer solutions to $x_1+x_2+\cdots+x_5=36$ such that $x_1\ge 4,x_3 = 11,x_4\ge 7$

And how about $x_1\ge 4, x_3=11,x_4\ge 7,x_5\le 5$

In both cases, $x_1,x_2,x_3,x_4,x_5$ must be nonnegative integers.

Is there a general formula to calculate things like this?

• I think that if you re-write the question as Maximize: x1+x2+x3+x4+x5-36 where $x_i$ > 0 and $x_1\ge 4, x_3=11,x_4\ge 7,x_5\le 5$, you could use the linear programming method called Simplex method to find values of $x_i$. – NoChance Dec 9 '11 at 1:31

Suppose you had no constraints on the $x_i$. Your problem is addressed by the "Stars and Bars" method (or, if you do not wish to count the order of your summands, the Partition Function).

Now, your first question can be reduced to the question with no constraints by asking:

What is the number of non-negative integer solutions to $x_1 + x_2 + x_4 + x_5 = 14$?

What I did was set $x_3 = 11$ and subtract 11 from the righthand side and remove $x_3$ from consideration, since we may as well regard $x_3$ as a constant.

For $x_1$ and $x_4$, subtract 4 and 7, respectively, from the righthand side. Now we care only that $x_1 \geq 0$ and $x_4 \geq 0$. In other words, we want the number of non-negative integer solutions to $x_1 + x_2 + x_4 + x_5 = 14$.

To take care of a constraint like $x_5 \leq 5$, first find the number of solutions with no constraints on $x_5$. Then, find the number of solutions with $x_5 \geq 6$. Subtract the latter from the former.

In all your case, essentially we want to find the number of natural number solutions for the following equation:

$$\displaystyle \sum_{i=1}^{n} a_i = N$$ where $a_i \in \mathbb{N}$

The method is as follows:

Consider $N$ sticks.

$| | | | | | | | ... | | |$

We want to do partition these $N$ sticks into $n$ parts.

This can be done if we draw $n-1$ long vertical lines in between these $N$ sticks.

The number of gaps between these $N$ sticks is $N-1$.

So the total number of ways of drawing these $n-1$ long vertical lines in between these $N$ sticks is $C(N-1,n-1)$.

So the number of natural number solutions for $\displaystyle \sum_{i=1}^{n} a_i = N$ is $C(N-1,n-1)$.

If we are interested in the number of non-negative integer solutions, all we need to do is replace $a_i = b_i - 1$ and count the number of natural number solutions for the resulting equation in $b_i$'s.

i.e. $\displaystyle \sum_{i=1}^{n} (b_i - 1) = N$ i.e. $\displaystyle \sum_{i=1}^{n} b_i = N + n$.

So the number of non-negative integer solutions to $\displaystyle \sum_{i=1}^{n} a_i = N$ is given by $C(N+n-1,n-1)$.

First things first. Let's take $x_3$ out of the equation, leaving us with $x_1+x_2+x_4+x_5=25$. For the first problem, I'm going to assume $x_2$ and $x_5$ are non-negative, otherwise, I think we're going to have infinite solutions. We know $x_1$ is at least 4 and $x_4$ is at least 7, so that gives us a total of 14 to distribute to the 4 different variables.

To represent the distribution of these 14 items, let's use a string of 0's and 1's. So for example, 00010001000100000 represents $x_1=4+3=7,x_2=3,x_4=7+3=10$, and $x_5=5$. The 1's are dividers. So we have 14 0's for the 14 items and 3 dividers. So we have a string of size 17 and we want to set 3 of the characters to 1. The number of such strings is $\binom {17}{3}$.

Here is an approach to understanding your problem in greater generality.

Suppose we would like to count the number of non-negative and ordered integer solutions of the Diophantine equation $x_1 + x_2 + x_3 + x_4 + x_5 = 36$ with the following additional constraints: $x_1 \geq 4$, $x_3 = 11$ and $x_4 \geq 7$. First, as my colleague Mike suggests, let's subtract $x_3$ from both sides. We are then to count: $x_1 + x_2 + x_4 + x_5 = 25$ given said constraints.

I prefer to think about this problem combinatorially in terms of lattice points of dilated polytopes. The unconstrained inequality $x_1 + x_2 + x_4 + x_5 \leq R$ represents the number of non-negative lattice points of the $R$-dilate of the polytope $\mathbf{conv}(\mathbf{0}, \mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3, \mathbf{e}_4)$, which is bounded by a $4$-simplex or pentachoron and the natural boundaries of the positive orthant, where $\mathbf{e}_i$ represents the $i^{\text{th}}$ basis of $\mathbb{R}^{4}$. For simplicity, we'll just call this object a simplicial $4$-polytope $P$.

It is clear that the number non-negative solutions of $x_1 + x_2 + x_4 + x_5 = R$ is found by considering the inequality $R - 1 < x_1 + x_2 + x_4 + x_5 \leq R$ which can be determined by simply subtracting the number of lattice points of two consecutive dilates of the same pentachoron. That said, the number of non-negative lattice points of an $R$-dilate of $P$ is the iterated sum, \begin{align} N(R) = \sum_{i_1 = 0}^{R} \sum_{i_2 = 0}^{R - i_1} \sum_{i_3 = 0}^{R - i_1 -i_2} \sum_{i_4 = 0}^{R - i_1 -i_2 -i_3} 1 = \binom{R + 4}{R}. \end{align} So, with no constraints, we have the following number of non-negative solutions: \begin{align} \binom{R+4}{R} - \binom{R + 3}{R - 1}. \end{align} To account for the constraints, we modify the various limits of summation accordingly, \begin{align} N(R) = \sum_{i_1 = 4}^{R} \sum_{i_2 = 0}^{R - i_1} \sum_{i_3 = 7}^{R - i_1 -i_2} \sum_{i_4 = 0}^{ R-i_1 - i_2 - i_3} 1. \end{align} So the answer to your first question (without a constraint on $x_5$) is therefore $N(25) - N(24)$, which is $680$. To account for the constraint on $x_5$, we further modify the innermost summation, \begin{align} N(R) = \sum_{i_1 = 4}^{R} \sum_{i_2 = 0}^{R - i_1} \sum_{i_3 = 7}^{R - i_1 -i_2} \sum_{i_4 = 0}^{ \min(5, R-i_1 - i_2 - i_3)} 1. \end{align} The answer to your second question is therefore $N(25) - N(24)$, which is $515$.

To compute the solutions explicitly, use the following mathematica code:

FindInstance[x1 + x2 + x4 + x5 == 25 && x1 >= 4 && x2 >= 0 && x4 >= 7 && x5 >= 0, {x1, x2, x4, x5}, Integers, 1000]}

FindInstance[x1 + x2 + x4 + x5 == 25 && x1 >= 4 && x2 >= 0 && x4 >= 7 && 5 >= x5 >= 0, {x1, x2, x4, x5}, Integers, 1000]}

Compute the "Length[]" of the output and you can verify that there are indeed $680$ and $515$ integral solutions, respectively.

• Thanks a lot for the mathematica code! – geraldgreen Dec 9 '11 at 7:17

$\infty$, if you have no constraint on $x_2$ and $x_5$ other than that they are integers: note that you can always add $1$ to one of these and subtract $1$ from the other. Or did you mean nonnegative (or positive) integers?