Velleda Baldoni ; Nicole Berline ; Brandon Dutra ; Matthias Köppe ; Michele Vergne et al.
-
Top Coefficients of the Denumerant
dmtcs:2373 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2013,
DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
-
https://doi.org/10.46298/dmtcs.2373
Top Coefficients of the DenumerantConference paper
Authors: Velleda Baldoni 1,2,3; Nicole Berline 4; Brandon Dutra 5; Matthias Köppe 5; Michele Vergne 6; Jesus De Loera
NULL##NULL##NULL##NULL##NULL##NULL
Velleda Baldoni;Nicole Berline;Brandon Dutra;Matthias Köppe;Michele Vergne;Jesus De Loera
5 Department of Mathematics [Univ California Davis]
6 Institut de Mathématiques de Jussieu
For a given sequence α=[α1,α2,…,αN,αN+1] of N+1 positive integers, we consider the combinatorial function E(α)(t) that counts the nonnegative integer solutions of the equation α1x1+α2x2+…+αNxN+αN+1xN+1=t, where the right-hand side t is a varying nonnegative integer. It is well-known that E(α)(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(α)(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(α)(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.