Open Journal of Discrete Mathematics, 2011, 1, 108-115

doi:10.4236/ojdm.2011.13014 Published Online October 2011 (http://www.SciRP.org/journal/ojdm)

Copyright © 2011 SciRes. OJDM

Bijections between Lattice Paths and Plane Partitions

Mateus Alegri1, Eduardo Henrique de Mattos Brietzke2, José Plínio de Oliveira Santos3*,

Robson da Silva4

1Departamento de Matemática, UFS, Campus Itabaiana, Itabaiana-SE, Brazil

2Instituto de Matemática, UFRGS, Porto Alegre-RS, Brazil

3IMECC-UNICAMP, Campinas-SP, Brazil

4ICE-UNIFEI, Itaju bá-MG, Brazil

E-mail: malegri@ufs.br, brietzke@mat.ufrgs.br, *josepli@ime.unicamp.br, rsilva@unifei.edu .br

Received July 4, 2011; revised August 5, 2011; accepted August 15, 2011

Abstract

By using lattice paths in the three-dimensional space we obtain bijectively an interpretation for the overparti-

tions of a positive integer n in terms of a set of plane partitions of n. We also exhibit two bijections between

unrestricted partitions of n and different subsets of plane partitions of n.

Keywords: Lattice Paths, Plane Partitions, Partitions, q-Analog.

1. Introduction

In [1], one of us, Santos, in a joint work with Mondek

and Ribeiro, introduced a new combinatorial interpreta-

tion for partitions in terms of two-line matrices. In that

paper a new way of representing, as two-line matrices,

unrestricted partitions and several identities from Slater’s

list ([2]) including Rogers-Ramanujan Identities, and

Lebesgue’s Partition Identity is described. In [3] we were

able to provide a number of bijective proofs for several

identities based on the two-line matrix representation,

including a new bijective proof for the Lebesgue Identity,

as well as a combinatorial proof for an identity related to

three-quadrant Ferrers graphs, given by Andrews (see [4]).

The possibility of associating a partition of n to a

two-line matrix and the two-line matrix to a lattice path

from the origin to the line x + y – n was mentioned in [1].

This construction can be done in many different ways.

Each one of those provides us with a family of polyno-

mials that are, each one, a q-analog for the partition func-

tion. In order to construct these families it was employed

the same idea of counting the lattice path according to

the area limited by the path and the x-axis, as done by

Pólya.

Our main goal in the present paper is to associate a

three-line matrix to a path in the 3-dimensional space, in

order to build a volume, which is going to correspond to

a plane partition. In this way it is possible to construct

bijections from certain classes of plane partitions to

overpartitions or unrestricted partitions. In some cases

mock theta functions appear as the generating functions

for these matrices (see [5]).

2. Background

In this section we remember a few definitions and state a

theorem that is the base for constructing the bijections.

Definition 2.1 A partition of a positive integer n is a

collection of positive integers 12

such

that 12

=

n

. Each i

is called a part of

the partition.

Definition 2.2 An overpartition is a partition where

the first occurrence of a part can be overlined.

Example 2.1 There are 14 overpartitions of 4:

4, 4,31,31,31,31,22, 22, 211,2

11,211,211,1111,1111

Definition 2.3 A Plane partition is a left-justified

π

array of positive integers such that

,,1

πij ij,

πij

,1 1,

max π,π

iji j

πij

ij

. We say that πis a plane partition of

n if =n

,

,1

.

Now, if we stack , cubes over the position

of each part of a plane partition , we obtain a geomet-

rical figure in the first octant of the 3-dimensional space,

which represents in the same way a Ferrers diagram

represents a partition.

πij ,ij

π

π

Example 2.2 Below (shown in Figures 1 and 2) we

have a plane partitions of 43 and its standard geometri-

cal representation.