Mac Mahon's Partition Analysis Revisited

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_³

s₁=-¥

...

s_r=-¥

A_{s₁,...,s_r}l₁^s₁...l_r^s_r=

s₁=0

...

s_r=0

A_{s₁,...,s_r}.

To evaluate this operator, Mac Mahon proposed a list of elimination rules. The proof of each is straightforward as it uses the simple identity

n³0

xⁿ=1/(1-x).

We list a few of them only:

W_³

l^-s

(1-l x)

æ
ç
ç
è

ö
÷
÷
ø

x^s

(1-x)(1-xy)

s³0,

W_³

(1-l x)

æ
ç
ç
è

ö
÷
÷
ø

æ
ç
ç
è

ö
÷
÷
ø

(1- x)(1-xy)(1-xz)

W_³

(1-l x)

æ
ç
ç
è

l^s

ö
÷
÷
ø

(1-x)(1-x^sy)

s>0,

W_³

(1-l^s x)

æ
ç
ç
è

ö
÷
÷
ø

1+xy

1-y^s-1

1-y

(1- x)(1-xy^s)

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:

f₃(q)=W_³

a1,a₂,a₃³1

l₁^a₁-a₂-2l₂^a₂-a₃-2q^{a₁+a₂+a₃} =W_³

l₁^-2l₂^-2q³

(1-l₁ q)

æ
ç
ç
è

1 -

l₂q

l₁

ö
÷
÷
ø

æ
ç
ç
è

1 -

l₂

ö
÷
÷
ø

=W_³

q²l₂^-2q³

(1-q)

(

1 -l₂q²

)

æ
ç
ç
è

1 -

l₂

ö
÷
÷
ø

q²q⁴q³

(1-q)

(

1 -q²

)

(

1 -q³

)

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

f_k(q)=

q^k²

(1-q)(1-q²)...(1-q^k)

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 (b_j,b_j-1,..., b₁) with b_j/j³b_j-1/j-1³...³b₁/1³0 and b_j-b_j-1+...+(-1)^j-1 b₁=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-l x)

æ
ç
ç
è

l^s

ö
÷
÷
ø

(1-x)(1-x^sy)

Let us illustrate it for j=3.

b₃

b₂

b₁

³0

x^{b₃-b₂+b₁} q^{b₃+b₂+b₁} =W_³

b₃,b₂,b₁³0

l₁^2b₃-3b₂l₂^b₂-2b₁x^{b₃-b₂+b₁}q^{b₃+b₂+b₁}

=W_³

(1-l₁²qx)

æ
ç
ç
è

l₂ q

l₁³x

ö
÷
÷
ø

æ
ç
ç
è

l₂²

ö
÷
÷
ø

=W_³

(1-xq)(1-xq³)(1-xq⁵)

The Omega operator can also give a bijective proof of the theorem [5]. Let us show how to proceed for j=3:

b₃

b₂

b₁

³0

q₃^b₃q₂^b₂ q₁^b₁

=W_³

b₃,b₂,b₁³0

l₁^2b₃-3b₂l₂^b₂-2b₁ q₃^b₃q₂^b₂q₁^b₁ =W_³

1+q₂q₃²

(1-q₃)(1-q₂²q₃³)(1-q₁q₂²q₃³)

From the previous equation we get that there is a bijection between the lecture hall partitions (b₃,b₂,b₁) of n and the partitions of n into parts {1,3,5} with multiplicity m_i for the part i. This bijection becomes:

b₃=3m₅+2m₃-

ê
ê
ê
ë

m₃

ú
ú
ú
û

+m₁, b₂=2m₅+m₃, b₁=

ê
ê
ê
ë

m₃

ú
ú
ú
û

4 k-Gons with Integer Length

The problem can be defined as follows. The number |T_k(n)| of k-gons with length n is equal to the number of solutions of

a_k³ a_k-1³...³ a₁³1, a₁+a₂+...+a_k=n, a₁+a₂+...+a_k-1>a_k. (1)

Let F_k(q)=å_n|T_k(n)|qⁿ be the associated generating function. For triangles (k=3) we get

F₃(q)=

T₃(n)

qⁿ=

q³

(1-q²)(1-q³)(1-q⁴)

This is easy to prove as conditions (1) give

F₃(q)=W_³

a₁³1

a₂,a₃³0

l₁^a₃-a₂l₂^a₂-a₁l₃^{a₁+a₂-a₃-1}q^{a₁+a₂+a₃}

=W_³

ql₁^-1

æ
ç
ç
è

ql₂

l₃

ö
÷
÷
ø

æ
ç
ç
è

ql₁l₃

l₂

ö
÷
÷
ø

æ
ç
ç
è

ql₃

l₁

ö
÷
÷
ø

q³

(1-q²)(1-q³)(1-q⁴)

We can even be more specific

F₃(q₁,q₂,q₃)=

a₃³ a₂³ a₁³1

a₁+a₂>a₃

q₁^a₁ q₂^a₂ q₃^a₃ =W_³

a₁³1

a₂,a₃³0

l₁^a₃-a₂l₂^a₂-a₁l₃^{a₁+a₂-a₃-1}q₁^a₁ q₂^a₂

=W_³

ql₁^-1

æ
ç
ç
è

ql₂

l₃

ö
÷
÷
ø

æ
ç
ç
è

ql₁l₃

l₂

ö
÷
÷
ø

æ
ç
ç
è

ql₃

l₁

ö
÷
÷
ø

q₁q₂q₃

(1-q₂q₃)(1-q₁q₂q₃)(1-q₁q₂q₃²)

This shows there is a bijection between the 3-tuples (u₁,u₂,u₃) of N³ and the triangles whose sides have length u₁+u₂+1, u₁+u₂+u₃+1 and u₁+2u₂+u₃+1.

Thanks to the Omega operator we can compute the generating function for larger k:

F₄(q)

q⁴(1+q+q⁵)

(1-q²)(1-q³)(1-q⁴)(1-q⁶)

F₅(q)

q⁵(1-q¹¹)

(1-q)(1-q²)(1-q⁴)(1-q⁵)(1-q⁶)(1-q⁸)

F₆(q)

q⁶(1-q⁴+q⁵+q⁷-q⁸-q¹³)

(1-q)(1-q²)(1-q⁴)(1-q⁶)(1-q⁸)(1-q¹⁰)

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. -- Birkhäuser 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. Séminaire 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 (Gößweinstein, 1999), pp. 1--39. -- Springer, Berlin, 2001.
[6]: Bousquet-Mélou (Mireille) and Eriksson (Kimmo). -- Lecture hall partitions. The Ramanujan Journal, vol. 1, n°1, 1997, pp. 101--111.
[7]: Bousquet-Mélou (Mireille) and Eriksson (Kimmo). -- Lecture hall partitions. II. The Ramanujan Journal, vol. 1, n°2, 1997, pp. 165--185.
[8]: Bousquet-Mélou (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 L^AT_EX by H^EV^EA.