Skip to Main content Skip to Navigation
Conference papers

Top Coefficients of the Denumerant

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-01229687
Contributor : Alain Monteil Connect in order to contact the contributor
Submitted on : Tuesday, November 17, 2015 - 10:19:57 AM
Last modification on : Sunday, June 26, 2022 - 5:33:04 AM
Long-term archiving on: : Thursday, February 18, 2016 - 11:38:37 AM

File

dmAS0197.pdf
Publisher files allowed on an open archive

Identifiers

Citation

Velleda Baldoni, Nicole Berline, Brandon Dutra, Matthias Köppe, Michele Vergne, et al.. Top Coefficients of the Denumerant. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.1149-1160, ⟨10.46298/dmtcs.2373⟩. ⟨hal-01229687⟩

Share

Metrics

Record views

155

Files downloads

711