<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue4" %>
A General Algorithm for the MacMahon Omega Operator
Guo-Niu Han
Institut de Recherche Mathématique Avancée, Université Louis Pasteur et CNRS, 7, rue René-Descartes, 67084 Strasbourg Cedex, France
guoniu@math.u-strasbg.fr
Annals of Combinatorics 7 (4) p.467-480 December, 2003
AMS Subject Classification: 05A17, 05A19, 05E05, 15A15, 68W30
Abstract:
In his famous book "Combinatory Analysis" MacMahon introduced Partition Analysis ("Omega Calculus") as a computational method for solving problems in connection with linear diophantine inequalities and equations. The technique has recently been given a new life by G.E. Andrews and his coauthors, who had the idea of marrying it with the tools of to-day's Computer Algebra.

The theory consists of evaluating a certain type of rational function of the form by the MacMahon operator. So far, the case where the two polynomials A and B are factorized as products of polynomials with two terms has been studied in details. In this paper we study the case of arbitrary polynomials A and B. We obtain an algorithm for evaluating the operator using the coefficients of those polynomials without knowing their roots. Since the program efficiency is a persisting problem in several-variable polynomial Calculus, we did our best to make the algorithm as fast as possible. As an application, we derive new combinatorial identities.

Keywords: partition analysis, partitions, Omega operator, diophantine inequalities, algorithm

References:

1. M. Bousquet-Mélou and K. Eriksson, Lecture hall partitions, Ramanujan J. 1 (1997) 101每 111.

2. G.-N. Han, Généralisation de l'identité de Scott sur les permanents, Linear Algebra Appl. 311 (2000) 25每34.

3. L. Habsieger, Private commucation, 2002.

4. G.-N. Han and C. Krattenthaler, Rectangular Scott-type permanents, Sém. Lothar. Combin. B43g (2000) 25 pp.

5. J.P. Jouanolou, Private commucation, 2002.

6. A. Lascoux, Notes on Interpolation in one and several variables, 40 pp.,http://igm.univ-mlv.fr/~al.

7. A. Lascoux, Square-ice enumeration, In: The Andrews Festschrift, Seventeen Papers on Classical Number Theory and Combinatorics, D. Foata and G.N. Han, Eds., Springer-Verlag, 2001, pp. 335每348.

8. A. Lascoux and M.-P. Schützenberger, Formulaire raisonné de fonctions symétriques, Publication LITP, Université Paris 7, 1985.

9. P.A. MacMahon, Combinatory Analysis, 2 Vols., Cambridge University Press, Cambridge, 1915?916, reprinted by Chelsea, New York, 1960.

10. I.G. Macdonald, Symmetric Functions and Hall Polynomials, Second Edition, Clarendon Press, Oxford, 1995.

11. G.E. Andrews, P. Paule, and A. Riese, Omega package for Mathematica,http://www.risc.uni-linz.ac.at/research/combinat/risc/software.

12. G.E. Andrews, MacMahon's partition analysis I: the lecture hall partition theorem, Progr. Math. 161 (1998) 1每22.

13. G.E. Andrews, MacMahon's partition analysis II: fundamental theorems, Ann. Combin. 4 (2000) 327每338.

14. G.E. Andrews, P. Paule, and A. Riese, MacMahon's partition analysis III: the Omega package, Europ. J. Combin. 22 (2001) 887每904.

15. G.E. Andrews and P. Paule, MacMahon's partition analysis IV: hypergeometric multisums, In: The Andrews Festschrift, Seventeen Papers on Classical Number Theory and Combinatorics, D. Foata and G.N. Han Eds., Springer-Verlag, 2001, pp. 189每208.

16. G.E. Andrews, P. Paule, A. Riese, and V. Strehl, MacMahon's partition analysis V: bijections, recursions, and magic squares, In: Algebraic Combinatorics and Applications, Lecture Notes in Mathematics, A. Betten et al., Eds., Springer-Verlag, 2001, pp. 1每39.

17. G.E. Andrews, P. Paule, and A. Riese, MacMahon's partition analysis VI: a new reduction algorithm, Ann. Combin. 5 (2001) 251每270.

18. G.E. Andrews, P. Paule, and A. Riese, MacMahon's partition analysis VII: constrained compositions, In: q-Series with Applications to Combinatorics, Number Theory, and Physics, Contemp. Math., Vol. 291, B.C. Berndt and K. Ono, Eds., Amer. Math. Soc., 2001, pp. 11每27.

19. G.E. Andrews, P. Paule, and A. Riese, MacMahon's partition analysis VIII: plane partition diamonds, Adv. Appl. Math. 27 (2001) 231每242.

20. G.E. Andrews, P. Paule, and A. Riese, MacMahon's partition analysis IX: k-gon partitions, Bull. Austral. Math. Soc. 64 (2001) 321每329.