Tell me more ×
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.
up vote 1 down vote favorite

I would like a method to determine the number of positive integer solutions for an linear inequality, of the form:
$Ax + By + ... < Z$ given integer A,B, .. Z and integer $x,y,z,w \ge 0$

For example, there are 11 solutions to $3x + 5y < 15$

I know this is similar to the existing question ( Count the number of positive solutions for a linear diophantine equation ). However, I am unclear about extending it to cover the inequality - Do I need to apply the formula for each 0 .. Z ? Also, it seems difficult to go from even $Ax + By = N$ to $y + z = n$ while remaining in integers.

share|improve this question
Your $2$-dimensional question could be reformulated as counting the number of lattice points in the triangle with corners $(x,y) = \{(0,0), (5,0), (0,3)\}$, but without counting the points on the long diagonal. In that case it is one less than half of the number of lattice points in the rectangle formed by those points and $(5,3)$, which contains $24$ points, so then it is $11$. – TMM Sep 5 '11 at 18:49
In $2$ dimensions you could generalize this for arbitrary $A, B, Z$, but for higher dimensions it becomes harder I think. – TMM Sep 5 '11 at 18:53

1 Answer

up vote 2 down vote

The number of positive solutions of $3x+5y<15$ is the same as the number of positive solutions of $3x+5y+z=15$. The same "trick" works in general. Thus (apart from an increase of $1$ in the number of variables), there is no great difference between $<K$ and $= K$.

The real problems, whether one is dealing with equality or inequality, come from the implicit congruential restrictions.

There are a number of ideas that one can use, none very pleasant. It is useful to reformulate the problem so that we are looking for non-negative solutions. Then we can use generating functions to obtain an explicit $F(t)$ such that, for any $n$, the number of solutions with right-hand side equal to $n$ is the coefficient of $t^n$ in the power series expansion of $F(t)$. That is unfortunately not necessarily a practical computational tool for finding an exact answer.

share|improve this answer
"come from the implicit congruential restrictions": Are you talking about the equality case here? Can you give a concrete example? – Srivatsan Sep 6 '11 at 5:39
@Srivatsan Narayanan: Consider $2x+3y \le n$ or equivalently $2x+3y+z=n$, non-negative solutions. The number of solutions is not too hard to compute. But we get $6$ slightly different "formulas," for $n congruent to $0$, $1$, $\dots 5$ (modulo $6$). – André Nicolas Sep 6 '11 at 10:43

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.