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 α 1 x 1 +α 2 x 2 +⋯+α N x N +α N+1 x N+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.
Baldoni, M., Berline, N., De Loera, J., Dutra, B., Koeppe, M., Vergne, M. (2013). Top degree coefficients of the denumerant. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 25th International Conference on Formal power series and Algebraic combinatorics (FPSAC 2013), 1149-1160.
Top degree coefficients of the denumerant
BALDONI, MARIA;
2013-01-01
Abstract
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 α 1 x 1 +α 2 x 2 +⋯+α N x N +α N+1 x N+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.File | Dimensione | Formato | |
---|---|---|---|
dmAS0206.pdf
solo utenti autorizzati
Descrizione: Articolo principale
Licenza:
Copyright dell'editore
Dimensione
459.22 kB
Formato
Adobe PDF
|
459.22 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.