For a given sequence $mathbf{alpha} = [alpha_1,alpha_2,dots,alpha_{N+1}]$ of $N+1$ positive integers, we consider the combinatorial function $E(mathbf{alpha})(t)$ that counts the nonnegative integer solutions of the equation $alpha_1x_1+alpha_2 x_2+cdots+alpha_{N} x_{N}+alpha_{N+1}x_{N+1}=t$, where the right-hand side $t$ is a varying nonnegative integer. It is well-known that $E(mathbf{alpha})(t)$ is a quasi-polynomial function in the variable $t$ of degree $N$. In combinatorial number theory this function is known as Sylvesters denumerant. Our main result is a new algorithm that, for every fixed number $k$, computes in polynomial time the highest $k+1$ coefficients of the quasi-polynomial $E(mathbf{alpha})(t)$ as step polynomials of $t$ (a simpler and more explicit representation). Our algorithm is a consequence of a nice poset structure on the poles of the associated rational generating function for $E(mathbf{alpha})(t)$ and the geometric reinterpretation of some rational generating functions in terms of lattice points in polyhedral cones. Our algorithm also uses Barvinoks fundamental fast decomposition of a polyhedral cone into unimodular cones. This paper also presents a simple algorithm to predict the first non-constant coefficient and concludes with a report of several computational experiments using an implementation of our algorithm in LattE integrale. We compare it with various Maple programs for partial or full computation of the denumerant.
Download