1
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "come from the implicit congruential restrictions": Are you talking about the equality case here? Can you give a concrete example? $\endgroup$
    – Srivatsan
    Commented Sep 6, 2011 at 5:39
  • $\begingroup$ @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$). $\endgroup$ Commented Sep 6, 2011 at 10:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .