# Counting number of solutions with restrictions

I want to count the number of non-negative integer solutions to an equation such as

$$x+5y+8z=n$$

I can do this using generating functions; for example, the answer here is

$$[x^n]\frac{1}{(1-x)(1-x^5)(1-x^8)}$$ where $[x^n]$ is the coefficient of $x^n$.

But what if I add a restriction between variables such as $y \le z$? I have no idea how to count the number of solutions with this additional constraint. Any suggestions?

## 1 Answer

If you want $y\leq z$, use the substitution $z = y + z'$, and you're solving $x + 5y + 8(y+z') = n$, which is equivalent to non-negative integer solutions for $x + 13y + 8 z' = n$.

If you want $x\leq y \leq z$, a similar method will work. You could also do this for $2y \leq z$.

Of course, with more restrictions, this can get harder to clearly do. It could be difficult to solve subject to $x \leq y, z \leq 2y, x \geq \pi z$ (assuming any solutions exist).

• Perfect, just what I was looking for. – user79913 May 28 '13 at 20:17