Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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$. –  Emmad Kareem Dec 9 '11 at 1:31

5 Answers 5

up vote 2 down vote accepted

(I assume you mean for the $x_i$ to be non-negative, else there are infinitely-many solutions.)

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 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$, which brings us back to the case with no constraints on the $x_i$.

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
Thanks a lot for the mathematica code! –  geraldgreen Dec 9 '11 at 7:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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