MIT Combinatorics Seminar

On MacMahon's partition analysis

Guoce Xin  (Brandeis University)

Wednesday, October 06, 2004    4:15 pm    Room 2-338


In his famous book "Combinatory Analysis" MacMahon introduced partition analysis as a computational method for solving problems of counting solutions to linear Diophantine equations and inequalities, counting lattice points in a convex polytope, and computing Ehrhart quasi-polynomials. Recent results by (1998) G.E. Andrews and his co-authors, together with their Omega package, which can be used as a tool for solving such problems, will be introduced. I will present a new approach, which combines the theory of iterated Laurent series and a new algorithm for partial fraction decompositions, and leads to an algorithm, whose running time is much less than that of the Omega package. This talk is going to be mostly based on my paper, "A Fast Algorithm for MacMahon's Partition Analysis" (accepted by Electron. J. Combin., arXiv: math.CO/0408377).