Name
Abstract | ||
|---|---|---|
For a given sequence $\mathbf{\alpha} = [\alpha_1,\alpha_2,\dots,\alpha_{N+1}]$ of $N+1$ positive integers, we consider the combinatorial function $E(\mathbf{\alpha})(t)$ that counts the nonnegative integer solutions of the equation $\alpha_1x_1+\alpha_2 x_2+\cdots+\alpha_{N} x_{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(\mathbf{\alpha})(t)$ is a quasi-polynomial function in the variable $t$ of degree $N$. In combinatorial number theory this function is known as Sylvester's 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(\mathbf{\alpha})(t)$ as step polynomials of $t$ (a simpler and more explicit representation). Our algorithm is a consequence of a nice poset structure on the poles of the associated rational generating function for $E(\mathbf{\alpha})(t)$ and the geometric reinterpretation of some rational generating functions in terms of lattice points in polyhedral cones. Our algorithm also uses Barvinok's fundamental fast decomposition of a polyhedral cone into unimodular cones. This paper also presents a simple algorithm to predict the first non-constant coefficient and concludes with a report of several computational experiments using an implementation of our algorithm in LattE integrale. We compare it with various Maple programs for partial or full computation of the denumerant. |
Year | Venue | DocType |
|---|---|---|
2015 | Integers | Journal |
Volume | ISSN | Citations |
15 | INTEGERS, vol 15 (2005), A11 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Velleda Baldoni | 1 | 39 | 4.82 |
| Nicole Berline | 2 | 29 | 3.31 |
| Jesús A. De Loera | 3 | 357 | 42.24 |
| Brandon E. Dutra | 4 | 0 | 0.34 |
| Matthias KöPpe | 5 | 191 | 20.95 |
| Michèle Vergne | 6 | 59 | 8.21 |