A RECURRENCE RELATION FOR MULTIPLE CATALAN
NUMBERS
A Thesis
by
MERSEDEH BIGLARI SEFIDI
Submitted to the O ce of Graduate Studies
of Texas A&M University-Commerce
in partial ful llment of the requirements
for the degree of
MASTER OF SCIENCE
May 2016
A RECURRENCE RELATION FOR MULTIPLE CATALAN
NUMBERS
A Thesis
by
MERSEDEH BIGLARI SEFIDI
Approved by:
Advisor: Hasan Coskun
Committee: Padmapani Seneviratne
Pamela Webster
Head of Department: Tingxiu Wang
Dean of the College: Brent Donham
Dean of Graduate Studies: Arlene Horne
iii
Copyright
c
MERSEDEH BIGLARI SEFIDI
iv
ABSTRACT
A RECURRENCE RELATION FOR MULTIPLE CATALAN NUMBERS
Mersedeh B. Se di, MS
Texas A&M University-Commerce, 2016
Advisor: Hasan Coskun, PhD
The goal of this project was to nd a recurrence formula for certain q and qt
analogs of classical Catalan numbers, and study such formulas in detail in the
two dimensional case. To this end, we reviewed de nitions and fundamental
properties of classical Catalan numbers, q-Catalan numbers, and qt-Catalan
numbers such as their generating functions and recursive relations.
We found four recurrence relations in the literature for the classical Catalan
numbers. We were able to generalized one of them to the q case and the mul-
tiple qt case. In fact, we wrote the recurrence relation in two di erent ways: in
terms of rational Macdonald functions, and in combinatorial form in terms of
Young tableau. Moreover, we worked simpli ed versions of both these n dimen-
sional formulas in the two dimensional case to investigate possible connections
to the classical case. This project covers one aspect of a new line of research in
mathematics, and generalizes useful identities to higher dimensions.
ACKNOWLEDGMENTS
First, I would like to express my deepest gratitude to my advisor, Dr. Hasan
Coskun, for the endless support he provided. His patience, encouragement, and
guidance motivated me throughout my studies. If it wasn't for his belief in me,
I never would have experienced the delight of working on this thesis. From him,
I learned not only mathematics, but also how to be a better instructor.
I am indebted to Dr. Tingxiu Wang, the department head, and my com-
mittee members Dr. Padmapni Seneviratne and Dr. Pamela Webster in the
Mathematics Department of Texas A&M-Commerce University for reading my
thesis and for their valuable comments on the formatting of this paper. Much
gratitude also goes to Leanne Farquhar, Christina Gammon, and Diana Hines
for the quick responses to emails for the information I needed.
Finally, I express gratitude to my parents for their faith and prayer, to my
husband for his unconditional love and support, to my intelligent son for his
encouragement and assistance with technology, and to my wonderful daughters
for their kind words and teddy bears.
CONTENTS
1. Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1
2. Background : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4
2.1 The Limiting w = Function . . . . . . . . . . . . . . . . . . . . 5
2.2 The Multiple qt-Binomial Coe cients . . . . . . . . . . . . . . . 6
2.3 Classical Catalan Numbers . . . . . . . . . . . . . . . . . . . . . 8
2.3.1 Recurrence relation for the classical Catalan numbers . . 8
2.3.2 A Generating Function for the Classical Catalan Numbers 9
2.4 The q-Catalan Numbers . . . . . . . . . . . . . . . . . . . . . . 10
2.4.1 Recurrence Relation for the q-Catalan Numbers . . . . . 11
2.4.2 A New Recurrence Relation for the q-Catalan Numbers . 12
2.5 The Multiple qt-Catalan Numbers . . . . . . . . . . . . . . . . . 15
2.5.1 The qt-Catalan numbers . . . . . . . . . . . . . . . . . . 15
2.5.2 The Multiple qt-Catalan numbers . . . . . . . . . . . . . 16
2.5.3 A Recurrence Relation for qt-Catalan Numbers . . . . . 18
2.5.4 Combinatorial Formula for the Recurrence Relation . . . 31
3. Future Research : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 40
vii
4. References : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41
5. VITA : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 46
viii
LIST OF TABLES
2.1 q-Catalan numbers . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 qt-Catalan numbers . . . . . . . . . . . . . . . . . . . . . . . . . 16
ix
LIST OF FIGURES
2.1 Young diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2 Young tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1
1. INTRODUCTION
Catalan numbers are the most special sequence among the combinatorial
numbers since it gives solutions to many counting problems. Catalan numbers
are a great source of both fun and excitement for students and professional
mathematicians. In Grimaldi's book [24], one can nd many examples where
Catalan numbers arise as well as general ideas about the Catalan numbers, to-
gether with a survey and uni cation of the q-analogs of Catalan numbers. Many
recent publications study various aspects of Catalan numbers. Speci cally, their
history, recurrence relations, various de nitions, applications in combinatorics,
extensions to q-Catalan numbers, relations to hypergeometric series [6], the two
parameter extension to qt-Catalan numbers, their generating functions [42],
[45], and their combinatorial interpretations have been investigated [41]. By
reviewing this information, one begins to understand the development of higher
qt-Catalan numbers. In this paper, the focus has been nding recurrence re-
lations for qt-Catalan numbers, and studying such formulas in detail in the
two-dimensional case, which is a unique task on Catalan numbers research.
In the eld of combinatorial mathematics, the sequence of Catalan numbers
f1,1,2, 5,14,42,132, 429, 1430, . . . g are natural numbers that come up in many
2
counting problems [44]. These counting problems typically involve objects that
are de ned recursively. A closed formula may be written in terms of the binomial
coe cients in the form
Cn =
1
(n + 1)
2n
n
(1.1)
The name Catalan is derived from Eugene Charles Catalan, a Belgian math-
ematician who was born in 1814 and passed away in 1894 [39]. He was one of
the rst few people to work on this sequence.
There are numerous scholarly articles and books on classical, q, and qt Cata-
lan numbers. Catalan numbers have been studied throughout history and in var-
ious elds of mathematics since they were discovered. However, one-dimensional
and multi-dimensional extensions are fairly new objects, yet to be studied ex-
tensively as the classical Catalan numbers. The generalization by Garsia and
Haglund in a series of papers on qt-Catalan numbers is perhaps the most general
version. Their de nition involves two parameters, but not multi-dimensional,
and are not indexed by partitions. It was the work of Dr. Coskun that intro-
duced the multi-dimensional qt analogues, and developed some of their prop-
erties [12],[13],[15]. By comparing and contrasting existing work on Catalan
numbers, it is plausible that higher dimensional qt analogues would have inter-
esting combinatorial interpretations, closed formulas, and generating functions.
This study uses the idea of generalizing one of the recurrence relations (out
of four distinct ones found in the literature) of classical Catalan numbers to
the q-case and the multiple qt-case. We write a new recurrence relation in two
3
di erent ways in terms of rational Macdonald functions, and in combinatorial
form in terms of Young tableau. Next, we write the explicit versions of both
these n dimensional formulas in the two dimensional case. In summary, our work
presents ve new results: a new recurrence relation for q-Catalan numbers, and
a new recurrence relation for qt-Catalan numbers written in two new forms, and
each of their explicit representations in the two dimensional case.
4
2. BACKGROUND
The q-Pochhammer symbol (a; q) may be de ned as:
(a) = (a; q) :=
(a; q)1
(aq ; q)1
(2.1)
for complex parameters q; 2 C. Here (a; q)1 in the formula is de ned to be
the in nite product (a; q)1 :=
Q1
i=0(1aqi). If = m is a nonnegative integer,
we will get the nite product (a; q)m =
Qm1
k=0 (1 aqk).
For higher dimensional formulas, we will consider sequences indexed by par-
titions = ( 1; : : : ; n) with n parts. For t 2 C, we will need the following
partition generalization
(a) = (a; q; p; t) :=
Yn
i=1
(at1i; q; p) i : (2.2)
Note that, if = ( 1) = 1 is a partition with one part (i.e., an integer) then
(a; q; p; t) = (a; q; p) 1 = (a) 1 .
5
2.1 The Limiting w = Function
The rational Macdonald functions w and BCn abelian functions are basi-
cally equivalent functions which were independently constructed in Coskun's [12]
and Rain's book [40]. Risearchers nd that the limited cases are closely related
with Macdonald polynomials [37], and interpolation Macdonald polynomials
found in Okounkov paper [38] as pointed out in Dr. Coskun's work [12].
For this paper, we mention some properties of w = in [12] as the limiting of
the basic (i.e., p is zero) W function.
First we review some notation for certain partition statistics [11]. Namely,
j j =
Pn
i=1 i and n( ) =
Pn
i=1(i 1) i, and n( 0) =
Pn
i=1
i
2
, and
t (n) = (t(n1); t(n2); : : : ; t; 1).
For n part partitions and , we also de ne H = (q; t) as
H = (q; t) :=
Y
1 i<j n
(q i j1tji) j1 j
(q i j1+1tji1) j1 j
(q i j1+1tji1) j1 j
(q i j1tji) j1 j
(2.3)
Next, for x 2 C, we de ne
w = (x; q; t) := (q=x)j j+j jqn( 0)+n( 0)H = (q; t)
(x1)
(x1)
(2.4)
6
Finally, the recurrence formula for w = function can now be written as
w = (y; z; q; t) =
X
t`(j jj j)w = (yt`; q; t)w = (z; q; t) (2.5)
Among many interesting properties of the w = , we will use below the fol-
lowing identities: If z = xt (n) (x is a complex number), then we have:
w (xt (n); q; t) = (1)j jxj jtn( )qj jn( 0)(x1)
Y
1 i<j n
(tji+1) i j
(tji) i j
(2.6)
We also know from Coskun's paper [12] if = k = (k; k; ; k) is an n-part
partition, and z = (x1; x2; ; xn) 2 Cn we have:
w k(z; q; t) = qnk
Yn
i=1
(q1kxi)k (2.7)
2.2 The Multiple qt-Binomial Coe cients
For the de nition of multidimensional Catalan numbers, we use general-
izations of binomial coe cients as we did for the one dimensional case. The
multiple qt-binomial coe cient is de ned [10] as follows:
Let = ( 1; 2; ; n) which is a partition with n parts and z be an n-
tuple (x1; : : : ; xn) 2 Cn of complex numbers. Then the qt-binomial coe cient
7
is given by:
z
qt
:=
qj jt2n( )+(1n)j j
(qtn1)
Y
1 i<j n
(qtji) i j
(qtji1) i j
w (qzt (n); q; t) (2.8)
for q; t 2 C. This de nition is valid even for 2 Cn. Note that for n = 1, the
above de nition becomes the same as the Gaussian coe cients (that is, the one
dimensional q-binomial coe cients).
n
k
q
:=
(q)n
(q)nk(q)k
(2.9)
[4], [5], [22], [23], [21], [37], [7], [9].
Several properties of the qt-binomial will be needed below. For example, in
the case of z = x = (x; : : : ; x) 2 Cn, we have the following result:
x
qt
=
t2n( )+(1n)j j
(qtn1)
(qx; q1; t1)
Y
1 i<j n
(qtji) i j
(qtji1) i j
(tji+1) i j
(tji) i j
(2.10)
This identity is established independently in [34].
Another special case is when is a rectangular partition, that is = k. In
that case we get
z
k
qt
=
Yn
i=1
(q1kqxitni)k
(qtni)k
(2.11)
In particular for k = 1, the de nition reduces to
z
1
qt
=
Yn
i=1
(qxitni)1
(qtni)1
=
Yn
i=1
(1 qxitni)
(1 qtni)
(2.12)
8
2.3 Classical Catalan Numbers
In combinatorics, we remarked that the Catalan numbers constructed as a
unique sequence of natural numbers that are demonstrated in di erent counting
problems. These problems sometimes involve recursively de ned objects. The
Catalan number Cn, for example, may be viewed as the number of ways of
associating a product of n+1 terms. This is but one of the many other situations
where these numbers arise. As we noted before, an explicit formula is given by
Cn =
1
(n + 1)
2n
n
(2.13)
Thus the rst few Catalan numbers may be easily computed to give the
values as in the following list f1; 1; 2; 5; 14; 42; 132; 429; 1430; : : :g by substituting
n = 1; 2; 3; 4; : : : in this formula.
Besides the closed formula given above, another expression for Cn is written
explicitly as
Cn =
2n
n
2n
n + 1
(2.14)
for n 0. Both these formulas may be found in [16] and [39].
2.3.1 Recurrence relation for the classical Catalan numbers
One may nd the recurrence relations for the classical Catalan numbers in
many books in the literature. We quote the following relations from [17]. First,
9
we have
Cn+1 =
Xn
i=0
(CiCni); C0 = 1: (2.15)
Note that this may be written as
Cn+1 = C0Cn + C1Cn2 + + CnC0 (2.16)
Note also that the closed formula Cn = 1=(n + 1)
2n
n
given above may be
derived from this Catalan recurrence.
A di erent recurrence relation for classical Catalan numbers is given by the
identity:
Cn+1 =
2(2n + 1)
n + 2
Cn; C0 = 1: (2.17)
This can be more e cient for calculating Catalan numbers.
2.3.2 A Generating Function for the Classical Catalan Numbers
A generating function for Cn may be calculated from the rst recurrence (2.15)
mentioned above. We rst multiply both sides by xn, and sum both sides over
all values of n from 0 to 1. This gives two candidates for a recurrence relation.
C(x) =
1
p
1 4x
2x
: (2.18)
The generating function satis es C(0) = 1. Substituting 0 for either form
of C(x) gives a fraction with denominator of zero. However, limx!0+ C(x) is
10
the indeterminate form 0/0 for the negative square root and the same limit
evaluates to 1 for the positive square root, so this gives an unde ned fraction.
If we apply L'Hopital's rule, we have
lim
x!0+
1
p
1 4x
2x
= 1 (2.19)
The other square root does evaluate to the correct number, so the generating
function for Cn is:
C(x) =
1
p
1 4x
2x
: (2.20)
2.4 The q-Catalan Numbers
A q-analog of the Catalan numbers has been de ned by Carlitz and Rior-
dan [17],[43], and [8]) as follows
Cn(q) =
1
[n + 1]
2n
n
q
(2.21)
Here the q-bracket can be de ned by:
[n]q = [n] =
1 qn
1 q
=
X
0 i<n
qi = 1 + q + q2 + q3 + + qn1 (2.22)
By this notation, we can write the q-analogue of the binomial coe cients in the
form:
n
k
q
=
[n]q!
[k]q![n k]q!
(2.23)
11
where [n]q! = [n]! = [n][n 1] [1].
Using this formula, the rst few q-Catalan numbers are calculated as listed
below.
C0(q) = 1
C1(q) = 1
C2(q) = 1 + q
C3(q) = 1 + 2q + q2 + q3
C4(q) = 1 + 3q + 3q2 + 3q3 + 2q4 + q5 + q6
: : :
Tab. 2.1: q-Catalan numbers
Note that when q ! 1, then Cn(q) is reduced as the classical Catalan num-
bers Cn.
2.4.1 Recurrence Relation for the q-Catalan Numbers
Various recursive relations for q-Catalan numbers have been given in dif-
ferent forms. For example, Carlitz and Riordan ([17],[43], and [8]), de ned
q-Catalan numbers by the recurrence relation
Cn(q) =
Xn1
k=0
qkCk(q)Cnk1(q) (2.24)
with C0(q) = 1. We may obtain di erent values of q-Catalan numbers for
n = 0; 1; 2; : : : by using the above recurrence relation.
12
There are at least two other interesting forms of recurrence relations found
in the work of Andrews [1] as Theorem 1 and Theorem 2. These recurrence
relations are written as q-series identities in the form
Cn+1(q) =
X
r 0
q2r2+2r
n
2r
q
Cr(q)
(qr+2; q)nr
(q; q)r
(2.25)
and
Cn(q) =
Xn
r=1
(1)r1qr2r
n r + 1
r
q
Cnj(q)
(qnr+1; q)r
(q; q)r
(2.26)
2.4.2 A New Recurrence Relation for the q-Catalan Numbers
Besides the three recurrences, we may write another recurrence relation for
q-Catalan numbers by generalizing the recurrence relation that we mentioned
in classical form (2.16)
Cn+1 =
2(2n + 1)
n + 2
Cn; C0 = 1: (2.27)
We will generalize this recurrence relations, for both the case of q-Catalan
numbers, and later in the next section for the case of qt-Catalan numbers.
Theorem 1. Let n be a positive integers, then the recurrence relation for q-
Catalan numbers is:
Cn+1(q) =
(1 + qn+1)(1 q2n+1)
(1 qn+2)
Cn(q) (2.28)
13
Proof: We take a similar approach to the classical case for nding the re-
currence relation for q-Catalan numbers. Recall that the closed formula for
q-Catalan numbers is
Cn(q) =
1 q
1 qn+1
2n
n
q
: (2.29)
which, for n + 1, becomes
Cn+1(q) =
1 q
1 qn+2
2(n + 1)
n + 1
q
: (2.30)
On the other hand, we know
2n
n
q
=
[2n]!
[2n n]! [n]!
(2.31)
Thus, by dividing previous formulas, we get
Cn+1(q)
Cn(q)
=
1q
1qn+2
2(n+1)
n+1
q
1q
1qn+1
2n
n
q
(2.32)
By using the de nition of the q-binomial coe cient formula, we write the last
identity as
Cn+1(q)
Cn(q)
=
1 qn+1
1 qn+2
[2n + 2]! [n]! [n]!
[2n]! [n + 1]! [n + 1]!
(2.33)
14
which becomes
Cn+1(q)
Cn(q)
=
1 qn+1
1 qn+2
[2n + 2][2n + 1] [1]] [n][n 1] [1] [n][n 1] [1]
[2n][2n 1] [1] [n + 1][n] [1][n + 1][n] [1]
(2.34)
After simplifying the above fraction, we get
Cn+1(q)
Cn(q)
=
1 qn+1
1 qn+2
[2n + 2][2n + 1]
[n + 1][n + 1]
(2.35)
Simpli cation of the expanded formula gives us
Cn+1(q)
Cn(q)
=
1 qn+1
1 qn+2
1q2n+2
1q
1q2n+1
1q
1qn+1
1q
1qn+1
1q
(2.36)
Finally, summarizing the calculations above, we have
Cn+1(q)
Cn(q)
=
(1 + qn+1)(1 q2n+1)
(1 qn+2)
(2.37)
It is clear that we can write the above formula in the form
Cn+1(q) =
(1 + qn+1)(1 q2n+1)
(1 qn+2)
Cn(q) (2.38)
and this is the desired recurrence formula for q-Catalan numbers.
To the best of my knowledge, this result is new and has not been written
before.
15
2.5 The Multiple qt-Catalan Numbers
In his paper [10], Dr. Coskun presents numerous analogues of important
categories of number sequences and has developed many of their fundamental
properties. In my paper, I pursued a recurrence formula for the qt-Catalan
numbers, and study it in detail in the two-dimensional case.
2.5.1 The qt-Catalan numbers
I would like to start with a quick introduction to another class of qt-Catalan
numbers. Garsia and Haiman introduced qt-Catalan numbers and the higher
qt-Catalan number in studying symmetric functions and Macdonald polynomi-
als [19]. Their de nition of the qt-Catalan sequence is given by the combinatorial
formula
Cn(q; t) =
X
`n
t2
P
lq2
P
a(1 t)(1 q)
Q0;0(1 qa0tl0)
P
qa0tl0
Q
(qa tl+1)(tl qa+1)
(2.39)
where the sum is over all partitions of the index n, and
Q0;0 means the product
skips the corner cell in the Young diagram of the partition [18].
It should be noted that, by specializing the values of q and t in the qt-Catalan
numbers, one also recovers the q-Catalan numbers from this de nition.
The combinatorial symbols used in the formula are de ned as follows: Let
s = (i; j) be a square in the Young diagram of a partition . Then, the arm
length is a = a(s) = a (s) = ij, the arm colength a0 = a0(s) = a0
(s) = j1,
16
the leg length l = l(s) = l (s) = 0
i j where 0 is the dual partition, and the
leg colength l0 = l0(s) = l0
(s) = i 1.
The qt-Catalan numbers are currently known to be polynomials in q and t.
You may nd the table of these polynomials in Garsia and Haiman's paper [19].
The rst few of those polynomials are:
C1 = 1
C2 = q + t
C3 = q3 + qt + q2t + qt2 + t3
C4 = q6 + q3t + q4t + q5t + q2t2 + q3t2 + q4t2 + qt3 + q2t3 + q3t3 + qt4
+q2t4 + qt5 + t6
: : :
Tab. 2.2: qt-Catalan numbers
The fundamental properties of these numbers are covered in Haiman [30],
Haglund [28] and [26], and Garsia and Haglund [20]. Recent studies on this topic
pursued mainly two directions: various extensions [35], [36], and the structural
features of the (higher) qt-Catalan numbers [32], [29], [25]. It came to promi-
nence within the last 20 years in an increasing number of contexts in multiple
areas of mathematics. Haglund's book [27] gives a complete tutorial on these
numbers.
2.5.2 The Multiple qt-Catalan numbers
The sequences of combinatorial numbers have been widely investigated for
their properties and extensions. Many mathematicians have spent their time to
17
investigating principles of q-generalization and the applications of these prin-
ciples in connections with other types of numbers. It was through the work
of Dr. Coskun [10] that numerous multiple qt-analogues of categories of com-
binatorial numbers have been constructed for the rst time, except the case
of qt-binomial coe cients. The qt-binomial coe cients were constructed inde-
pendently by Kaneko, [31] in a special case, and Okounkov[38] using di erent
operator methods for integer partitions [12]. Dr. Coskun [10] developed the
most general version of the qt-binomial coe cients, and investigated their prop-
erties as an interesting project in their own right. Moreover, he also extended
the idea to other combinatorial number sequences, one of the multi-dimensional
generalizations of which is the multiple qt-Catalan numbers.
It should be pointed out that the de nition of qt-Catalan numbers by Garsia
and Haiman is indexed by positive integers, and thus it is one-dimensional. On
the other hand, Coskun's de nition is multidimensional and is titled 'multiple'
qt-Catalan numbers to avoid possible confusions. This family of multiple num-
bers reduces to single dimensional q-Catalan numbers in the one-dimensional
case for n = 1, which is studied in [8], [3], [2], [19], and [17].
The main focus of this paper is nding a recurrence relation for the multiple
qt-Catalan numbers, and studying that formula in it's explicit form in the two
dimensional case. I would like to also point out that I have used Wolfram's
Mathematica software to check my formulas and make sure that my results are
free of any typographical errors.
The de nition of the multiple qt-Catalan number C we used in this paper
18
may be stated as follows [14]. Let = ( 1; 2; ; n) be an n-part partition.
Then
C :=
1
[ + 1]q;t
2
q;t
(2.40)
Here, 1
= (1; : : : ; 1) with n copies of 1 as before, and the multiple bracket
function [ ]q;t is de ned as usual:
[ ]q;t =
1
q;t
(2.41)
for any partition .
2.5.3 A Recurrence Relation for qt-Catalan Numbers
I take the same approach that I used for the q-Catalan numbers and write a
generalized recurrence formula for the qt-Catalan numbers. In other words, we
calculate the fraction
C + 1
(q; t)
C (q; t)
(2.42)
This yields the multiple analogue for the same recurrence.
Theorem 2. Let be an n-part partition. Then the recurrence relation for the
multiple qt-Catalan number is:
C + 1
C
=
Yn
i=1
(1 q i+1tni)
(1 q i+2tni)
2( + 1)
+ 1
qt 2
qt
(2.43)
19
Proof: We write the recurrence relation for qt-Catalan by dividing C + 1
(q; t)
by C (q; t), as in the one-dimensional case.
Thus,
C + 1
C
=
1
( +2
1
)q;t
2( + 1)
+ 1
q;t
1
( +1
1
)q;t
2
q;t
(2.44)
By using the binomial formula given above we get the following result:
1 +2
1
q;t
=
1
qj 1
jt2n( 1)+(1n)j 1
j
(qtn1) 1
:
Q
1 i<j<nf
(qtji) i j
(qtji1) i j
g:w 1
(q +2t ; q; t)
(2.45)
And also, we have:
1 +1
1
q;t
=
1
qj 1
jt2n( 1)+(1n)j 1
j
(qtn1) 1
:
Q
1 i<j<nf
(qtji) i j
(qtji1) i j
g:w 1
(q +1t ; q; t)
(2.46)
We see that the front factor may cancel if we divide the above formulas by
each other. Thus, we may get rid of the front factor and have mainly the two
w functions. We now take the ratio
1 +2
1
q;t
1 +1
1
q;t
=
+1
1
q;t +2
1
q;t
(2.47)
20
of the two identities above, and write it as
1
qj 1jt2n( 1)+(1n)j 1j
(qtn1) 1
:
Q
1 i<j<nf
(qtji) i j
(qtji1) i j
g:w 1
(q +2t ; q; t)
1
qj 1jt2n( 1)+(1n)j 1j
(qtn1) 1
:
Q
1 i<j<nf
(qtji) i j
(qtji1) i j
g:w 1
(q +1t ; q; t)
(2.48)
This gives
1 +2
1
q;t
1 +1
1
q;t
=
w 1
(q +1t ; q; t)
w 1
(q +2t ; q; t)
(2.49)
Thus, we have
C + 1
C
=
w 1
(q +1t ; q; t)
2( + 1)
+ 1
qt
w 1
(q +2t ; q; t)
2
qt
(2.50)
By using the identity 2.7,
w k(z; q; t) = qnk
Yn
i=1
(q1kxi)k (2.51)
and setting k = 1, we get
C + 1 C
=
q2(1)Qn
i=1(q11q i+1tni)1
2( + 1)
+ 1
qt
q2(1)
Qn
i=1(q11q i+2tni)1
2
qt
(2.52)
21
Finally, this gives
C + 1
C
=
Qn
i=1(q i+1tni)1
2( + 1)
+ 1
qt Qn
i=1(q i+2tni)1
2
qt
=
Yn
i=1
(1 q i+1tni)
(1 q i+2tni)
2( + 1)
+ 1
qt 2
qt
(2.53)
as desired.
This is the n dimensional version of the recurrence relation. I would like
to write this more explicitly in the two dimensional case so that I can readily
compare with the one dimensional formula.
Theorem 3. In two dimensional case, we have
C + 1
C
=
q2
(1 q 1+2t)(1 q 2+2)
:
w + 1
(q2( + 1)t (n); q; t)
w (q2 t (n); q; t)
(2.54)
Proof: Consider n = 2 in the previous theorem. We get:
C + 1
C
=
(1 q 1+1t)(1 q 2+1)
(1 q 1+2t)(1 q 2+2)
2( + 1)
+ 1
qt 2
qt
(2.55)
Next, we need to do some more simpli cation on the other part of our
fraction. Again, we use the de nition of the qt-binomial coe cients, which
gives the following result:
22
2( + 1)
+ 1
qt 2
qt
=
qj + 1
jt2( 2+1)j + 1
j
(qt) 1+1(q) 2+1
(qt21)( 1+1)( 2+1)
(qt211)( 1+1)( 2+1)
qj jt2 2+(12)j j(qt) 1 2
(qt) (q) 1 2
w + 1
(q2( + 1)t (n); q; t)
w (q2 t (n); q; t)
(2.56)
Now, by using the q-Pochhammer symbol (a; q)m =
Qm1
k=0 (1 aqk), and
simplifying the formula we get
2( + 1)
+ 1
qt 2
qt
=
qj + 1
jt 2 1
(qt) 1+1(q) 2+1
qj jt 2 1
(qt)
(qt) 1 2
(q) 1 2
(qt) 1 2
(q) 1 2
:
w + 1
(q2( + 1)t (n); q; t)
w (q2 t (n); q; t)
(2.57)
We clearly can simplify the middle fraction further, and to get:
2( + 1)
+ 1
qt 2
qt
=
qj +1j(qt)
qj j(qt) 1+1(q) 2+1
:
w + 1(q2( + 1)t (n); q; t)
w (q2 t (n); q; t)
(2.58)
The q-Pochhammer symbols also simplify to give
2( + 1)
+ 1
qt 2
qt
=
q2
(1 q 1+1t)(1 q 2+1)
w + 1
(q2( + 1)t (n); q; t)
w (q2 t (n); q; t)
(2.59)
23
Thus, from the above formula we have:
C + 1
C
=
(1 q 1+1t)(1 q 2+1)
(1 q 1+2t)(1 q 2+2)
q2
(1 q 1+1t)(1 q 2+1)
w + 1
(q2( + 1)t (n); q; t)
w (q2 t (n); q; t)
(2.60)
Finally, after further simpli cation, we get:
C + 1
C
=
q2
(1 q 1+2t)(1 q 2+2)
w + 1
(q2( + 1)t (n); q; t)
w (q2 t (n); q; t)
(2.61)
which is the result we want to obtain.
In this theorem, we have two w functions. I would like to write them in
explicit form in two dimensional case to investigate a more simpli ed formula
for this recurrence relation. Therefore, we need to nd a formula for the w
functions in two variables. I used a formula for qt binomial coe cient obtained
in the work of Dr. Coskun and his student Rachel Landers in her MS thesis [33]
to write an explicit formula for w function in two dimensional case. We will
then use this formula to write the recurrence relation for qt-Catalan numbers.
Lemma 1. Let and be a 2-part partition. Then, the w function in two
24
variables may be written explicitly as a summation as follows:
w (q t (n); q; t)
=
(1) 1q 1 1+ 1 2(t) 1q
1
2 ( 1 21
)q 1 2 1 2(q 1) 1(t1q 1) 2(qt) 1
(q 1t1) 2(q) 1 2(t) 1 2(q) 1(qt) 1 2
:
X 1
2
qi 2(i
2)(t)i(q 2)i(q) 1i(q 1i+1)i 2(t)i 2(q 2+i+1) 1i(t) 1i (2.62)
Proof: The proof follows from the de nition of qt binomial coe cients. Re-
call that the qt binomial coe cient is de ned by :
qt
:=
qj jt2n( )+(1n)j j
(qtn1)
Y
1 i<j n
(qtji) i j
(qtji1) i j
w (q t (n); q; t) (2.63)
In the thesis paper [33] mentioned above, we nd an explicit formula (with some
typos xed here) for the two-dimensional case of the qt-binomial coe cient as
follows
q;t
=
q 1 1+ 1 1t 2(1) 1q
1
2 ( 1 22
)(q 1) 1(q 1t1) 2
(t1q 1) 2(q)3
1 2(q) 2(t) 1 2(q) 1
:
X 1
2
qi 2(i
2)(t)i(q 2)i(q) 1i(q 1i+1)i 2
(t)i 2(q) 1 2(q 2+i+1) 1i(t) 1i (2.64)
25
Since these are equal, we get
q 1 1+ 1 1t 2(1) 1q
1
2 ( 1 22
)(q 1) 1(q 1t1) 2
(t1q 1) 2(q)3
1 2(q) 2(t) 1 2(q) 1
:
X 1
2
qi 2(i
2)(t)i(q 2)i(q) 1i(q 1i+1)i 2(t)i 2(q) 1 2(q 2+i+1) 1i(t) 1i
=
qj jt2n( )+(1n)j j
(qtn1)
Y
1 i<j n
(qtji) i j
(qtji1) i j
w (q t (n); q; t) (2.65)
To nd the w function, we just need to divide the left hand side by the multiple
of w function in the above formula. So, we get:
w (q t (n); q; t) =
q 1 1+ 1 1t 2(1) 1q
1
2 ( 1 22
)(q 1) 1(q 1t1) 2
(t1q 1) 2(q)3
1 2(q) 2(t) 1 2(q) 1
(qt21)
qj jt2n( )+(12)j j
(qt211) 1 2
(qt21) 1 2
:
X 1
2
qi 2(i
2)(t)i(q 2)i(q) 1i(q 1i+1)i 2(t)i 2(q) 1 2(q 2+i+1) 1i(t) 1i
(2.66)
After some calculation, we get the desired result given above.
Now, we use this explicit formula for w function in the following theorem
that was promised above. Namely, we investigate a more explicit recurrence for
qt-Catalan numbers in the two dimensional case.
Theorem 4. Let be a 2-part partition. Then, the recurrence relation for the
26
multiple qt-Catalan number is:
C + 1
C
=
t(tq2 1+2 1)(tq2 1+1 1)
(1 q 1+2t)(1 q 2+2)(q 1+1 1)(tq2 1 2+1 1)
:
P 1+1
i= 2+1 qi2( 2+1)(i
2)(t)i(q2( 2+1))i(q)2( 1+1)i(q 1+1i+1)i( 2+1)
P 1
i= 2
qi2 2(i
2)(t)i(q2 2)i(q)2 1i(q 1i+1)i 2
,!
(t)i( 2+1)(q( 2+1)+i+1) 1+1i(t) 1+1i
(t)i 2(q 2+i+1) 1i(t) 1i
(2.67)
Here, ,! means that the formula extends to the next line. The second line should
not be considered as a factor in a multiplication.
Proof: We begin the identity in Theorem 3. We then use Lemma 1 to
substitute the numerator and denominator of the last fraction by w function
formulas. Recall that
C + 1
C
=
q2
(1 q 1+2t)(1 q 2+2)
:
w + 1
(q2( + 1)t (n); q; t)
w (q2 t (n); q; t)
(2.68)
First, we rewrite the formula for w + 1(q2( + 1)t (n); q; t) using Lemma 1
w + 1
(q2( + 1)t (n); q; t)
=
q
3
2 1
2+7
2 1+ 1 2+1t 1+1(1) 1+1(q2( 1+1)) 1+1(t1q2( 1+1)) 2+1(qt) 1+1
(t1q 11)) 2+1(q) 1 2(t) 1 2(q)2( 1+1)(qt) 1 2
:
X1+1
i= 2+1
qi2( 2+1)(i
2)(t)i(q2( 2+1))i(q)2( 1+1)i
(q( 1+1)i+1)i( 2+1)(t)i( 2+1)(q( 2+1)+i+1) 1+1i(t) 1+1i (2.69)
27
Next, we rewrite the formula for w (q2 t (n); q; t) again using Lemma 1.
w (q2 t (n); q; t) =
q
3
2 1
21
2 1+ 1 2 2t 1(1) 1(q2 1) 1(t1q2 1) 2(qt) 1
(t1q 1)) 2(q) 1 2(t) 1 2(q)2 1(qt) 1 2
:
X 1
i= 2
qi2 2(i
2)(t)i(q2 2)i(q)2 1i
(q 1i+1)i 2(t)i 2(q 2+i+1) 1i(t) 1i (2.70)
Now, by dividing the two results for the w function evaluations above, we have
w + 1
(q2( + 1)t (n); q; t)
w (q2 t (n); q; t)
=
tq4 1+ 2+1(q2( 1+1)) 1+1(t1q2( 1+1)) 2+1(qt) 1+1(t1q 1) 2(q)2 1
(t1q( 1+1)) 2+1(q)2( 1+1)(q2 1) 1(t1q2 1) 2(qt) 1 P 1+1
i= 2+1 qi2( 2+1)(i
2)(t)i(q2( 2+1))i(q)2( 1+1)i(q 1+1i+1)i( 2+1)
P 1
i= 2
qi2 2(i
2)(t)i(q2 2)i(q)2 1i(q 1i+1)i 2
,!
(t)i( 2+1)(q( 2+1)+i+1) 1+1i(t) 1+1i
(t)i 2(q 2+i+1) 1i(t) 1i
(2.71)
In the previous formula, I found
C + 1
C
=
q2
(1 q 1+2t)(1 q 2+2)
:
w + 1
(q2( + 1)t (n); q; t)
w (q2 t (n); q; t)
(2.72)
28
Now, we substitute w + 1
(q2( + 1)t (n);q;t)
w (q2 t (n);q;t) with the formula we just found to write
C + 1
C
=
q2
(1 q 1+2t)(1 q 2+2)
:
tq4 1+ 2+1(q2( 1+1)) 1+1(t1q2( 1+1)) 2+1(qt) 1+1(t1q 1) 2(q)2 1
(t1q( 1+1)) 2+1(q)2( 1+1)(q2 1) 1(t1q2 1) 2(qt) 1
:
P 1+1
i= 2+1 qi2( 2+1)(i
2)(t)i(q2( 2+1))i(q)2( 1+1)i(q 1+1i+1)i( 2+1)
P 1
i= 2
qi2 2(i
2)(t)i(q2 2)i(q)2 1i(q 1i+1)i 2
,!
(t)i( 2+1)(q( 2+1)+i+1) 1+1i(t) 1+1i
(t)i 2(q 2+i+1) 1i(t) 1i
(2.73)
We are able to simplify some of the terms of the front factor in the above
formula. For example,
(qt) 1+1
(qt) 1
= (1 q 1+1t) (2.74)
and we may simplify
(q)2 1
(q)2( 1+1)
=
1
(1 q2 1+1)(1 q2 1+2)
(2.75)
and
(t1q 1) 2
(t1q( 1+1)) 2+1
=
q( 1+1)t
(q 1+1t 1)
(2.76)
29
Then, we get a simpli ed version
C + 1
C
=
t2q5 1+ 2+4(q2( 1+1)) 1+1(t1q2( 1+1)) 2+1
(1 q 1+2t)(1 q 2+2)(q2 1) 1(t1q2 1) 2(1 q2 1+2)(1 q2 1+1)
:
P 1+1
i= 2+1 qi2( 2+1)(i
2)(t)i(q2( 2+1))i(q)2( 1+1)i(q 1+1i+1)i( 2+1)
P 1
i= 2
qi2 2(i
2)(t)i(q2 2)i(q)2 1i(q 1i+1)i 2
,!
(t)i( 2+1)(q( 2+1)+i+1) 1+1i(t) 1+1i
(t)i 2(q 2+i+1) 1i(t) 1i
(2.77)
Since we have:
(q2( 1+1)) 1+1
(q2 1) 1
=
(q2 1+1 1)(q2 1+2 1)
q3 1+2(q 1+1 1)
; (2.78)
we further simplify to write
C + 1
C
=
t2q2 1+ 2+2(t1q2( 1+1)) 2+1
(1 q 1+2t)(1 q 2+2)(t1q2 1) 2(q 1+1 1)
:
P 1+1
i= 2+1 qi2( 2+1)(i
2)(t)i(q2( 2+1))i(q)2( 1+1)i(q 1+1i+1)i( 2+1)
P 1
i= 2
qi2 2(i
2)(t)i(q2 2)i(q)2 1i(q 1i+1)i 2
,!
(t)i( 2+1)(q( 2+1)+i+1) 1+1i(t) 1+1i
(t)i 2(q 2+i+1) 1i(t) 1i
(2.79)
Note that in the front factor, we only have two q-Pochhammer left: one in the
numerator and one in the denominator. We simplify those as well, and write
(t1q2( 1+1)) 2+1
(t1q2 1) 2
=
(1 t1q2 12) (1 t1q2 12:q 2)
(1 t1q2 1) (1 t1q2 1:q 21)
(2.80)
30
Since we simplify equal of the factors in the above fraction, we get
(t1q2( 1+1)) 2+1
(t1q2 1) 2
=
(1 t1q2 12)(1 t1q2 11)
(1 t1q2 1+ 21)
(2.81)
I factor some terms on the left hand side which leads me to the simpler fraction
(1 t1q2 12)(1 t1q2 11)
(1 t1q2 1+ 21)
=
q2 1 22(tq2 1+2 1)(tq2 1+1 1)
t(tq2 1 2+1 1)
;
(2.82)
so that we have
(t1q2( 1+1)) 2+1
(t1q2 1) 2
=
q2 1 22(tq2 1+2 1)(tq2 1+1 1)
t(tq2 1 2+1 1)
(2.83)
Now, we substitute the formula in (2.80) and we get
(q2( 1+1)) 1+1
(q2 1) 1
=
(q2 1+1 1)(q2 1+2 1)
q3 1+2(q 1+1 1)
(2.84)
Therefore, we obtain the simpli ed identity
C + 1
C
=
t(tq2 1+2 1)(tq2 1+1 1)
(1 q 1+2t)(1 q 2+2)(q 1+1 1)(tq2 1 2+1 1)
:
P 1+1
i= 2+1 qi2( 2+1)(i
2)(t)i(q2( 2+1))i(q)2( 1+1)i(q 1+1i+1)i( 2+1)
P 1
i= 2
qi2 2(i
2)(t)i(q2 2)i(q)2 1i(q 1i+1)i 2
,!
(t)i( 2+1)(q( 2+1)+i+1) 1+1i(t) 1+1i
(t)i 2(q 2+i+1) 1i(t) 1i
(2.85)
This is the explicit form of the two dimensional recurrence relation for qt-
31
Catalan numbers that does not include w functions.
2.5.4 Combinatorial Formula for the Recurrence Relation
The last formulation of the recurrence relation that we study in this paper
is written in terms of the combinatorial formula for the multiple qt-Catalan
numbers. As before, we rst write the n dimensional version, and then study
an explicit formula in the two dimensional case. In Theorem 6 of [14], Dr.
Coskun gave a combinatorial formula for multiple qt-Catalan numbers, which I
have used to nd the combinatorial recurrence relation.
First, we review some terminology. A partition = ( 1; : : : ; n) of N is a
non-increasing sequence of positive integers i that add up to N. A partition
can be represented by a Young diagram. For example, for = (5; 2) we have
Fig. 2.1: Young diagram
If s = (i; j), we de ne a0(s) = j 1, l0(s) = i 1, a(s) = i j, and
l(s) = 0
j i where 0 is the transpose partition. Note that + 1 = (6; 3) is
obtained by simply adding a square at the end of each row.
A reverse Young tableau on denotes the Young diagram together with a
lling with numbers from f1; 2; : : : ; ng to each square that decreases strictly by
columns, and decreases weakly in rows.
For example, there are 4 reverse tableaux of shape = (5; 2). They are
32
Fig. 2.2: Young tableau
2 2 1 1 1
1 1
2 2 2 1 1
1 1
2 2 2 2 1
1 1
2 2 2 2 2
1 1
The entry in box s = (i; j) is denoted by T(s). For example T(1; 4) = 1
for the rst tableaux, and T(1; 4) = 2 for the third tableau. Note that, each
tableaux is associated with a sequence of horizontal strips. For example, that
sequence for the rst tableaux is
; = (2; 0) (5; 2) =
With this notation, the combinatorial formula for multiple qt-Catalan num-
bers with an n-part partition is written as follows [14]:
C =
Y
s2 1
(1 q1+a0(s)tn1l0(s))
(1 q1+ 1+l0(s)qa0(s)tn1l0(s))
Y
s2
1
(1 qa (s)+1tl (s))
:
X
T
T (q; t)
Y
s2
tl0(s)+1T(s)(1 q2 T(s)a0(s)tl0(s)) (2.86)
where the sum is over all reversed Young tableau on .
Theorem 5. Let be any partition. Then, the combinatorial recurrence relation
33
for multiple qt-Catalan numbers is given by
C +1
C
=
Yn
i=0
(1 q1+ 1+itn1i)
(1 q2+ 1+itn1i)
(1 + q)n
Y
s2
(1 qa (s)+2tl (s))
(1 qa (s)+1tl (s))
P
T0 T0(q; t)
Q
s2 +1 tl0(s)+1T0(s)(1 q2( +1)T0(s)a0(s)tl0(s))
P
T T (q; t)
Q
s2 tl0(s)+1T(s)(1 q2 T(s)a0(s)tl0(s))
(2.87)
Proof: It su ces to divide C +1 by C as we did in the previous theorem.
Here we denote the tableau for + 1 by T0 to avoid any confusion.
C +1
C
=
Q
s2 1
(1q1+a0(s)tn1l0(s))
(1q
1+ 1+l0(s) qa0(s)tn1l0(s)) Q
s2 1
(1q1+a0(s)tn1l0(s))
(1q
1+ 1+l0(s) qa0(s)tn1l0(s))
Q
s2 +1
1
Q (1qa (s)+1tl (s))
s2
1
(1qa (s)+1tl (s))
P
T0 T0(q; t)
Q
s2 +1 tl0(s)+1T0(s)(1 q2( +1)T0(s)a0(s)tl0(s))
P
T T (q; t)
Q
s2 tl0(s)+1T(s)(1 q2 T(s)a0(s)tl0(s))
(2.88)
Since is a n-part partition, we have `( ) = n. In the above formula I see
three large fractions. I tried to simplify each fraction, and change them to a
smaller product as much as possible.
For the rst fraction, considering s 2 1
we have a0(s) = 0, and it becomes
Q
s2 1
(1q1+a0(s)t21l0(s))
(1q
1+ 1+l0(s) qa0(s)t21l0(s)) Q
s2 1
(1q1+a0(s)t21l0(s))
(1q
1+ 1+l0(s) qa0(s)t21l0(s))
=
Yn
i=0
(1 q1+ 1+itn1i)
(1 q2+ 1+itn1i)
(2.89)
The second large fraction, can be simpli ed by separating the squares s 2
34
and those s 2 + 1= as follows.
Q
s2 +1(1 qa +1(s)tl +1(s)) Q
s2 (1 qa (s)tl (s))
=
Y
s2
(1 qa (s)+1tl (s))
(1 qa (s)tl (s))
Y
s2 +1=
(1 q2)
1 q
(2.90)
Through simple algebra, we get
Q
s2 +1(1 qa +1(s)tl +1(s)) Q
s2 (1 qa (s)tl (s))
= (1 + q)n
Y
s2
(1 qa (s)+1tl (s))
(1 qa (s)tl (s))
(2.91)
Substituting the simpli ed fractions, gives the desired result
This result holds for an arbitrary partition . Now we write the formula in
the explicit form in the two dimensional case:
Theorem 6. Let be a 2-part partition. Then, the combinatorial recurrence
relation for multiple qt-Catalan numbers is:
C +1
C
=
(1 q1+ 1t)(1 q1+ 2)(1 + q)2
(1 q2+ 1t)(1 q2+ 2)
Y 1
j=1
(1 q 1j+2t)
(1 q 1j+1t)
Y 2
j=1
(1 q 2j+2)
(1 q 2j+1)
P 1 2
k=0
Q 2+k+1
j= 2+2
(1q 2+ij t)(1q 1j+1)
(1q 1j t)(1q 2+ij+1) P 1 2
k=0
Q 2+k
j= 2+1
(1q 2+ij t)(1q 1j+1)
(1q 1j t)(1q 2+ij+1)
,!
Q 2+1
j=1 (1 q2 2+1j) (1 q2 1+1j)
Q 2
j=1(1 q2 2+1j) (1 q2 1+1j)
,!
Q 2+k+1
j= 2+2 t1(1 q2 2+1j)
Q 1+1
j= 2+k+2(1 q2 1+1j)
Q 2+k
j= 2+1 t1(1 q2 2+1j)
Q 1
j= 2+k+1(1 q2 1+1j)
(2.92)
Proof: Since is a 2-part partition, we have `( ) = n = 2. I further simplify
the three large fractions that I worked above in the previous theorem for the
35
case n = 2.
In the rst fraction, I simpli ed the numerator by considering n = 2 and
s 2 1. So, the product fraction in the numerator for the two- dimensional case
becomes as follows.
(1 q1t210)
(1 q2+ 1q0t210)
(1 q1t211)
(1 q2+ 1+1q0t211)
=
(1 qt)(1 q)
(1 q2+ 1t)(1 q2+ 2)
(2.93)
Again in the rst fraction, I simpli ed the denominator by considering n = 2
and s 2 1. So, the product fraction in the denominator for the two-dimensional
case becomes
(1 q1t210)
(1 q1+ 1q0t210)
:
(1 q1t211)
(1 q1+ 1+1q0t211)
=
(1 qt)(1 q)
(1 q1+ 1t)(1 q1+ 2)
(2.94)
Then, by dividing the two previous formulas, we get
Q
s2 1
(1q1+a0(s)t21l0(s))
(1q
1+ 1+l0(s) qa0(s)t21l0(s)) Q
s2 1
(1q1+a0(s)t21l0(s))
(1q
1+ 1+l0(s) qa0(s)t21l0(s))
=
(1 q1+ 1t)(1 q1+ 2)
(1 q2+ 1t)(1 q2+ 2)
(2.95)
Now, we simplify the second fraction in the front factors:
Q
s2 +1
1
Q (1qa (s)+1tl (s))
s2
1
(1qa (s)+1tl (s))
=
Q
s2 +1(1 qa +1(s)tl +1(s)) Q
s2 (1 qa (s)tl (s))
(2.96)
36
which reduces to
Q
s2 +1(1 qa +1(s)tl +1(s)) Q
s2 (1 qa (s)tl (s))
=
Y
s2
(1 qa (s)+2tl (s))
(1 qa (s)+1tl (s))
Y
s2 +1=
(1 q2)
1 q
(2.97)
Then, by simplifying the product for the skew partition at the end, we may
write this as
Q
s2 +1
1
Q (1qa (s)+1tl (s))
s2
1
(1qa (s)+1tl (s))
= (1 + q)2
Y
s2
(1 qa (s)+2tl (s))
(1 qa (s)+1tl (s))
(2.98)
or
Q
s2 +1
1
Q (1qa (s)+1tl (s))
s2
1
(1qa (s)+1tl (s))
= (1 + q)2
Y 1
j=1
(1 q 1j+2t)
(1 q 1j+1t)
Y 2
j=1
(1 q 2j+2)
(1 q 2j+1)
(2.99)
To simplify the third fraction in the formula that includes two summations in
thenumerator and denominator, I didn't make it smaller but we observed many
beautiful similar relationships. For the two partitions and + 1, we consider
the Durfee rectangle, and brake the formula in two parts: one part includes the
squares in the Durfee rectangle of , and the second part includes squares that
are not in that Durfee rectangle. So, the third fraction in the formula becomes
37
as follows.
P
T0 T0(q; t)
Q
s2 +1 tl0(s)+1T(s)(1 q2( +1)T(s)a0(s)tl0(s))
P
T T (q; t)
Q
s2 tl0(s)+1T(s)(1 q2 T(s)a0(s)tl0(s))
=
P 1 2
k=0 T0k
(q; t)
Q 2+1
j=1 (1 q2 2+1j) (1 q2 1+1j)
P 1 2
k=0 Tk(q; t)
Q 2
j=1(1 q2 2+1j) (1 q2 1+1j)
,!
Q 2+k+1
j= 2+2 t1(1 q2 2+1j)
Q 1+1
j= 2+k+2(1 q2 1+1j)
Q 2+k
j= 2+1 t1(1 q2 2+1j)
Q 1
j= 2+k+1(1 q2 1+1j)
(2.100)
where the rst row comes from the rst and second row of the Durfee rectan-
gle, and the second row from the extension in the rst row outside the Durfee
rectangle.
Recall that = is called a horizontal strip and denoted by 4 if for each
i 2 [n]
i i; and i i+1:
Then, the T factor for the tableaux T is de ned by
T =
Yn
i=1
(i)= (i1)
where ; = (0) 4 4 (n) = is the standard sequence for the tableaux, and
the individual factors = are given by
= =
Y
s2R = C =
b (s)
b (s)
where R = and C = denotes the rows and columns that intersect the skew
38
partition = in the Young diagram, and for each square s = (i; j) 2 we set
b (s) =
1 qa (s)tl (s)+1
1 qa (s)+1tl (s)
(2.101)
Note that (1)= (0) = 1, since (0) = ;. Therefore,
T = (1)= (0): = (1) = 1
Y
s2R
= (1)C
= (1)
b (1)(s)
b (s)
(2.102)
This becomes,
T =
Y
s2R
= (1)C
= (1)
1q
a
(1) (s)
t
`
(1) (s)+1
1q
a
(1) (s)+1
t
`
(1) (s)
1qa (s)t` (s)+1
1qa (s)+1t` (s)
(2.103)
which may be written as
T =
Y
s2R
= (1)C
= (1)
(1 qa
(1) (s)t`
(1) (s)+1)(1 qa (s)+1t` (s))
(1 qa (s)t` (s)+1)(1 qa
(1) (s)+1t`
(1) (s))
(2.104)
We simplify this factor a bit more, and then substitute the above formula
in third large fraction to make it explicit form.
Note that for n = 2, the sequence always has the form ; 4 (1) 4 which
may be written as (0; 0) 4 (j; 0) 4 ( 1; 2) where j = 2; : : : ; 1 generating a
tableaux T for each j. Therefore, for we will have the sequence of Young
tableaux T0; T1; ; T 1 2 . Note also that this sequence for +1 will have the
same number of tableaux, say T00
; T01
; ; T0
1 2 where each T0k
is obtained by
adding an extra column holding the numbers f2; 1g to the Durfee rectangle for
39
Tk.
Let Tk denote the tableaux associated with the middle partition (1) =
( 2 + k; 0) for each k = 0; : : : ; 1 2. The second factor above is over all
squares s 2 R = (1) C = (1) . For all Tk, k = 0; : : : ; 1 2, we have
R = (1) C = (1) = f(1; 2 + 1); (1; 2 + 2); : : : ; (1; 2 + k)g
It is clear to see that, here ` (s) = ` (1)(s) = 0, and we get
T =
Y
s2R
= (1)C
= (1)
(1 qa
(1) (s)t)(1 qa (s)+1)
(1 qa (s)t)(1 qa
(1) (s)+1)
(2.105)
or for Tk
Tk =
Y2+k
j= 2+1
(1 q 2+ijt)(1 q 1j+1)
(1 q 1jt)(1 q 2+ij+1)
(2.106)
Note that for k = 0, Tk = 1 as an empty product. Furthermore,
T0k
=
2Y+k+1
j= 2+2
(1 q 2+ijt)(1 q 1j+1)
(1 q 1jt)(1 q 2+ij+1)
(2.107)
Finally, substituting the above calculations together with all of the previous
simpli cations, I get the desired result for the combinatorial representation of
the recurrence relation for the multiple qt-Catalan numbers.
40
3. FUTURE RESEARCH
The classical Catalan numbers, q-Catalan numbers, and qt-Catalan num-
bers are very interesting combinatorial objects. Many articles are found in the
literature on the rst two sequences, but there is not enough work carried out
on the higher dimensional qt-Catalan numbers. In the next project, we plan
to work on constructing additional properties that qt-Catalan numbers satisfy
beyond their recurrence relations.
41
4. REFERENCES
[1] George Eyre Andrews, q-Catalan Identities, Mathematics Subject Classi -
cation, 2000.
[2] , Identities in Combinatorics II 53 (1975), 240-245.
[3] , Journal of Combinatorial Theory, The Pensylvania State Univer-
sity 44 (1987), 267-273.
[4] , Their Development and Application in Analysis, Number Theory,
Combinatorics, Physics, and Computer Algebra, CBMS Regional Confer-
ence Series in Mathematics, 66 Amer. Math. Soc, 1986.
[5] , Gaussian Polynomials and nite Rogers - Ramanujan identities.
Theory and applications of special functions (2005), 39-60.
[6] Wilfrid Norman Bailey, Generalized Hypergeometric Series, Hanfer, New
York (1964).
[7] Alexander Berkovich and Ole Warnaar, Positivity preserving transforma-
tions for q-binomial coe cients (2005), 2291-2351.
[8] Leonard Carlitz and John Riordan, Two Element Lattice Permutation
Numbers and q-Generalization 31 (1964), 371-388.
42
[9] W. Edwin Clark and Mourad Ismail, Binomial and q-binomial coe cient
inequalities related to the Hamiltonicity of the Kneser graphs and their q-
analogues, J. Combin. Theory Ser. A 76 1 (1996), 83-89.
[10] Hasan Coskun, Multiple analogues of binomial coe cients and families of
related special numbers, math.Co 310 (2010), 1-10.
[11] Hasan Coskun, A BCn Bailey Lemma and generalizations of Rogers-
Ramanujan Identities, AMS Transactions (2003).
[12] Hasan Coskun, Mutiple Bracket Function, Stirling Number, and Lah Num-
ber Identities, Math. Res. Lett. (1997), 2-15.
[13] Hasan Coskun and Robert Gustafson, The well{poised Macdonald functions
W and Jackson Coe cients ! on BCn, Jack, Hall{Littlewood and Mac-
donald Polynomials, ICMS, AMS Contemporary Mathematics, 417, 2006.
[14] Hasan Coskun, Combinatorial formulas for Certain Sequences of Multiple
Numbers, arxive:1601.00052v1[math.co] (2016), 2-22.
[15] , An Elliptic BCn Bailey Lemma, Multiple Rogers{Ramanujan Iden-
tities and Euler's Pentagonal Number Theorems, AMS Transactions, 360
(2008), 2280-2298.
[16] Darrin D Frey and James A. Sellers, Generalizing Bailey's Generalization
of the Catalan Numbers, Cedarville university, OH (1999), 1-7.
[17] Philip J. Furlinger and Josef Hofbauer, q-Catalan Numbers, scienceDirect
40 (1985), 248-264.
43
[18] Adriano Garsia, A q-analogue of the Lagrange inversion Formula, Vol. 7,
Houston J.Math, 1981.
[19] Adriano Garsia and Mark Haiman, A Remarkable q; t-Catalan Sequence
and q-Lagrange Inversions, Vol. 5, J. Algebraic Combin, 1996.
[20] Adriano Garsia and Jim Haglund, A proof of the q; t-Catalan Positivity
Conjecture, Vol. 3, Discrete Math 256, 2002.
[21] Frank Garvan and Drew Stanton, Sieved partition functions and q-binomial
coe cients, Math. Comp. 55191, 1990.
[22] George Gasper and Mahbubur Rahman, Basic hypergeometric series, Ency-
clopedia of mathematics and its applications, Cambridge University Press,
Cambridge 35 (1990).
[23] Henry Williams Gould, The bracket function, q-binomial coe cients and
some new Stirling number formulas, Fibonacci Quart (1967), 401-422.
[24] Ralph P Grimaldi, Fibonacci and Catalan Numbers, John Wiley and sons,
2011.
[25] Eugene Grosky and Mikhail Mazin, Compacti ed Jacobians and q; t-
Catalan Numbers, Combinatorial Theory Series A120 (2013), 49-63.
[26] James Haglund, The q; t-Catalan Numbers and the Space of Diagonal,
Vol. 32, Contemporary Mathematics, 2004.
[27] James Haglund, The q; t-Catalan Numbers and the Space of Diagonal Har-
monics, Mathematics Subject Classi cation, 1991.
44
[28] Jim Haglund, Statistics for the q; t-Catalan Numbers, Vol. 2, Adv. Math
175, 2003.
[29] Mark Haiman, Conjectures on the Quotient Ring by Diagonal Invarients,
Vol. 3, J. Algebraic Combin, 1994.
[30] , q; t-Catalan Numbers and the Hilbert Scheme, Discretemath, 1998.
[31] Jyoichi Kaneko, q-selberg integrals and Macdonald Polynomials, Ann. Sci.
Ecole Norm. Sup., 1996.
[32] Kyungyon Lee and Li Li and Nicholas Loehr, Limits of Modi ed Higher
q; t-Catalan Numbers, http://arxiv.org/ 2 (2013), 3-7.
[33] Rachel Landers, Combinatorial Interpretation of the Multiple Binomial Co-
e cients, Proquest (2015), 12-30.
[34] Michel Lassalle, Coe cients binomiaux generalises et polynomes de Mac-
donald, J. Funct. Anal. 158 (1998), 289-324.
[35] Nick Loehr and Greg Warrington, Square q; t-Lattice Paths, Vol. 2,
Trans.Amer.Math, 2007.
[36] Nick Loehr and M. Can, A Proof of the q; t-Square Conjecture, Vol. 7, J.
Combin, 2006.
[37] Ian Grant Macdonald, Symmetric Functions and Hall Polynomials, Oxford
University Press (1995).
[38] Andrei Okounkov, Binomial Formula for Macdonald Polynomials and Ap-
plications, Math. Res. Lett., 1997.
45
[39] Igor Pak, History of Catalan Numbers, UCLA University,
http://www.math.ucla.edu (2014).
[40] Ron E. Rains, BCn Symmetric Abelian Functions, Duke Math 135 (2006),
99-180.
[41] Neil Sloane, Combinatorial Interpretations of Catalan Numbers, oeis.org
(2014).
[42] Mike Spivey, The Catalan Numbers From Their Generating Function, mike-
spivey.wordpress.com (2013), 1-3.
[43] Richard P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Uni-
versity Press, 1999.
[44] Richard Stanley and Weistein and W. Eric, Catalan Numbers, Wofram
(2014).
[45] Herbert S Wilf, Generating Funtionology, Academic Press, 1994.
46
5. VITA
Mersedeh Biglari Se di
2600 S. NEAL ST., COMMERCE, TX 75429
EMAIL: MSEFIDI@LEOMAIL.TAMUC.EDU
Mersedeh Biglari Se di received her B.S in Mathematics for Secondary Ed-
ucation from Ferdowsi University in Iran in 1990. She taught mathematics in
Iran's Nemooneh (school for gifted students) and other high schools for seven
years.
After she moved to the United States, Mersedeh completed more than thirty
hours of classes at Brookhaven College. She also, completed her teaching certi-
cation program to pursue her dream of continuing to teach. She restarted her
career by working as a substitute teacher in Carrollton Farmers Branch school
district, then moved on to working in Brookhaven College as an adjunct faculty
member. She continued to study mathematics, and received her Master's from
Texas A&M-Commerce University in May 2016.
Mersedeh is currently teaching at Brookhaven community college in Dallas,
Texas where she enjoys volunteering in her three children's schools and mentor-
ing young students in Brookhaven College.