## 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; Nicole Berline 2; Brandon Dutra 3; Matthias Köppe 3; Michele Vergne 4; Jesus De Loera

• 1 Università degli Studi di Roma Tor Vergata [Roma]
• 2 Centre de Mathématiques Laurent Schwartz
• 3 Department of Mathematics [Univ California Davis]
• 4 Institut de Mathématiques de Jussieu

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
• 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

## Publications

Is related to
• 1 ScholeXplorer