Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

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.


Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Section: Proceedings
Published on: January 1, 2013
Imported on: November 21, 2016
Keywords: Denumerants,Ehrhart quasi-polynomials,partitions,polynomial-time algorithm,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Algebraic and Geometric Computation with Applications; Funder: National Science Foundation; Code: 0914107
  • High-performance computations with rational generating functions; Funder: National Science Foundation; Code: 0914873
  • EMSW21-VIGRE: Focus on Mathematics; Funder: National Science Foundation; Code: 0636297

1 Document citing this article

Consultation statistics

This page has been seen 379 times.
This article's PDF has been downloaded 620 times.