# Determining number of positive integer solutions to Ax + By + Cz + Dw < Z ?

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.

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$.
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.
• @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