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.

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
add comment

1 Answer 1

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
add comment

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.