×

On the number of nonnegative integer solutions of a system of linear Diophantine equations. (English) Zbl 0477.90048

Ann. Discrete Math. 11, 95-108 (1981).
Two assertions are proved about the number \(\nu(k)\) of integer points in the polyhedron \[ a_1x_1+\dots+a_nx_n = k,\quad a_1, \dots, a_n,\, k\in\mathbb Z^n,\;x_1, \dots, x_n\in\mathbb R_+\,. \]
Theorem 1. There exists a partition \(\mathbb R^n=\bigcup_{i=1}^N C_i\), where \(C_i\) is a cone with integer generators and with the vertex in 0 such that \(\nu(k)|_{C_i\cap\mathbb Z^n}\) is either infinity or a quasipolynomial.
Theorem 2. If in addition the matrix \((a_1, \dots, a_n)\) is totally unimodular, then \(\nu(k)|_{C_i\cap\mathbb Z^n}\) is either infinity or a polynomial.
For the entire collection see [Zbl 0465.00007].
Reviewer: M. Frumkin

MSC:

11D04 Linear Diophantine equations
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI