Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Here is an example: given vectors a_1,...,a_n, let f(s) be the number of ways to write the vector s as a nonnegative integer combination of the a_i. This function f(s) is called the vector partition function, and it can be encoded nicely as a generating function. But suppose we would like to find an explicit representation of the function f(s), using, say, the greatest integer function. I will show how to find this representation quickly (in polynomial time). Indeed, given a rational generating function encoding of any counting function c(s), we can find an explicit representation for c(s) quickly. Another interesting example of such a function is the Ehrhart quasi-polynomial, which I will also discuss. This is joint work with Sven Verdoolaege