How many non-negative integer solutions are there for the equation $ax + by + cz + … \leq C$?

Question

I've got an interesting question in combinatorics.
Given a number of constants $a$, $b$, $c$ and so on, where these constants are integers higher then one.
And there is also a constant $C$, which is also an integer higher then one. How many non-negative integer solutions are there for the equation: $$ax + by + cz + ... \leq C$$ Example: let's say we have 2 constants $a$ and $b$, with the respective values $5$ and $2$. Then there are $58$ different solutions for this equation given that $C = 30$. An example of a solution might be: $x = 0$ and $y = 0$ or $x = 5$ and $y = 2$. For this example I've graphed out all of the solutions in Geogebra with the red dots.

Could anyone maybe give some advice or give the solution to this problem. Any help would be greatly appreciated.

Answer 1

$\renewcommand{\vec}[1]{\mathbf{#1}}$ Let $\vec{a}:(\mathbb{Q}^{> 0})^{d}$ be a $d$-tuple of positive rationals. Then you're asking for the number of integral points in the rational simplex $S\subseteq \mathbb{R}^d$ defined by $$\begin{align}\vec{x}&:\mathbb{R}^d\\ \vec{x}&\geq 0\\ \vec{a}\cdot\vec{x}&\leq 1\text{.} \end{align}$$

If $d$ is allowed to vary, then counting the number of points in a rational simplex is an NP-hard problem.

On the other hand, let $N$ be the smallest positive integer such that $N/a_i\in \mathbb{Z}^{\geq 0}$ for all $i=1,2,\ldots d$. Then there exist $(d+1)$ $N$-periodic functions $$\begin{align}e_i&:\mathbb{Z}^{\geq 0}\to\mathbb{Q}\quad(i\in0,1,\ldots, d)\\ e_i(n+N)&=e_i(n)\end{align}$$ such that the number of integral points in $nS$ is given by $$\#(nS\cap\mathbb{Z}^d)=\sum_{i=0}^de_i(n)n^d\text{.}$$ The expression on the right is said to be the Ehrhart quasipolynomial of $S$.

Again, if $d$ is variable, then calculating the $e_i$ is an NP-hard problem. However, if one only wants the largest $(k+1)$ coefficients then there is a polynomial-time algorithm to calculate $e_d,e_{d-1},\ldots e_{d-k}$. Additionally, for fixed $d$ there is a polynomial-time algorithm to calculate $e_0,e_1,\ldots e_d$.

• https://mathoverflow.net/questions/10266/counting-lattice-points-on-an-n-simplex
• http://www.math.lsa.umich.edu/~barvinok/thet.pdf
• https://sites.math.washington.edu/~thomas/teaching/m583_s2008_web/Barvinok.pdf