Paper Menu >>

Journal Menu >>

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: [email protected], [email protected], *[email protected], [email protected] .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
s

such
that 12
=
s
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.
109
M. ALEGRI ET AL.
44432
43322
2221
22
1
Figure 1. A plane partition.
Figure 2. Geometrical representation.
In [6] the following correspondence between three-
line matrices and overpartitions is presented.
Theorem 2.1 The number of overpartitions of n is
equal to the number o f three-line matrices of the form
123
123
123
s
s
s
ccc c
ddd d
eee e





(1)
with non-negative integ er entries satisfying

11
11
0,1
=1
=0 if =
=
=,
t
ss
ttt
ttt t
ttt
e
ce
ede
cc d i
cden





t
e
1
where , except when and , in
which case .
=
t
ie
t
i
t
=0
1
==
tt
ee
1=
t
c
The proof of this theorem can be found in [6]. We de-
scribe the bijection that follows from the theorem. Given
a matrix A of the form (1), the corresponding overparti-
tion 12
=
s
 
 is obtained by adding up the
entries in each column of A. A part t
of
is
marked if and only if . Due to the conditions de-
fining matrices of the form (1), in case of more than one
column of A add up to the same number, only the left
most of these parts is marked.
=1
t
e
Example 2.3 In the table below we have the 14 over-
partitions of 4 and the corresp onding three-line matrices
of the form (1).
overpartitionmatrix overpartition matrix
4
1
3
0





4
0
3
1





31
11
20
00





31
01
20
10





31
00
30
01





31
00
20
11





22
21
01
00





22
11
01
10





211
111
100
000





211
011
100
100





211
001
200
010





211
001
100
110





1111

1111
0000
0000





1111
0111
0000
1000





3. Bijection between Overpartitions and
Plane Partitions via Lattice Path
In this section we stablish a bijection between the over-
partitions of n and certain plane partitions of n. In order
to do this we describe a possible way to build a volume
from a three-line matrix and, then, we associate a plane
partition.
Consider, for example, the matrix
631
421.
220



(2)
Copyright © 2011 SciRes. OJDM
M. ALEGRI ET AL.
110
In order to obtain a solid representing a plane partition
we start drawing the lattice path at moving 6
units in the x-direction, 4 units in the y-direction, 2 units
in z-direction, 3 units in the x-direction, and so on. In this
way we generate a 3-dimensional path. These move-
ments are represented in Figure 3, where the star to-
gether with a number near a corner represents a move-
ment in the positive z-direction. When the displacements
in both, the y and z-directions, are zero, we have a prob-
lem to reconstruct the three-line matrix from the lattice
path, which can be overcome by the introduction of two
different colors.
(0,1,1)
We need to get from the picture given in Figure 3 a
representation for a plane partition in the conventional
way, i.e., as a solid in the first octant. It suffices to apply
the transformation =1 , which corre-
sponds to a reflection with respect to the yz-plane fol-
lowed by a translation in the x-direction. Figure 4 below
shows the corresponding volume.
1
s
i
i
xx c 
Note that in the solid shown in Figure 4 there is an
extra wall added on the back as if at the end of the lattice
path we had moved one extra unit in the x-direction. This
must be done to avoid ambiguity when we reconstruct
the three-line matrix from the solid. The plane partition
corresponding to this solid is shown below.
55555555
5555555
33333
33333
33333
1
1
1
1
1
1
Figure 3. The lattice path.
Figure 4. The solid.
As one may see above in Theorem 1, the three-line
matrix can have zero entries, in which case we should
have to introduce different colors in order to be able to
reconstruct the original matrix from the volume. It is
important to mention that by the way we are building the
lattice path from the matrix the distance from the origin
to the end of the path is equal to as shown in
Figure 3 (remember we have started at (0,1,1) and, be-
cause the extra wall added on the back in Figure 4 the
number of layers (11) on the plane partition plus the
height of the first layer (5) plus its width (8) must be
2n
3n
(213 =24)
).
Now we are going to describe how to solve the prob-
lem when there are zero entries so that it will not be nec-
essary to use colors. Consider the overpartition 43
21
of 10. By Theorem 1 its three-line matrix repre-
sentation is
3101
1210.
0010





In this case if we draw the lattice path as in Figure 3 it
would be quite difficult to tell the matrix from which we
have started without using colors. One way to solve this
problem is to add 1 to each entry of the matrix and then
draw the lattice path. In the example above the resulting
matrix is
4212
2321
1121



(3)
and the corresponding figures, as done for matrix (2) are
shown in Figure 5 and Figure 6 below.
Definition 3.1 A plane partition is said to be of type
if in its geometrical representa tion the the number of
distinct levels that are parallel to each of the planes xy,
xz, and yz is the same.
Copyright © 2011 SciRes. OJDM
111
M. ALEGRI ET AL.
Figure 5. The lattice path.
Figure 6. The solid.
Another way to characterize a plane partition of type
is to say that the number of steps necessary to climb
from the xy-plane to the top of the solid representing the
plane partition is the same as climbing from the xz-plane
or from the yz-plane to the respective top.
From the observations given above we can always
move from an overpartition to a 3-line matrix with non-
zero entries and, then, drawing the lattice path, get a
plane partition of type . The number of distinct levels
that are parallel to each of the planes xy, xz, and yz will
be one plus the number of columns of the original matrix.
This number is precisely the number of blocks (rectan-
gular prisms) that are present in the 3-dimension repre-
sentation of the plane partition.
Considering the construction above, it is easy to write
the matrix with positive entries by looking at the solid
representing a plane partition of type . To get the en-
tries on the third line we have to stand on the plane z = 1
(remember we have started drawing the lattice path at
), climb to the top and set the height of those
steps as the entries. For instance, in Figure 6 the steps
are, respectively, 1, 1, 2, and 1. To get the entries on the
second line we have to stand on the plane y = 1 (we have
started at ), go up to the top and set the height of
those steps as the entries. In Figure 6, these steps are
respectively, 2, 3, 2, and 1. As we have made a reflection
in the construction of the solids, in order to obtain the
entries on the first line we have to stand on the plane x =
1, climb to the top, count the height of those steps and,
then, we set the entries as being these integer in the re-
verse order. For example, from Figure 6, we have for the
first line: 4, 2, 1, and 2.
(0,1,1)
(0,1,1)
The discussion above provides us with a bijection be-
tween plane partitions of type and those three-line
matrices from which by subtracting 1 of each entry we
get matrices of the form (1).
Definition 3.2 A plane partition of n is said to be of
type if it is a plane partition o f type and the ma-
trix obtained by subtracting 1 from each entry of its cor-
responding three-line matrix is of the form (1).
 
We summarize what we have obtained above in the
following theorem that gives a complete characterization
for the overpartitions in terms of plane partitions.
Theorem 3.1 The number of plane partitions of n of
type is equal to the the number of overpartitions of
n.
4. Two Bijections between Unrestricted
Partitions and Plane Partitions
There is a trivial bijection between unrestricted partitions
and plane partitions that can be obtained just by looking
a Ferrers diagram as a plane partition with one row. In
this section we present two bijections between unre-
stricted partitions and plane partitions different from the
trivial.
In [1] three interpretations as two-line matrices for
unrestricted partitions are presented. One of them estab-
lishes that:
Theorem 4.1 (Theorem 8 of [1] ) The number of un-
restricted partitions of n is equal to the number of ma-
trices of the form
12
12
,
s
s
cc c
dd d


(4)
where 11
=0, =
s
tt t
cccd
, and .
=
ii
cd
 n
The proof of this theorem can be found in [1]. Given a
partition 12
s

 of n, we split each part i
into a column starting with
s
as the right-most column
Copyright © 2011 SciRes. OJDM
M. ALEGRI ET AL.
112
of a matrix of the form (4): =
s
s
d
, 1t
=
tt
ccd
and
111
=
ttt
dc

==
. Conversely, given a matrix of the form
(4), we obtain a partition of n adding up the entries in
each column.
In our next theorem we have an interpretation, as
three-line matrices, for unrestricted partitions.
Theorem 4.2 The number of unrestricted partitio ns of
n is equal to the number of three-line matrices of the
form
12
12
12
,
cc
dd
ee
s
s
s
c
d
e



11
= ,
1,=
(5)
where 1
=0, 1
s
ss t
c dd
tt
ee

0
0
1
00
10
1
00
010
0001
10
01
00















s tt
cc
0
0
1





cd
ii
cd

n
n
,
and .
=
i
e
The proof of this theorem is just a consequence of the
following notation for the positive integers.
0
10
1
00
210
01
10
301
00
11
400
000
111
500
0
11
00
00











We define the sum of two integers in this notation by
adding the corresponding matrices in the usual way if
they have the same number of columns and, if not, we
add to the matrix representing the smaller integer a
number of zero columns on the right to have the two ma-
trices with the same number of columns so that we may
add in the usual way. For example,
11100 11000
5400010 00100
0000100010






22100
=0 0 11 0,
00011





and
6643 3310 0
988544 002100210.
000210021


 


With this three-line matrix representation for unre-
stricted partitions and exactly the same construction de-
scribed in the previous section for overpartitions we can
state a nontrivial characterization for unrestricted parti-
tions as plane partitions.
Definition 4.1 A plane partition of n is said to be of
type if it is a plane partition of type and the
matrix obtained by subtracting 1 from each entry of its
corresponding three-line matrix is of the form (5).
 
Theorem 4.3 The number of plane partitions of n of
type is equal to the the number of unrestricted parti-
tions of n.
Consider, for example, the partition .
Then
54221
22100 33211
54221 2011031221.
1201123122


 



Now we can obtain the plane partition associated to
54221
 by drawing the lattice path (Figure 7)
and constructing the solid (Figure 8) as before:
Figure 7. The lattice path.
Copyright © 2011 SciRes. OJDM
113
M. ALEGRI ET AL.
Figure 8. The plane partition.
As an extra example consider the partition 63
. Then
32
311100
6332 120010
012011
422211
231121
123112






and the lattice path and the corresponding plane partition
associated to are shown in Figures 9 and
10.
6332
Figure 9. The lattice path.
Figure 10. The plane partition.
Our final result is another representation for unrestricted
partitions as plane partitions different from the one just
described. To do this we use the result given in Theorem
4.2. From the restrictions defining a matrix of the form
(5) it is easy to see that the third line, without 1, is
equal to the second one (just shifted one position to the
right). Now we can associate to each one of these three-
line matrices a two-line matrix by adding together the
elements t and 1t
e
e
d
that are equal. This is equivalent
to multiply the second line by 2. We add the element 1
to the first entry 1 on the first line. We observe that, in
general, the number of columns in the two-line matrix
obtained is reduced by one. Te only case in which this
number is not reduced is when the three-line matrix has
only one column. In this case we define the correspond-
ing two-line matrix by:
e
c
1,ifiseven
01
00,fis odd.
n
n
nin
n

 
 

 

 

To illustrate the bijection just defined we list below
two examples
22100 3210
20110 4022
12011
311100 31110
120010 24002
012001
















Copyright © 2011 SciRes. OJDM
M. ALEGRI ET AL.
114
From this bijection we have the following theorem.
Theorem 4.4 The number of unrestricted partitio ns of
n is equal to the number of two-line matrices of the form
12
12
,
s
s
cc c
dd d


(6)
where
for >1s, =0
s
c, t
d is even with , 2
12
2
d
cc
 ,
1
12
t
d
for >1t; =
tt
cc
for =1s and n even, 1=1c and =1dn;
1
for =1s and n odd, 1=0c and 1=dn;
and =n.
ii
In order to get, for an integer n, a complete description
for another subset of plane partitions having the same
cardinality as the number of unrestricted partitions of n
we do the following.
cd

When we moved from a matrix of the form (5) to one
like (6) we have added the entries 1 and 1
c of (5) to
get the entry 1 of (6). Now we consider the two-line
matrix without this addition and use this matrix to draw a
lattice path, as we did before, by first adding one to each
entry. Observing that this lattice path is entirely on the
plane we use the element 1 to move up this
lattice path to the plane
e
e
e
c
=1z
1
=1z
. This operation is il-
lustrated below.
22100
5422120110
12011
22103321
4022 5132



 





e
The corresponding lattice path and plane partition are
shown in Figures 11 and 12.
Definition 4.2 A plane partition is said to be of type E
if the number of faces that are parallel to th e xz-plane is
equal to the number of faces that are parallel to the
yz-plane and there is only one face parallel and above
the xy-plane.
Definition 4.3 A plane partition of type is a plane
partition of type E such that the matrix obtained from its
corresponding two-lin e matrix with nonzero entries after
subtracting 1 from each entry and adding to is
of the form (6).
1
e1
c
Figure 10 gives an example of a plane partition of
type . Observe that there is only one face (on the
plane 1) parallel and above the xy-plane. With
this definitions and the discussion above we now state
our last theorem.
=1z
Figure 11. The lattice path.
Figure 12. The plane partition.
Theorem 4.5 The number of plane partitions of n of
type is equal to the number of unrestricted parti-
tions of n.
5. References
[1] P. Mondek, A. C. Ribeiro and J. P. O. Santos, “New
Two-Line Arrays Representing Partitions,” Annals of
Combinatorics, Vol. 15, No. 2, 2011, pp. 341-354.
doi:10.1007/s00026-011-0099-0
[2] L. J. Slater, “Further Identities of the Rogers-Ramanujan
type,” Proc. London Math. Soc., Vol. 54, No. 2, 1952, pp.
Copyright © 2011 SciRes. OJDM
M. ALEGRI ET AL.
Copyright © 2011 SciRes. OJDM
115
147-167. doi:10.1112/plms/s2-54.2.147
[3] E. H. M. Brietzke, J. P. O. Santos and R. Silva, “Bijective
Proofs Using Two-Line Matrix Representations for Parti-
tions,” The Ramanujam Journal, Vol. 23, 2010, pp. 265-
295. doi:10.1007/s11139-009-9207-8
[4] G. E. Andrews, “Three-Quadrant Ferrers Graphs,” Indian
Journal of Mathematics, Vol. 42, 2000, pp. 1-7.
[5] E. H. M. Brietzke, J. P. O. Santos and R. Silva, “Combi-
natorial Interpretations as Two-Line Array for the Mock
Theta Functions,” Submitted.
[6] M. Alegri, “Interpretações para Identidades Envolvendo
Sobrepartições e Partições Planas,” Ph.D. Thesis, IME
CC-Universidade Estadual de Campinas, Campinas-SP,
2010.