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.
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore MAT/03 - Geometria
English
Denumerant, integer points.
http://www.dmtcs.org/pdfpapers/dmAS0197.pdf
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.
Baldoni, M; Berline, N; De Loera, J; Dutra, B; Koeppe, M; Vergne, M
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
dmAS0206.pdf

non disponibili

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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/122287
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact