1
$\begingroup$

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.

All posible solutions for a = 5, b = 2 and C = 30

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

$\endgroup$
  • $\begingroup$ Ok so basically an equation like $a_1x_1+a_2x_2...+a_nx_n=c$ would be a n dimensional plane(2D plane -> a line, 3D plane -> a infinite rectangle thing). The solution will be the lattice points that are in between the plane and the origin. So for your example the points lie in between the origin and the line $5x+2y=30$. $\endgroup$ – Ariana Oct 29 '18 at 18:35
0
$\begingroup$

$\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$.

$\endgroup$
  • $\begingroup$ I've been looking at this for a couple days and I can confidently say that I do not posses the mathematical capabilities to understand the answer. It looks like you know what you're talking about and I'm 90% sure you're right, but I can't mark this answer as correct, because of that. Thanks for your answer still. If you want to simplify your answer then it might be good to know that I have a highschool level of maths knowledge: I know what an integral, but that's probably the most advanced think I've learned. $\endgroup$ – Trashtalk Oct 28 '18 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.