For a given sequence &a;= [α1,α2,&dots;, αN,αN+1] of N+1 positive integers, we consider the combinatorial function E(&a;)(t) that counts the nonnegative integer solutions of the equation α1x1+α2 x2+⋯+αN xN+αN+1xN+1=t, where the right-hand side t is a varying nonnegative integer. It is well-known that E(&a;)(t) is a quasipolynomial function of t of degree N. In combinatorial number theory this function is known as the 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(&a;)(t) as step polynomials of t. Our algorithm is a consequence of a nice poset structure on the poles of the associated rational generating function for E(&a;)(t) and the geometric reinterpretation of some rational generating functions in terms of lattice points in polyhedral cones. Experiments using a MAPLE implementation will be posted separately.
Résumé. Considérons une liste &a;=[α1,α2,…, αN+1] de N+1 entiers positifs. Le dénumérant E(&a;)(t) est la fonction qui compte le nombre de solutions en entiers positifs ou nuls de l'équation ∑i=1N+1 xiαi=t, où t varie dans les entiers positifs ou nuls. Il est bien connu que cette fonction est une fonction quasi-polynomiale de t, de degré N. Nous donnons un nouvel algorithme qui calcule, pour chaque entier fixé k (mais N n'est pas fixé), les k+1 plus hauts coefficients du quasi-polynôme E(&a;)(t) en termes de fonctions en dents de scie. Notre algorithme utilise la structure d'ensemble partiellement ordonné des pôles de la fonction génératrice de E(&a;)(t). Les k+1 plus hauts coefficients se calculent á l'aide de fonctions génératrices de points entiers dans des cônes polyèdraux de dimension inférieure ou égale á k.