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 <>
Submitted on : Tuesday, November 17, 2015 - 10:19:57 AM
Last modification on : Monday, December 14, 2020 - 9:41:56 AM
Long-term archiving on: : Thursday, February 18, 2016 - 11:38:37 AM

File

dmAS0197.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01229687, version 1

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. ⟨hal-01229687⟩

Share

Metrics

Record views

295

Files downloads

1260