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 Denumerant

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
  • High-performance computations with rational generating functions; Funder: National Science Foundation; Code: 0914873
  • EMSW21-VIGRE: Focus on Mathematics; Funder: National Science Foundation; Code: 0636297
  • Algebraic and Geometric Computation with Applications; Funder: National Science Foundation; Code: 0914107

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1108.4391
Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.aam.2011.12.003
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1108.4391
  • 10.48550/arxiv.1108.4391
  • 10.1016/j.aam.2011.12.003
  • 10.1016/j.aam.2011.12.003
  • 1108.4391
Formulae for the number of partitions of n into at most m parts (using the quasi-polynomial ansatz)

1 Document citing this article

Consultation statistics

This page has been seen 205 times.
This article's PDF has been downloaded 491 times.