Counting with rational generating functions

Details Counting with rational generating functions Counting with rational generating functions

2005-04-04

arxiv.org/abs/math/0504059v2

Mathematics

Combinatorics

25 pages; revised version has significant changes to exposition, but same results

Scientific paper

We examine two different ways of encoding a counting function, as a rational generating function and explicitly as a function (defined piecewise using the greatest integer function). We prove that, if the degree and number of input variables of the (quasi-polynomial) function are fixed, there is a polynomial time algorithm which converts between the two representations. Examples of such counting functions include Ehrhart quasi-polynomials, vector partition functions, integer points in parametric polytopes, and projections of the integer points in parametric polytopes. For this last example, this algorithm provides the first known way to compute the explicit function in polynomial time. We rely heavily on results of Barvinok, and also of Verdoolaege, Seghir, Beyls, et al.

Affiliated with

Also associated with

No associations

Rating

Counting with rational generating functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting with rational generating functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting with rational generating functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-280151