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.
Best Answer
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.