Mac Mahon's Partition Analysis Revisited

Peter Paule

RISC, Linz (Austria)

Algorithms Seminar

October 2, 2000

[summary by Sylvie Corteel]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).
Abstract
The purpose of this talk is to present the W operator introduced by Mac Mahon in 1915 and to show its power in current combinatorial and partition-theoretic research. This operator is implemented in the Mathematica Package Omega which was developped by A. Riese. This is joint work with G. E. Andrews (Penn State University) and A. Riese (RISC-Linz).



1  Introduction

Mac Mahon devoted many pages of his famous book ``Combinatorial Analysis'' [9] to W-calculus. Netherveless this method was not used for 85 years except by Stanley in 1973 [10]. The purpose of this talk is to present the W operator and to show its power in current combinatorial and partition-theoretic research [1, 2, 3, 4, 5]. In this summary, we define the W operator and exhibit a few of its elimination rules, before giving two problems where this operator is a powerful tool: lecture hall partitions and k-gons of integer length.

2  The Omega Operator

Let us now define the operator and present a few rules.
Definition 1  [9] The Omega operator W is defined as follows:
W
s1=-
...
sr=-
As1,...,srl1s1...lrsr=
s1=0
...
sr=0
As1,...,sr.

To evaluate this operator, Mac Mahon proposed a list of elimination rules. The proof of each is straightforward as it uses the simple identity
 
n0
xn=1/(1-x).
We list a few of them only:
W
l-s
(1-l x)


1-
y
l



=
xs
(1-x)(1-xy)
,    
     s0,  
W
1
(1-l x)


1-
y
l






1-
z
l



=
1
(1- x)(1-xy)(1-xz)
,
     
W
1
(1-l x)


1-
y
ls



=
1
(1-x)(1-xsy)
,    
     s>0,  
W
1
(1-ls x)


1-
y
l



=
1+xy
1-ys-1
1-y
(1- x)(1-xys)
,    
     s>0.  

For example to find the generating function of the partitions with three parts and whose parts differ by at least two, we use the first rule:
f3(q)=W
 
a1,a2,a31
l1a1-a2-2l2a2-a3-2qa1+a2+a3 =W
l1-2l2-2q3
(1-l1 q)


1 -
l2q
l1






1 -
q
l2



=W
q2l2-2q3
(1-q) ( 1 -l2q2 )


1 -
q
l2



=
q2q4q3
(1-q) ( 1 -q2 ) ( 1 -q3 )
.


It is also possible to generalize this result for partitions with k parts and whose parts differ by at least two for any k>0, that is
fk(q)=
qk2
(1-q)(1-q2)...(1-qk)
.

3  Lecture Hall Partitions

The lecture hall partition theorem is one of the most elegant recent result in partition analysis [6, 7]. Let us state the refinement of this theorem [8].
Theorem 1   The number of partitions of n of the form (bj,bj-1,..., b1) with bj/jbj-1/j-1...b1/10 and bj-bj-1+...+(-1)j-1 b1=m is equal to the number of partitions of n into m odd parts less than 2j.

This theorem can also be proved with the Omega operator [1], which is what motivated G. E. Andrews to resuscitate the Omega operator. The proof mainly uses the elimination rule
W
1
(1-l x)


1-
y
ls



=
1
(1-x)(1-xsy)
Let us illustrate it for j=3.
 
b3
3
b2
2
b1
1
0
xb3-b2+b1 qb3+b2+b1 =W
 
b3,b2,b10
l12b3-3b2l2b2-2b1xb3-b2+b1qb3+b2+b1
=W
1
(1-l12qx)


1-
l2 q
l13x






1-
qx
l22



=W
1
(1-xq)(1-xq3)(1-xq5)
.


The Omega operator can also give a bijective proof of the theorem [5]. Let us show how to proceed for j=3:
 
b3
3
b2
2
b1
1
0
q3b3q2b2 q1b1
=W
 
b3,b2,b10
l12b3-3b2l2b2-2b1 q3b3q2b2q1b1 =W
1+q2q32
(1-q3)(1-q22q33)(1-q1q22q33)
.
                 

From the previous equation we get that there is a bijection between the lecture hall partitions (b3,b2,b1) of n and the partitions of n into parts {1,3,5} with multiplicity mi for the part i. This bijection becomes:
b3=3m5+2m3-


m3
2



+m1,      b2=2m5+m3,      b1=


m3
2



.

4  k-Gons with Integer Length

The problem can be defined as follows. The number |Tk(n)| of k-gons with length n is equal to the number of solutions of
ak ak-1... a11, a1+a2+...+ak=n, a1+a2+...+ak-1>ak.     (1)

Let Fk(q)=n|Tk(n)|qn be the associated generating function. For triangles (k=3) we get
F3(q)=
 
n
| T3(n) | qn=
q3
(1-q2)(1-q3)(1-q4)
.
This is easy to prove as conditions (1) give
F3(q)=W
 
a11
a2,a30
l1a3-a2l2a2-a1l3a1+a2-a3-1qa1+a2+a3
=W
ql1-1



1-
ql2
l3






1-
ql1l3
l2






1-
ql3
l1



=
q3
(1-q2)(1-q3)(1-q4)


We can even be more specific
F3(q1,q2,q3)=
 
a3 a2 a11
a1+a2>a3
q1a1 q2a2 q3a3 =W
 
a11
a2,a30
l1a3-a2l2a2-a1l3a1+a2-a3-1q1a1 q2a2
=W
ql1-1



1-
ql2
l3






1-
ql1l3
l2






1-
ql3
l1



=
q1q2q3
(1-q2q3)(1-q1q2q3)(1-q1q2q32)
.


This shows there is a bijection between the 3-tuples (u1,u2,u3) of N3 and the triangles whose sides have length u1+u2+1, u1+u2+u3+1 and u1+2u2+u3+1.

Thanks to the Omega operator we can compute the generating function for larger k:
F4(q)
=
q4(1+q+q5)
(1-q2)(1-q3)(1-q4)(1-q6)
,
                 
F5(q)
=
q5(1-q11)
(1-q)(1-q2)(1-q4)(1-q5)(1-q6)(1-q8)
,
                 
F6(q)
=
q6(1-q4+q5+q7-q8-q13)
(1-q)(1-q2)(1-q4)(1-q6)(1-q8)(1-q10)
.
                 
We then can see that no pattern can be found and the Omega operator was a quick tool to show that the solutions of this k-gon problem do not have ``nice'' generating functions.

References

[1]
Andrews (George E.). -- MacMahon's partition analysis. I. The lecture hall partition theorem. In Mathematical essays in honor of Gian-Carlo Rota (Cambridge, MA, 1996), pp. 1--22. -- Birkhuser Boston, Boston, MA, 1998.

[2]
Andrews (George E.). -- MacMahon's partition analysis. II. Fundamental theorems. Annals of Combinatorics, vol. 4, n°3-4, 2000, pp. 327--338. -- Conference on Combinatorics and Physics (Los Alamos, NM, 1998).

[3]
Andrews (George E.) and Paule (Peter). -- MacMahon's partition analysis. IV. Hypergeometric multisums. Sminaire Lotharingien de Combinatoire, vol. 42, n°B42i, 1999. -- The Andrews Festschrift (Maratea, 1998). 24 pages.

[4]
Andrews (George E.), Paule (Peter), and Riese (Axel). -- MacMahon's partition analysis: the Omega package. European Journal of Combinatorics, vol. 22, n°7, 2001, pp. 887--904.

[5]
Andrews (George E.), Paule (Peter), Riese (Axel), and Strehl (Volker). -- MacMahon's partition analysis. V. Bijections, recursions, and magic squares. In Algebraic combinatorics and applications (Gweinstein, 1999), pp. 1--39. -- Springer, Berlin, 2001.

[6]
Bousquet-Mlou (Mireille) and Eriksson (Kimmo). -- Lecture hall partitions. The Ramanujan Journal, vol. 1, n°1, 1997, pp. 101--111.

[7]
Bousquet-Mlou (Mireille) and Eriksson (Kimmo). -- Lecture hall partitions. II. The Ramanujan Journal, vol. 1, n°2, 1997, pp. 165--185.

[8]
Bousquet-Mlou (Mireille) and Eriksson (Kimmo). -- A refinement of the lecture hall theorem. Journal of Combinatorial Theory. Series A, vol. 86, n°1, 1999, pp. 63--84.

[9]
MacMahon (Percy A.). -- Combinatory analysis. -- Chelsea Publishing Co., New York, 1960, xix+302+xix+340p. Two volumes (bound as one).

[10]
Stanley (Richard P.). -- Linear homogeneous Diophantine equations and magic labelings of graphs. Duke Mathematical Journal, vol. 40, 1973, pp. 607--632.

This document was translated from LATEX by HEVEA.