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 DenumerantArticle

Authors: Velleda Baldoni 1,2; Nicole Berline 3; Brandon Dutra 4; Matthias Köppe 4; Michele Vergne 5; Jesus De Loera

For a given sequence $\alpha = [\alpha_1,\alpha_2,\ldots , \alpha_N, \alpha_{N+1}]$ of $N+1$ positive integers, we consider the combinatorial function $E(\alpha)(t)$ that counts the nonnegative integer solutions of the equation $\alpha_1x_1+\alpha_2 x_2+ \ldots+ \alpha_Nx_N+ \alpha_{N+1}x_{N+1}=t$, where the right-hand side $t$ is a varying nonnegative integer. It is well-known that $E(\alpha)(t)$ is a quasipolynomial function of $t$ of degree $N$. In combinatorial number theory this function is known as the $\textit{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(\alpha)(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(\alpha)(t)$ and the geometric reinterpretation of some rational generating functions in terms of lattice points in polyhedral cones. Experiments using a $\texttt{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
  • High-performance computations with rational generating functions; Funder: National Science Foundation; Code: 0914873
  • Algebraic and Geometric Computation with Applications; Funder: National Science Foundation; Code: 0914107
  • EMSW21-VIGRE: Focus on Mathematics; Funder: National Science Foundation; Code: 0636297

1 Document citing this article

Consultation statistics

This page has been seen 270 times.
This article's PDF has been downloaded 542 times.