Counting with rational generating functions (Q2474247)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Counting with rational generating functions |
scientific article |
Statements
Counting with rational generating functions (English)
0 references
5 March 2008
0 references
The authors study two ways of encoding a counting function \(c : {\mathbb Z}^d \to {\mathbb Q}\). The first is in the form of a rational generating function \[ \sum_{ m \in {\mathbb Z}^d } c(m) \, x^m = \sum_{ i \in I } \alpha_i {{ x^{ p_i } } \over { \left( 1 - x^{ a_{ i1 } } \right) \cdots \left( 1 - x^{ a_{ is } } \right) }} , \] where \(I\) is finite, \(\alpha_i \in {\mathbb Q}\) and \(p_i, a_{ ij } \in {\mathbb Z^d}\). Here we use the multinomial notation \(a^b = a_1^{ b_1 } \cdots a_k^{ b_k }\) for vectors \(a = (a_1,\dots,a_k)\) and \(b = (b_1,\dots,b_k)\). The second form of encoding \(c\) is in form of a step-polynomial \[ c(m) = \sum_{ j=1 }^n \alpha_j \prod_{ k=1 }^{ d_j } \left\lfloor \langle a_{ jk } , m \rangle + b_{ jk } \right\rfloor , \] where \(\alpha_j, b_{ jk } \in {\mathbb Q}\) and \(a_{ ij } \in {\mathbb Q}^d\). Examples of such counting functions include Ehrhart quasipolynomials (integer-point enumeration in rational polyhedra) and their variants, such as vector partition functions. The main result of the paper is that, if the degree and number of input variables of the (quasi-polynomial) function \(c\) are fixed, there is a polynomial-time algorithm that converts between the two representations. The main tool in the proof of this result is Barvinok's algorithm [\textit{A. I. Barvinok}, Discrete Comput. Geom. 12, No. 1, 35--48 (1994; Zbl 0804.52009)].
0 references
rational generating functions
0 references
piecewise quasi-polynomials
0 references
vector partition functions
0 references
parametric counting functions
0 references
parametric polytopes
0 references
Barvinok algorithm
0 references