tailieunhanh - Báo cáo toán học: "A Fast Algorithm for MacMahon’s Partition Analysis"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: A Fast Algorithm for MacMahon’s Partition Analysis. | A Fast Algorithm for MacMahon s Partition Analysis Guoce Xin Department of Mathematics Brandeis University Waltham USA maxima@ Submitted Aug 26 2004 Accepted Aug 30 2004 Published Sep 9 2004 Mathematics Subject Classifications 11Y60 05A17 Abstract This paper deals with evaluating constant terms of a special class of rational functions the Elliott-rational functions. The constant term of such a function can be read off immediately from its partial fraction decomposition. We combine the theory of iterated Laurent series and a new algorithm for partial fraction decompositions to obtain a fast algorithm for MacMahon s Omega calculus which partially avoids the run-time explosion problem when eliminating several variables. We discuss the efficiency of our algorithm by investigating problems studied by Andrews and his coauthors our running time is much less than that of their Omega package. 1 Introduction Zeilberger 20 proved a conjecture of Chan et al. 11 by proving an identity equivalent to CT CT __1_- __-1__- C C _1. Cid CT 11 .11- n . . C1 Cn-1 X1 Xn 1 li 1 1 ml li j xi xj where Ck s are the Catalan numbers. This identity should be interpreted as taking iterated constant terms 10 . in applying CTXn to the displayed rational function we expand it as a Laurent series in xn the result is still a rational function and we can apply CTXn_1 . CTx1 to it iteratively. The idea behind the above treatment is to give a proper series expansion of 1 xi Xj for every i and j so that all of the expansions are compatible. Once we have determined the relations between the x s there is no confusion about their series expansion. For instance we can let 1 X1 xn. For the particular rational function in equation which is symmetric in the x s there is no confusion after a total ordering on the x s is given. Thanks to Ira Gessel THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R58 1 Here we present a slightly different but more efficient approach