A NEW COMBINATORIAL INTERPRETATION OF THE
MULTIPLE BINOMIAL COEFFICIENTS
A Thesis
by
RACHEL LANDERS
Submitted to the Office of Graduate Studies
of Texas A&M University-Commerce
in partial fulfillment of the requirements
for the degree of
MASTER OF SCIENCE
May 2015
A NEW COMBINATORIAL INTERPRETATION OF THE
MULTIPLE BINOMIAL COEFFICIENTS
A Thesis
by
RACHEL LANDERS
Approved by:
Advisor: Hasan Coskun
Committee: Padmapani Seneviratne
Stuart Anderson
Rebecca Dibbs
Yelin Ou
Head of Department: Tingxiu Wang
Dean of the College: Brent Donham
Dean of Graduate Studies: Arlene Horne
!iii
Copyright © 2015
Rachel Landers
!iv
ABSTRACT
A NEW COMBINATORIAL INTERPRETATION OF THE
MULTIPLE BINOMIAL COEFFICIENTS
Rachel Landers, MS
Texas A&M University-Commerce, 2015
Advisor: Hasan Coskun, PhD
Multiple qt-binomial coefficients, the n-dimensional analog of the classical binomial
coefficients, is an active research topic in the field of combinatorics. This project investigates the
combinatorial interpretation and properties of the qt-binomial coefficients in the two dimensional
case. The result will be useful in not only the field of combinatorics but also number theory,
statistics, computer science and other fields where the sequences of binomial coefficients or q-binomial
coefficients are used.
!v
ACKNOWLEDGEMENTS
I’d like to thank Josh for the late-night ice creams runs; Trini for being there when my
nerves are too much to handle; the Mathematics Department of Texas A&M University-
Commerce for always being so supportive of their students; and finally, Dr. Coskun for his
contributions and advice.
!vi
TABLE OF CONTENTS
LIST OF FIGURES ..................................................................................................................... vii
CHAPTER
1. INTRODUCTION ...................................................................................................... 1
2. BACKGROUND ........................................................................................................ 4
Classic Binomial Coefficients ............................................................................. 4
q-Binomial Coefficients ...................................................................................... 8
qt-Binomial Coefficients ...............................................................................… 15
Common Properties ........................................................................................... 18
3. THE PRINCIPAL THEOREM ................................................................................. 25
4. A NEW COMBINATORIAL INTERPRETATION IN TWO DIMENSIONS ......... 29
External Factors ................................................................................................. 31
Internal Factors .................................................................................................. 36
A Complete Example .....................................................................................… 42
5. FUTURE RESEARCH ............................................................................................. 51
REFERENCES .......................................................................................................................... 52
VITA ........................................................................................................................................ 56
!vii
LIST OF FIGURES
FIGURE
1. The Pascal Triangle ........................................................................................................... 6
2. The lattice paths of ! ................................................................................................. 12
3. The Ferrer diagram of λ=(5, 2, 1) .................................................................................... 12
4. All lattice paths for λ=(10, 8) and μ=(5,2) ...................................................................... 30
5. The external non-q-Pochammer factors and their weight distributions for λ=(10, 8)
and μ=(5,2) ......................................................................................................................31
6. The external q-Pochammer factors and their weight distributions for λ=(10, 8) and
μ=(5,2) ............................................................................................................................. 35
7. t−ρ(μ)q−ρ(μ)σ(λ) for λ=(10, 8) and μ=(5,2) ...................................................................... 38
8. (t)ρ(μ) for λ=(10, 8) and μ=(5, 2) ..................................................................................... 38
9. (qδ(μ)+1)ρ(μ) for λ=(10, 8) and μ=(5, 2) .......................................................................... 39
10. (qμ2−λ2)ρ(μ) for λ=(10, 8) and μ=(5, 2) ............................................................................ 39
11. (qρ(μ)+1)δ(μ) for λ=(10, 8) and μ=(5, 2) .......................................................................... 41
12. (t)δ(μ) for λ=(10, 8) and μ=(5, 2) ..................................................................................... 41
5
2
⎛
⎝ ⎜
⎞
⎠ ⎟
q
!viii
13. (q−δ(λ))δ(μ) for λ=(10, 8) and μ=(5, 2) ........................................................................... 42
14. The external non-q-Pochhammer factors for λ=(4, 2) and μ=(3, 1) ................................ 43
15. The external q-Pochhammer factors for λ=(4, 2) and μ=(3, 1) ....................................... 44
16. The first lattice path for λ=(4, 2) and μ=(3, 1) ................................................................ 47
17. The second lattice path for λ=(4, 2) and μ=(3, 1) ............................................................ 49
18. The third lattice path for λ=(4, 2) and μ=(3, 1) ............................................................... 50
1
Chapter 1
INTRODUCTION
The binomial coecients are a special sequence of numbers with many applied uses in
various fields of math [40]. The generalizations of the binomial coecients in the q- and qt-analogs
has become a hot topic in the field of combinatorics. Progress has been made within
recent years in the study of the qt-binomial coecients (which will be further discussed in
Section 2), but there still remains much to be discovered.
Of these gaps in knowledge, the near absence of combinatorial interpretations of the
qt-binomial coecients is perhaps the most conspicuous. Combinatorial interpretations of
the classic binomial coecients are plentiful, and the q-binomial coecients already have
multiple interpretations (most of which parallel those of the classic case). However, prior to
this study only one combinatorial interpretation of the qt-binomial coecients existed–that
of A. Okounkov, ✓
!
μ
◆
=
P⇤ μ(q!; q, t)
P⇤ μ(qμ; q, t)
(1)
which, unlike the combinatorial interpretation produced in this study, requires investigation
of the properties of every square in every reverse Young tableau of μ. Because even for small
partitions the number of possible reverse Young tableau can quickly reach tens of thousands,
Okounkov’s interpretation can be very lengthy and extensive. Even by computer, the time for
calculation using Okounkov’s method can range from seconds to minutes. The combinatorial
interpretation introduced in this paper–presented as a Corollary in Section 4–drastically cuts
the amount of calculation and time needed to find the qt-binomial coecients.
H. Coskun defines the most general form of the qt-binomial coecients so that where
z 2 C is an n-tuple of a complex number or a partition of an integer, q, t 2 C, and μ a
partition of at most n parts,
✓
z
μ
◆
q,t
=
q|μ|t2n(μ)+(1−n)|μ|
(qtn−1)μ
Y
1i<jn
⇢
(qtj−i)μi−μj
(qtj−i−1)μi−μj
%
!μ(qzt"(n); q, t). (2)
2
Although not combinatorial, this definition, in conjunction with Okounkov’s interpreta-tion,
was studied heavily to algebraically derive a new definition of the qt-binomial coecients
in the second dimension which is presented as a Lemma in Section 3. This new definition is
a much simpler theoretical approach to the qt-binomial coecients, because it is in the form
of a single sum. From this new definition the combinatorial interpretation presented in this
paper was then derived.
The results of this study are in terms of lattice paths, but a survey of all combinato-rial
properties of the classic, q-, and qt-binomial coecients is provided in Section 2. The
properties shared amongst the three–such as the recursive property, symmetric property,
and special subsets property–are also discussed and proven combinatorially. It will become
readily apparent in this section that the currently existing knowledge of the qt-binomial co-e
cients is sparse in comparison to that of the classic and q-binomial coecients. Further,
the definition and combinatorial interpretation which currently do exist are theoretically
and computationally complex–requiring a solid background in mathematics and the use of
a computer. In fact, for this paper Wolfram Mathematica was heavily used to compute the
qt-binomial coecients and conduct experiments investigating their properties.
In Section 3, the qt-binomial coecients are simplified to the given Lemma which, as
proven in the provided proof in the same section, remarkably reduces the complex formula
provided by H. Coskun to a single sum in the second dimension. Further, this lemma is then
shown to give way to the following corollary:
✓
z
μ
◆
=
q!(",μ)tμ2(1)|μ|(q"1t1)μ2(q"2)μ2
(q)μ2(q#(μ)+1t)μ2(q)2
#(μ)(t)#(μ)
·
X
L
[t⇢(μ)q⇢(μ)#(")(t)⇢(μ)(q%(μ)+1)⇢(μ)(qμ2"2)⇢(μ)
· (q⇢(μ)+1)%(μ)(t)%(μ)(q%("))%(μ)] (3)
where the Durfee rectangle of μ is the largest rectangle which fits inside the Young tableau
3
of μ, the extension of μ is the set of all squares which extend outside the Durfee rectangle
of μ, and L is defined as all lattice paths which wrap around either the Durfee rectangle or
the squares in the extension of μ so that !(μ) is the number of squares in the extension of μ,
⇢(μ) is the number of squares above the lattice path l, #(μ) is the number of squares below
the lattice path l, μ2 is the number of squares in the second row of the Young diagram of μ,
$2 is the number of squares in the second row of $, |μ| is the total number of squares in μ,
and %($, μ) is discussed in Section 4.1.1.
This corollary is discussed in closer detail in Section 4. Each factor in the corollary has
its own specific combinatorial interpretation; further, each factor belongs to one of either
four groups based on the combinatorial properties of the factor. These four groups are:
the external non-q-Pochhammer factors, the external q-Pochhammer factors, the internal ↵
factors, and the internal ' factors. Thus, each separate factor’s combinatorial interpretation
is detailed as well as illustrated in the provided figures in Section 3.
Together, the combinatorial interpretations of each separate factor produces a new com-binatorial
interpretation of the qt-binomial coefficients–a combinatorial interpretation which
is theoretically more elementary than other advanced methods used for calculating the qt-binomial
coefficients, is supremely e↵ective in simplifying the calculation of the qt-binomial
coefficients, and is expected to enable the future application of the qt-binomial coefficients
in other areas of mathematics and applied fields. The expectations of this combinatorial in-terpretation
of the qt-binomial coefficients are further discussed in Section 5 which considers
topics for future research.
4
Chapter 2
BACKGROUND
Combinatorics is the study of how to count a discrete set of objects and patterns. It
is a field which has experienced “explosive growth ... in the last forty years” [7] due, in
large part, to “the increasing importance of computers, the needs of computer science and
demands from applications where discrete models play more and more important roles” [22].
Special sequences of numbers, such as the Fibonacci numbers, Bell numbers, Lah numbers,
Stirling numbers, Catalan numbers, and–the focus of this study–the binomial coecients,
are commonly studied in combinatorics.
Although special sequences of numbers have been studied for centuries (in fact, the ear-liest
discussion of the binomial coecients found was written in the tenth century [11]),
the generalization of such sequences to the q- and qt- parameters has only recently in the
history of mathematics begun to be studied. For this reason, there is relatively little in-formation
about the qt-parameters. With the use of the Macdonald polynomials [29, 32],
a definition of the qt-binomial coecients has algebraically been derived, and properties of
the qt-binomial coecients have been similarly uncovered; however, combinatorial interpre-tations
are severely lacking.
Classic Binomial Coecients
The binomial coecients are produced by the following formula:
Definition 1. ✓
n
k
◆
=
n!
k!(n − k)!
(4)
where n! =
nQ1
i=0
n − i and k n.
The Binomial Theorem [5], together with Pascal’s Triangle, are perhaps the most com-monly
recognized application of the binomial coecients, because they are often both in-
5
troduced in early levels of algebra when students begin studying the expansion of binomials
(hence the name ”binomial coecients”).
Theorem 1 (Classic Binomial Theorem).
(a + b)n =
Xn
k=0
✓
n
k
◆
ankbk. (5)
This is significant in that a binomial need not be completely multiplied manually. A
mathematician armed with the knowledge of the Binomial Theorem need only know the
binomial coecients formula and/or the Pascal’s Triangle to quickly receive the expansion
she seeks [36].
Proof. A combinatorial proof is best demonstrated by an example. Note if say, n = 4, then
the following is received:
(a + b)4 = aaaa + aaab + aaba + · · · + bbbb = a4 + 4a3b + 6a2b2 + 4ab3 + b4 (6)
Thus, it can be observed that the coecient, C, of any term Casbns, where 0 s n,
in the expansion of (a + b)n is the number of rearrangements of s number of a’s and n − s
number of b’s. These coecients can be found by using the binomial coecient formula
$n
s
%
= n!
s!(ns)!, because the binomial coecients count the number of ways in which subsets
of k length can be formed using elements from a set of n elements where k n. This
property is a combinatorial interpretation and is explained below.
Another perspective into the proof of the Binomial Theorem is to think of the expansion
of (x + y)n as a series of decisions such that each decision is the choice between x and y for
the next factor. For instance, (x + y)n = (x + y)(x + y)(x + y) . . . (x + y) can be expanded
by choosing one of either x or y from the first set of parentheses, then again choosing one of
either x or y from the second set of parentheses, and continuing this process for each set of
parentheses until the nth set is finally reached. By multiplying each of the n choices made,
one term in the expansion is made. Continue this process for each of the 2n possible ways
6
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1
Figure 1: The Pascal Triangle
in which the terms can be formed. The result is a sum of terms consisting of k number of
x0s and n k number of y0s. Thus, the coecient, C, of the term, Cxkyn−k in the binomial
expansion of (x + y)n is the number of ways in which a set of k number of x’s and n k
number of y’s can be formed [30].
In addition to its use as a shortcut to calculate
!n
k
"
, the Pascal Triangle, as seen in Figure
(1), is a wonderful demonstration of the properties of the binomial coecients which will be
discussed later in this paper. To use the Pascal Triangle to find
!n
k
"
, starting with n = 0,
count down n number of rows, then, starting with k = 0, count over k number of columns
so that the binomial coecient,
!n
k
"
, is in the nth row and kth column of Pascal’s Triangle.
Combinatorial Interpretations In addition to the Binomial Theorem, the classic bino-mial
coecients have combinatorial interpretations which are each applicable in many fields
of math most readily apparent of which are the subset and lattice path interpretations.
The subset interpretation [37] of the binomial coecients is fairly straightforward and
the most basic.
7
Lemma 1. If given a set of n objects the number
!n
k
"
is the number of ways k objects can
be taken out of the given set such that order does not matter.
Proof. Suppose a set has n elements from which to choose k elements such that there are
no repeats. There are n ways to choose the first element. But there are only n 1 ways to
choose the second, because the first element can no longer be chosen since repeats are not
allowed. Likewise, there are n 2 ways to choose the third element, because the first two
elements are now eliminated from the possible choices of elements. This pattern continues
until the kth element is chosen, which can be done in n k + 1 ways. Thus, the number
of ways in which unordered k-subsets of a set with n elements is n!/(n k)!. However, the
binomial coefficients count the number of ordered subsets, i.e., all sets containing the same
elements are considered equal and are not counted more than once. To accommodate this,
choose any k elements from the set of n elements. The total number of subsets consisting
of these k specific elements is k!. In other words, a subset consisting of k elements can be
ordered in k! di↵erent ways. Thus, the number of k-subsets of an n-set is n!
k!(nk)! [3].
Lemma 2. If given a set of n number of non-collinear points,
!n
k
"
number of shapes with k
number of vertices can be formed by connecting any k number of points [9].
Proof. The proof is simply a geometrical representation of the subset interpretation. For
example,
!n
2
"
lines can be formed, because lines have two endpoints;
!n
3
"
triangles can be
formed, because triangles have three vertices.
The following interpretation is the most relevant to the results of this study [6, 37].
Lemma 3. The classic binomial coecients enumerate the number of lattice paths on a graph
such that each path begins at the origin and moves either north or east at each intersection
on the plane until the lattice path reaches the point (n k, k).
Proof. Following the trajectory of a path from the origin to the point (n k, k), observe
that no matter what path the lattice is taking, at every intersection it encounters one of two
possibilities which can occur: the path travels north or the path travels east. Furthermore,
8
because the path ends at (n k, k) and cannot move neither south nor west, the path
travels north exactly k times. Further, because the path travels from the origin to the point
(n k, k), the path, in total, makes (n k) + k = n moves. Therefore, the number of
acceptable routes from the origin to the point (n k, k) is the number of ways of choosing
which k of the n moves must be the ones which travel north, i.e.,
!n
k
"
ways [10].
q-Binomial Coecients
The q-series first entered the attention of mathematicians with the introduction of certain
famous theorems by Euler and Gauss [14,18,20] while Heine can be thanked for the systematic
development of the theory of the q-series [14, 24].
The q-binomial coecients [38] are a q-analog of the classic binomial coecients. In
other words, the q-binomial coecients add the parameter q such that when the limit of q
approaches 1, the classic binomial coecients are returned.
The q-analog of an integer, called a q-integer, q-number or q-bracket, is expressed as:
Definition 2 (q-Integer).
[n]q = [n] =
1 qk
1 q
=
Xk1
i=0
qi = 1+q + q2 + · · · + qk1 (7)
which makes the q-falling factorial defined as such:
Definition 3 (q-Falling Factorial).
[n]q! = (1+q)(1 + q + q2) . . . (1 + q + · · · + qn1) = (q; q)n(1 q)n (8)
The above definition uses the following definition.
Definition 4 (q-Pochhammer).
(q; q)n =
Yn
j=1
(1 qj) (9)
9
The above definition is the q-Pochhammer. Thus, the q-number is used to define the
q-binomial coecients like so:
Definition 5 (q-Binomial Coecients).
✓
n
k
◆
q
=
[n]q!
[k]q![n k]q!
=
kY1
i=0
1 qni
1 qi+1 (10)
Similarly, using Definition (4), the q-binomial coecients can also be written as [1]:
Definition 6.
✓
n
k
◆
q
=
(1 q) . . . (1 qn)
(1 q) . . . (1 qk)(1 q) . . . (1 qn k)
=
(q; q)n
(q; q)k(q; q)nk
(11)
Similarly to the classic binomial coecients, the q-binomial coecients are associated
with a q-binomial theorem which states [19]:
Theorem 2 (q-Binomial Theorem).
(x + y)n =
Xn
k=0
✓
n
k
◆
q
xnkyk (12)
Alternatively, the q-binomial theorem can also be defined as:
Theorem 3 (q-Binomial Theorem).
Yj1
i=0
(1 + xqi) =
Xj
k=0
xkq(k
2)
✓
j
k
◆
(13)
A tiling proof is given by Azose [2], but the proof by finite field as given by Stanley [37]
is discussed here.
Proof. Let q be a prime power. The expansion of the product on the left-hand side of
Definition (3) allows for two decisions for each factor (similarly to the proof of the classic
Binomial Theorem): the 1 term or the xqi term. If the 1 term is chosen then choose a row
10
vector !i of length j whose first nonzero coordinate is 1 which occurs in the (j−i)th position
which creates qi choices for !i Once all choices are made for i, let V be the span in Fj
q of
the chose !i’s. If k of the !i’s is chosen, then dimV = k. Now let M be the k ⇥ j matrix
whose rows are the !i’s in decreasing order of the index i. Next change every entry above
the first 1 in any row to 0. This produces a matrix in row-reduced echelon form. Thus every
row-reduced echelon matrix with k rows is produced exactly q(k
2) times, because there are
!k
2
"
entries of M which changed to 0.
Combinatorial Interpretations A plethora of combinatorial interpretations are available–
many of which parallel those of the classic binomial coecients. The following is a collection
of the most commonly found interpretations as well as their combinatorial proof.
While the subset interpretation of the classic binomial coecients is relatively straight-forward,
the combinatorial interpretation of the q-binomial coecients [37] first requires the
discussion of a partition [33]. A partition " of an integer n is a vector of non-increasing
positive integers such that their sum is n [35]. In other words, " = ("1,"2, . . . ,"k) where
"1 # "2 # · · · # "k and "1 + "2 + · · · + "k = n. Note that k is the length of the partition
and n is called the weight.
Lemma 4 (Partition Interpretation). If p(j, k, n) represents the number of partitions of n
with exactly k parts such that no part is greater than j then
✓
j + k
j
◆
q
=
X
n0
p(j, k, n)qn (14)
where j and k are fixed integers.
Proof. The proof lies in the demonstration of a bijection between the Young diagram of a
partition " of n which fits within an i ⇥ k rectangle and k-subsets of the set, {1, 2, . . . , i +
k −1, i+k} whose sum of elements is n+
!k+1
2
"
. Let F be the Young diagram of a partition
" = {"1,"2, . . . ,"k} (where "j may be 0 for any 1 j)of n with at most k rows with lengths
11
no longer than i. Then the set {1 + k, 2 + k 1, . . . ,k + 1} is a k-element subset of
{1, 2, . . . , i + k 1, i + k} and the sum of its elements is n +
!k+1
2
"
[8]. Because this map is
an obvious bijection, it is proved by Formula (5) which immediately follows below.
A demonstration of the Young diagrams as described is provided in Figure (2) and a
demonstration of the partition interpretation is as follows:
Example 1 (Partition Example). For j = 2 and k = 3 we have
!5
2
"
= 1+q + 2q2 + 2q3 +
2q4 + q5 + q6 which enumerates the following partitions of length k = 3 with no part greater
than j = 2.
Partitions of n = 0 : {0, 0, 0} (15)
Partitions of n = 1 : {1, 0, 0} (16)
Partitions of n = 2 : {2, 0, 0}, {1, 1, 0} (17)
Partitions of n = 3 : {2, 1, 0}, {1, 1, 1} (18)
Partitions of n = 4 : {2, 2, 0}, {2, 1, 1} (19)
Partitions of n = 5 : {2, 2, 1} (20)
Partitions of n = 6 : {2, 2, 2} (21)
Lemma 5 (Ferrer’s Diagram).
✓
n
k
◆
q
=
k(Xnk)
l=0
alql. (22)
Then the coecient al is the number of partitions of l whose Ferrer’s diagrams fit in a box
of size k by n k [28].
Proof. The proof is the same as Lemma 4–simply change the squares to dots.
The lattice path interpretation [6] of the q-binomial coecients parallels that of the classic
case; however, it assigns to each lattice paths weights such that the weight is the number
of squares directly above the lattice path which are not above or to the right of the point
(n k, k). More precisely,
12
Figure 2: The lattice paths of
!5
2
"
q.
Figure 3: The Ferrer Diagram of = (5, 2, 1).
Lemma 6 (Lattice Path Interpretation). the coecient of qj in
!n
k
"
q is the number of lattice
paths which, beginning at the origin, move only north or east until they reach the point
(n k, k) whose weight is j.
Proof. This lemma is easily proved by noticing that there is a direct bijection between the
Young tableau which fit inside the rectangle as described in Lemma (4) and, in fact, can
easily be seen in Figure (2).
13
Lemma 7 (Vector Space Interpretation). Another combinatorial interpretation of the q-binomial
coecients is that it enumerates the k-dimensional subspaces of V where V is an
n-dimensional vector space over the finite field Fq [38].
Proof. A proof is provided by Stanley [37] on page 64.
Lemma 8 (Row-Reduced Echelon Interpretation). Defining a row-reduced echelon as a k⇥n
matrix such that: 1) the left-most non-zero entry of each row is 1 (called the ”leading 1”), 2)
all the other entries in the column of a leading 1 are zero, 3) the leading 1 in any row occurs
to the right of the leading 1 in the row above it [34]. Given a matrix in reduced row echelon
form, delete all the entries in each row to the left of the leading 1. Then remove the columns
containing the leading 1’s. Lastly, replace each remaining entry with a ’*’. The q-binomial
coecients enumerates this pattern of matrices so that the coecient of qj in
!n
k
"
counts the
number of matrices with j number of asterisks [34].
Proof. A proof is provided by Stanley on page 66 [37].
A demonstration of the row-reduced echelon interpretation is provided here in the exam-ple
below.
Example 2. The following corresponds to
!6
2
"
q = 1+q+2q2+2q3+3q4+2q5+2q6+q7+q8
which says that 1 matrix has 0 asterisks, 1 matrix has 1 asterisk, 2 matrices have 2 asterisks,
2 matrices have 3 asterisks, 2 matrices have 5 asterisks, 2 matrices have 6 asterisks, 1 matrix
has 7 asterisks, 1 matrix has 8 asterisks.
0
B@
0 0 0 0 1 0
0 0 0 0 0 1
1
CA
,
0
B@0 0 0 1 ⇤ 0
0 0 0 0 0 1
1
CA
,
0
B@
0 0 0 1 0 ⇤
0 0 0 0 1 ⇤
1
CA
0
B@
0 0 1 ⇤ ⇤ 0
0 0 0 0 0 1
1
CA
,
0
B@
0 0 1 ⇤ 0 ⇤
0 0 0 0 1 ⇤
1
CA
,
0
B@
0 0 1 0 ⇤ ⇤
0 0 0 1 ⇤ ⇤
1
CA
0
B@
0 1 ⇤ ⇤ ⇤ 0
0 0 0 0 0 1
1
CA
,
0
B@
0 1 ⇤ ⇤ 0 ⇤
0 0 0 0 1 ⇤
1
CA
,
0
B@
0 1 ⇤ 0 ⇤ ⇤
0 0 0 1 ⇤ ⇤
1
CA
14
0
B@
0 1 0 ⇤ ⇤ ⇤
0 0 1 ⇤ ⇤ ⇤
1
CA
,
0
B@
1 ⇤ ⇤ ⇤ ⇤ 0
0 0 0 0 0 1
1
CA
,
0
B@
1 ⇤ ⇤ ⇤ 0 ⇤
0 0 0 0 1 ⇤
1
CA
0
B@
1 ⇤ ⇤ 0 ⇤ ⇤
0 0 0 1 ⇤ ⇤
1
CA
,
0
B@
1 ⇤ 0 ⇤ ⇤ ⇤
0 0 1 ⇤ ⇤ ⇤
1
CA
,
0
B@
1 0 ⇤ ⇤ ⇤ ⇤
0 1 ⇤ ⇤ ⇤ ⇤
1
CA
Lemma 9 (Inversions Interpretation). Define a pair (wi, wj) as an inversion of a word
w = w1w2 . . . wn, if i < j and wi > wj . The number of entries to the left of i satisfying
j > i. Let Gn be the set of all permutations of a set S. Further, let inv(w) denote the sum
of all inversions of wn [37]. Then
✓
n
k
◆
q
=
X
w2Gn
qinv(w) (23)
Proof. A combinatorial proof is provided by Stanley on page 37 [37].
A demonstration of the inversion interpretation is provided below.
Example 3. {3,2,1} has 0 descents. {3,1,2} has 1 descent. {2,3,1} has 1 descent. {2,1,3}
has 2 descents. {1,3,2} has 2 descents. {1,2,3} has 3 descents.
This corresponds to
*4
2
+
= 1+2q + 2q2 + q3
The tiling interpretation is of interest as well [2]. Let a board of length n using k green
squares and n − k red squares assign to each square a weight qw. Let Tn,k be the set of all
tilings of a board described as so using exactly k green squares and n − k red squares. Let
qwT be the weight of tiling T 2 Tn,k where wT is calculated by assigning to each red square
a weight of 1 and each green square the weight s so that s is equal to the number of red
squares to the left of that green square in the tiling and then multiplying the weight qs of
all the green squares. The q-binomial coecient
*n
k
+
q is created by summing the weights of
all these tilings, i.e.,
15
Lemma 10 (Tiling Interpretation).
✓
n
k
◆
q
=
X
Tn,k
qwT (24)
Proof. There exists a bijection between the tiling interpretation and the partition interpre-tation
[2].
qt-Binomial Coecients
Finally, the discussion arrives at the qt-binomial coecients which is the serious around
which the results of this study revolve. Not much is known about these series of numbers
and there exists little literature compared to that of the classic and q-binomial coecients.
Information which is known and is relevant to this study are discussed here.
The qt-binomial coecients add yet another parameter to the binomial coecients–the
t parameter. By allowing the t parameter to approach 1, the qt-binomial coecients reduce
to the q-binomial coecients which in turn reduce to the classic binomial coecients when
q approaches 1.
The currently known formulas for the qt-binomial coecients, which were derived using
the Macdonald [29] polynomials, both rely heavily on the Young diagrams and Young tableau
which are defined below.
A Young diagram is a finite collection of left-justified boxes so that the nth entry in a
partition = (1,2, . . . ,k) is the length of the nth row in the diagram. A reverse Young
tableau is a Young diagram with positive integers from the set 1, 2, . . . ,k in each block such
that the integers weakly decrease in the rows but strictly decrease in the columns [41]. When
the squares are replaced with dots this is called a Ferrer’s diagram [39]. See Figure (3) for
a demonstration of the Ferrer’s diagram.
The definition constructed by H. Coskun [15,16] is the most general form of the binomial
coecients in the sense that it is takes complex ntuples for its arguments. The following
16
partition statistics are used in this definition [15, 16]: (a)n = (a; q)n =
Qn−1
i=0 (1−aqi), (a)! =
(a; q, t)! =
Qn
i=1(at1−i; q)!i , |μ| =
Pn
i=1 μi, n(μ) =
Pn
i=1(i − 1)μi, and n(μ0) =
Pn
i=1
#μi
2
$
.
Thus, the qt-binomial coecients as given by H. Coskun [15,16] is defined as the following.
Definition 7. Where z 2 C is an n-tuple of a complex number or a partition of an
integer,q, t 2 C and μ a partition of at most n parts such that
✓
z
μ
◆
q,t
=
q|μ|t2n(μ)+(1−n)|μ|
(qtn−1)μ
Y
1i<jn
⇢
(qtj−i)μi−μj
(qtj−i−1)μi−μj
)
!μ(qzt"(n); q, t) (25)
where
!μ(x; q, t) =
(−q/x)|μ|qn(μ0)(x−1)!
(−q/x)|!|qn(!0)(x−1)μ
·
Y
1i<jn
(
(qμi−μj−1tj−i)μj−1−!j (q!i−μj−1+1tj−i−1)μj−1−!j
(qμi−μj−1+1tj−i−1)μj−1−!j (q!i−μj−1tj−i)μj−1−!j
)
(26)
The ! functions are the limiting cases of the rational Macdonald functions, and are the
most general symmetric rational functions of this kind [15, 16]. These have many interesting
properties such as their symmetry and vanishing property.
0.0.1 Example Using The Definition as Provided By H. Coskun
Using code constructed in Wolfram Mathematica, " = (4, 2) and μ = (3, 1) are used as
the input for Definition (25), so that the following result is found:
✓
"
μ
◆
=
(1 + q)(−1 + q4t)(−1 − q − q2t + qt2 + q2t2 + q3t2)
t(−1 + qt)(−1 + q3t)
(27)
Note that this result takes approximately 0.02 seconds to compute. This result will be
referred back to in the next section and in section (??) in order to compare the eciency of
Definition (25), Definition (8), and Corollary (1). The same " and μ will be used.
17
An Existing Combinatorial Interpretation Okounkov’s combinatorial interpretation
[31] is defined in terms of properties of the Young diagram associated with the partitions
! = (!1,!2, . . . ,!k) and μ = (μ1, μ2, . . . μk). The formula is defined as:
Definition 8. For partitions ! = (!1,!2, . . . ,!k) and μ = (μ1, μ2, . . . μk)
✓
!
μ
◆
=
P⇤ μ(q; q, t)
P⇤ μ(qμ; q, t)
(28)
where
P⇤ μ(x; q, t) =
X
T
T (q, t)
Y
s2μ
t1−T(s)(xT(s) qa0(s)tl0(s)) (29)
where the sum is over all reverse tableau constructed using partition μ with entries in N
and T(s) denotes the entry in the square s = (i, j) in the reverse tableau constructed using
partition μ such that [27]
/μ =
Y
s2R/μ−C/μ
(30)
where
b(s) = b(s; q, t) = f(x) =
8>< >:
1−qa(s)tl(s)+1
1−qa(s)+1tl(s)
1
(31)
and a(s) = !i j, a0(s) = j 1, l(s) = !j i, and l0(s) = i 1. Note that the summation
runs over all possible reverse Young tableau; however, the set of all possible reverse Young
tableau can be very large. In addition, the Okounkov interpretation must use statistics for
each square in the reverse Young tableau. For this reason, it quickly becomes impossible
to calculate the qtbinomial coecients using Okounkov’s formula without the use of a
computer and even then can be lengthy to compute for larger partitions.
As will be seen, the combinatorial interpretation presented in this paper relies on less
computation based on characteristics of the reverse Young tableau which results in a more
ecient method of computing the qt-binomial coecients.
18
0.0.2 Example Using The Interpretation as Provided By A. Okounkov
An example using Definition (25) and partitions = (4, 2) and μ = (3, 1) is discussed
here so that eciency can be compared between Definitions (25), (8), and (1).
Despite the brevity of the Young tableau of = (3, 1), the number of reverse Young
tableau which fit into this Young tableau is 15. Using code the author defines in Wolfram
Mathematica, the following result is found:
✓
μ
◆
=
(1 + q)(1 + q4t)(1 q q2t + qt2 + q2t2 + q3t2)
t(1 + qt)(1 + q3t)
(32)
This result is the same as found in Formula (27);yet the time it took for Wolfram Math-ematica
to compute the answer averages approximately 40.0 seconds in comparison to the
approximately 0.02 seconds it takes to compute the same and μ using Definition (25).
Common Properties
Because the q- and qt-binomial coecients are a generalization of the classic binomial
coecients, all three sequences share most of the known properties.
The sum of each row in Pascal’s Triangle is a power of 2. In other words,
Lemma 11.
Xn
k=0
✓
n
k
◆
= 2n (33)
Proof. Algebraically, the proof of this quite easily follows from the Binomial Theorem. If
a = 1 and b = 1, the property is achieved [17]. Combinatorially, the proof is done by showing
that both sides of the property count the number of subsets of an n-element set S. First
observe that for some k = 0, 1, 2, . . . ,n, every subset of S is a k-element subset of S. Because
$n
k
%
is the number of k-element subsets of S, it follows that
$n
0
%
+
$n
1
%
+· · ·+
$n
n
%
is the number
of subsets of S. The number of subsets of S can also be counted by observing that since S
has n elements, when forming subsets of S each of the n elements have either one of two
19
fates: membership in the subset or exclusion from the subset. Thus, by the multiplication
principle, there are 2n ways subsets of S can be formed [9].
The q-analogue of Lemma (11) is not found in the literature. However, by using its
qt-analogue, it is easily reduced to its q-analogue form.
Lemma 12.
Y
(
1 + qk) = qμ
✓
μ
◆
q
(34)
Proof. Because the qt-binomial coecients reduce to the q-analogue of the binomial coe-
cients as t approaches one, the same holds true for the properties. Therefore, to obtain the
q-analogue of the property simply allow t to approach 1.
The qt-analogue of the previous classic binomial coecient property is:
Lemma 13.
(1)=
X
μ✓qn(μ0)t−n(μ)
✓
μ
◆
qt
(35)
Proof. There exists an algebraic proof of this property in the qt-analogue, but since it is not
combinatoric it is not included [16].
The property that previous terms in the sequence surrender subsequent terms [21] is
known as the recursive property.
Lemma 14 (Recursive Property of the Classic Binomial Coecients).
✓
n
k
◆
=
✓
n 1
k 1
◆
+
✓
n 1
k
◆
(36)
The recursive property [36] of the classic binomial coecients is easily demonstrated in
Pascal’s Triangle (Figure 1). Notice that the sum of any two consecutive integers in the same
row surrender the integer below and between them. The combinatorial proof [25] is simple.
Proof. Let A be a set of n objects. From A select one element, say x. All k-element subsets
of A are then divided into two disjoint groups according to whether or not these contain x.
20
Because all sets containing x can choose k − 1 elements from the set A/{x}, which consists
of n − 1 elements, there are
!n−1
k−1
"
subsets containing x. Because the subsets not containing
x are able to pull elements from the n − 1 elements remaining in A which are not x, there
are
!n−1
k
"
subsets not containing x.
Lemma 15 (Recursive Property of the q-Binomial Coecients).
✓
n + 1
k
◆
q
= qk
✓
n
k
◆
q
+
✓
n
k − 1
◆
q
(37)
Proof. Consider k ⇥ n matrices in reduced echelon [28]. If the leading 1 in the last row is
in the last column, then the other entries in the last row and column are zero. Deleting
the other entries produces a (k − 1) ⇥ (n − 1) matrix in reduced echelon. Otherwise, the
last column is arbitrary which implies there are qk possibilities for it and deleting it leaves a
k ⇥ (n − 1) matrix in reduced echelon [12].
Lemma 16 (Recursive Property of the qt-Binomial Coecients).
X
μ?n
qn(μ0)t−n(μ)
✓
!i
μ
◆
qt
=
X
⌧?n
qn(⌧0)t−n(⌧)
✓
!
⌧
◆
+
X
⌫?(n−1)
qn(⌫0)+#it−n(⌫0)+#it−n()+1−i
✓
!
⌫
◆
qt
(38)
Proof. While a proof of this property does exist, it is algebraic in nature rather than com-binatorial
and so is not included in this list [16].
The symmetric property of the binomial coecients states that terms in a sequence are
symmetric. This property is also easily demonstrable in Pascal’s Triangle. Note that the
triangle is symmetric across a vertical line drawn from the tip of the Pascal’s Triangle to the
base.
21
Lemma 17 (Symmetric Property for the Classic Binomial Coecients).
✓
n
k
◆
=
✓
n
n k
◆
(39)
Proof. The combinatorial proof is short, but clear. Every k-element subset is determined by
the k elements it contains and also by the n k elements it does not contain [25] .
Lemma 18 (Symmetric Property for the q-Binomial Coecients).
✓
n
k
◆
q
=
✓
n
n k
◆
q
(40)
Proof. The proof arises from the fact that there is a bijection between subspaces of dimension
k of a vector space and the subspaces of codimension k of the dual space [13].
Lemma 19 (Symmetric Property for the qt-Binomial Coecients).
X
μ?n
✓
!
μ
◆
=
X
⌧?(|"|−n)
✓
!
⌧
◆
qt
(41)
Proof. While a proof of this property does exist, it is algebraic in nature rather than com-binatorial
and so is not included in this list [16].
Lemma 20 (Special Valuations of the Classic Binomial Coecients).
✓
n
0
◆
=
✓
n
n
◆
= 1 (42)
✓
n
1
◆
= n (43)
Proof. Property (42) is fairly obvious. The only subset possible of any n-set is the empty
set. Likewise, the only subset of size n which can be formed from the n-set is the n-set
itself. Notice also that this property is an extension of the symmetric property, because
$n
n
%
=
$ n
n−n
%
=
$n
0
%
[33].
22
Property (43) is also fairly obvious. The only way in which subsets of size one can be
formed is by allowing each element in the original n-set to be its own subset.
Lemma 21 (Special Valuations of the q-Binomial Coecients).
✓
n
0
◆
q
=
✓
n
n
◆
q
= 1 (44)
✓
n
1
◆
q
=
1 qn
1 q
=
Xn1
i=0
qi = [n]q (45)
Proof. This proof follows directly from the symmetry property similarly to the classic case.
Lemma 22 (Special Valuations of the qt-Binomial Coecients).
✓
!
0k
◆
qt
=
✓
!
!
◆
qt
= 1 (46)
where 0n is the n-part partition whose parts are all zero.
Proof. While a proof of this property does exist, it is algebraic in nature rather than com-binatorial
and so is not included in this list [16].
Lemma 23 (Classic Binomial Coecients).
2nm
✓
n
m
◆
=
Xn
k=m
✓
n
k
◆✓
k
m
◆
(47)
Lemma 24 (q-Binomial Coecients).
qμ2
⌫Y1
k=μ
(1 + qk)
✓
⌫
μ
◆
=
X"
μ=⌫
q(2)
✓
⌫
!
◆✓
!
μ
◆
(48)
Proof. Using the qt-analogue of the property as given below, the q-analogue of the property
can be derived algebraically by allowing t = 1.
23
Lemma 25 (qt-Binomial Coecients).
t−n(μ)qn(μ0) (1)⌫
(1)μ
✓
⌫
μ
◆
qt
=
X
μ✓"✓⌫
t−n(")qn("0)
✓
⌫
"
◆
qt
✓
"
μ
◆
qt
(49)
Proof. An algebraic proof is defined in [16] but is algebraic in nature, so it is not discussed
in this paper.
Lemma 26 (Special Case of Lemma 23).
2n−1n =
Xn
k=1
k
✓
n
k
◆
(50)
Proof. To prove this property it necessary to prove that both sides of the equality count
the number of ways in which, if any one element is set aside in its own subset, the number
of remaining subsets of any size can be formed. For the left-hand side of the equality, after
selecting the element to be isolated, there are 2n−1 ways in which the n1 remaining elements
can be formed. Note that this follows the same logic as the proof of
Pn
k=0
%n
k
&
= 2n, in that
each of the n 1 elements can have exactly one out of two possible states: inclusion in the
subset or exclusion from the subset. Further, because any of the n elements can be isolated
into its own group, the left-hand side, 2n−1n is received. To begin the investigation of the
right-hand side, observe that exist
%n
k
&
ways of forming a subset with k elements. Further
of any of these subsets of k elements, there exist k number of ways in which to choose the
element to be isolated. Thus, the left- and right-hand side of the property count the same
concept, proving the property [4].
Lemma 27 (Special Case of Lemma (24)).
q(μ
2)
⌫Y−1
k=μ
(1 qk)
X⌫−1
i=0
qi =
✓
⌫
"
◆
q
X"−1
i=0
qi
X
μ"⌫
q(2) (51)
Proof. Using the qt-analogue of the property as given below, the q-analogue of the property
can be derived algebraically by allowing t = 1.
24
Lemma 28 (Special Case of Lemma (25)).
t−n(μ)qn(μ0) (1)⌫
(1)μ
(
Xn
i=1
(1 q⌫i)t1−i
1 q
))
=
X
e1✓"✓⌫
t−n(")qn("0)(
Xn
i=1
(1 q"i)t1−i
1 q
)
✓
⌫
"
◆
qt
(52)
Proof. A proof exists of this property in the qt-analogue; however, it is algebraic in nature
and so is not included in this paper [16].
25
Chapter 3
THE PRINCIPAL THEOREM
For this study the combinatorial formula, we first rewrite the algebraic formula given by
Coskun [16] as a single sum in two dimensions.
Theorem 4 (The Principal Theorem). For z = (!1,!2) and μ = (μ1, μ2)
✓
!
μ
◆
=
q!1μ1−μ1
2 (μ1−1)+!2μ2−μ2
2 (μ2−1)tμ2(−1)|μ|(q−!1t−1)μ2(q−!2)μ2
(q)μ2(qμ1−μ2t)μ2(q)2
μ1−μ2(t)μ1−μ2
·
Xμ1
i=μ2
ti+μ2q−(i−μ2)(!1−!2)(t)i−μ2(qμ1−i+1)i−μ2(qμ2−!2)i−μ2
· (qi−μ2+1)μ1−i(t)μ1−i(q−!1+i)μ1−i
%
(53)
Proof. As stated previously, the above Lemma is derived from Formula (25). We prove this
result in seven steps below:
✓
!
μ
◆
q,t
=
q|μ|t2n(μ)+(1−n)|μ|
(qtn−1)μ
Y
1i<jn
⇢
(qtj−i)μi−μj
(qtj−i−1)μi−μj
(
!μ(qzt"(n); q, t) (54)
Because only the two-dimensional case is investigated, i.e., n = 2, the limit of the product,
1 i > j n, is reduced to 1 i < j 2 which implies i = 1 and j = 2. Furthermore, the
factor, (qtn−1)μ, reduces as so:
(qtn−1)μ =
Yn
i=1
(qtn−i)μi =
Y2
i=1
(qt2−i)μi = (qt)μi(q)μj (55)
For the purposes of generality, the indices, i and j are left as is; they are replaced with their
indicated values later in the proof as is n = 2. Thus, the following formula is received:
✓
!
μ
◆
= f!μ(q, t)!!/μ(q!1t, q!2 ; q, t) (56)
26
where
f!μ(q, t) =
q|μ|t2n(μ0)+(1−n)|μ|(qtj−i)μi−μj
(qt)μi(q)μj (qtj−i−1)μi−μj
(57)
and where !!/μ(y, z; q, t) is the recurrence relation for the skew partition "/μ which leaves
a horizontal strip defined as, "1 ! μ1 ! "2 ! μ2 . . . μn ! "n+1 = μn+1 = 0 for " =
("1,"2, . . . ,"n) and μ = (μ1, μ2, . . . ,μn) so that
!!/μ(y, z; q, t) =
X
⌫"!
!!/⌫(yt−l; q, t)!!/μ(z; q, t) (58)
where ⌫ is all such partitions within μ which create a horizontal strip and whose second row
is 0, i.e., the set of all ⌫ is the set (μ2, 0), (μ2 + 1, 0), . . . , (μ1, 0). By substituting Formula
(58) into Formula (56) the following formula is received:
✓
"
μ
◆
= f!μ(q, t)
X
⌫
t|μ|−|⌫|!μ/⌫(q!1 ; q, t)!⌫(q!2 ; q, t) (59)
where
!!/μ(x; q, t) = (−q/x)−|!|+|μ|q−n(!0)+n(μ0)H!/μ(q, t)
(x−1)!
(x−1)μ
(60)
and
H!/μ(q, p, t, b) =
Y⇢
(qμi−μj−1tj−i)μj−1−!j (q!i+!j t3−j−ib)μj−1−!j
(qμi−μj−1+1tj−i−1)μj−1−!j (q!i+!j+1t2−j−ib)μj−1−!j
&
·
Y(q!i−μj−1+1tj−i−1)μj−1−!j
(q!i−μj−1+1tj−i)μj−1−!j
Y
1<(j−1)n
(qμi+!j+1t1−j−ib)μj−1−!j
qμi+!j t2−j−ib)μj−1−!j
(61)
so that
!μ/⌫ = (−q1−!1)−|μ|+|⌫|q−n(μ0)+n(⌫0)H!/μ(q, t)
(q−!1)μ
(q−!1)μ
(62)
!⌫ = (−q1−!2)−|⌫|q−n(⌫0)H⌫(q, t)(q−!2)⌫ (63)
27
where
Hμ/⌫(q, t) =
Y
1i<j<n
⇢
(t)⌫1−μ2(qμ1−⌫1+1)⌫1−μ2
(q)⌫1−μ2(qμ1−⌫1+1t)⌫1−μ2
#
(64)
H⌫(q, t) = 1 (65)
Further,
(q−"1)μ(q−"2)⌫
(q−"1)⌫
=
Q2
k=1
(t1−kq−"1)μk
Q2
k=1
(t1−kq−"2)⌫k
Q2
k=1
(t1−kq−"1)⌫k
(66)
Thus, substituting Formulas (62) through (66) into Formula (59) the following is obtained:
✓
!
μ
◆
= f"μ(q, t)
X
⌫
t|μ|−|μ|(q1−"1)−|μ|+|⌫|q−n(μ0)+n(⌫0)(q1−"2)−|v|q−n(v)0
· Hμ/⌫(q, p, t, b)
8>><
>>:
Q2
k=1
(t1−kq−"1)μk(q−"2)vk
Q2
k=1
(t1−kq−"1)vk
9>>=
>>;
(67)
Now substitute Formula (64) into Formula (67). Additionally group all non-q-Pochhammer
terms into g"μ(q, t, ⌫) so that:
g"μ(q, t, ⌫) = t|μ|−⌫1(1)−|μ|+2⌫1q−|μ|−"1|μ|−⌫1"1+⌫1"2−(μ1
2 )−(μ2
2 ) (68)
Thus, the following definition is received:
✓
!
μ
◆
= f"μ(q, t)
X
⌫
g"μ(q, t)
(t)⌫1−μ2(qμ1−⌫1+1)⌫1−μ2
(q)⌫1−μ2(qμ1−⌫1t)⌫i−μ2
·
Q2
k=1
(q−"1t1−k)μk
Q2
k=1
(q−"2)⌫k
Q2
k=1
(t1−kq−"1+1)⌫k
(69)
28
For the next step it is realized that, because ⌫2 = 0 the following can be reduced as so:
Y2
k=1
(t1kq!2)⌫k = (q!2)⌫1 (70)
Consequently, after some cancellations of the q-Pochhammer factors inside the summation,
the following is obtained:
✓
"
μ
◆
=
f!μ(q, t)
(q)μ1μ2(t)μ1μ2
X
⌫
g!μ(q, t)(t)⌫1μ2(qμ1⌫1+1)⌫1μ2(q!2)⌫1
·
(q⌫1μ2+1)μ1⌫1
Q2
k=1
(t1kq!1)μk
Q2
k=1
(t1kq!1)⌫k
(71)
In the next step, after some cancellations amongst the q-Pochhammer factors, all factors
independent of ⌫ are taken outside of the summation.
✓
"
μ
◆
=
f!μ(q, t)
Q2
k=1
(t1kq!1)μk
(q)μ1μ2(t)μ1μ2(q!1)μ1
X
⌫
g!μ(q, t)(t)⌫1μ2(qμ1⌫1+1)⌫1μ2(q!2)⌫1
· (q⌫1μ2+1)μ1⌫1(t)μ1⌫1(q⌫1!1)μ1⌫1 (72)
Finally, the g!μ(q, t, ⌫) factors independent of ⌫ are also taken outside of the summation and,
because each ⌫ is a partition such that ⌫2 = 0 μ2 ⌫1 μ1 the formula can be written as
a single sum like so which is the given lemma:
✓
"
μ
◆
=
q!1μ1μ1
2 (μ11)+!2μ2μ2
2 (μ21)tμ2(−1)|μ|(q!1t1)μ2(q!2)μ2
(q)μ2(qμ1μ2t)μ2(q)2
μ1μ2(t)μ1μ2
·
Xμ1
i=μ2
[ti+μ2q(iμ2)(!1!2)(t)iμ2(qμ1i+1)iμ2(qμ2!2)iμ2
· (qiμ2+1)μ1i(t)μ1i(q!1+i)μ1i] (73)
29
Chapter 4
A NEW COMBINATORIAL INTERPRETATION IN TWO DIMENSIONS
Upon simplification to a single sum in two dimensions, it was made possible for a new
combinatorial interpretation to be made in terms of lattice paths by examining each separate
factor in the formula above. The combinatorial interpretation presented in this paper relies
on the Young diagrams created for two partitions, ! = (!1,!2) and μ = (μ1, μ2) where μ ✓ !.
(Note that μ ✓ ! $ μi !i, 8i.)
The Durfee rectangle of μ is defined as the largest rectangular partition which fits inside
the Young diagram of μ. The lattice paths upon which the combinatorial interpretation
presented in this paper relies are all those which begin at the bottom left corner of the
Young diagrams, wrap around the Durfee rectangle of μ or each square extending from the
Durfee rectangle of μ, and then extend towards the end of !. Furthermore, the extension
of μ is defined as the set of all squares in the first row of μ1 not in the Durfee rectangle.
Likewise, the extension of ! is the set of all squares in the first row of ! not in the Durfee
rectangle of !.
Thus, the definition as given in Formula (53) combinatorially gives way to the following
corollary.
Corollary 1. For ! = (!1,!2) and μ = (μ1, μ2)
✓
z
μ
◆
=
q!(",μ)tμ2(−1)|μ|(q"1t1)μ2(q"2)μ2
(q)μ2(q#(μ)+1t)μ2(q)2
#(μ)(t)#(μ)
·
X
L
[t⇢(μ)q⇢(μ)#(")(t)⇢(μ)(q%(μ)+1)⇢(μ)(qμ2"2)⇢(μ)
· (q⇢(μ)+1)%(μ)(t)%(μ)(q%("))%(μ)] (74)
where "(μ) is the number of squares in the extension of μ, ⇢(μ) is the number above the
current lattice path, $(μ) is the number of squares below the lattice path, μ2 is the number
of squares in the second row of the Young diagram of μ, !2 is the number of squares in the
30
second row of !, |μ| is the total number of squares in μ, and the sum is over all lattice paths
as described above. Note that "(!, μ) = q1μ1μ1
2 (μ11)+2μ2μ2
2 (μ21) is defined in terms of
the Young diagram as well; however, computing "(!, μ) is lengthy, so it is discussed below
in its own section.
Proof. Note that in Formula (53), certain di↵erences are common occurrences. Each of these
di↵erences have a combinatorial meaning which is now explained. μ1 μ2 is the di↵erence
between mu1 and μ2, i.e., the number of squares in the extension of μ. This value is assigned
the notation #(μ). i μ2 is the di↵erence between the ith square in the extension of μ and
the second row of μ. This value is assigned the notation ⇢(μ). μ1i is the di↵erence between
the first row of μ and the number of squares up to and including the current square. This
value is assigned the notation %(μ). |μ| is the sum of all rows in the Young tableau.
Figure 4: All lattice paths for ! = (10, 8) and μ = (5, 2)
All factors in the corollary are split either into the external factors group or the internal
factors group based on their placement in the corollary. The external factors are the factors
which are placed outside of the summation, and the internal factors are the factors which
are placed within the summation. The internal factors are further divided into the ↵ and
' groups based on which squares’ weights in the Young diagram the factors adopt. Each of
these groups are discussed separately in the following subsections.
31
q-Pochhammer External Factors
The external factors are the factors which exist outside of the summation. A diagram of
each factor and its weight distribution is provided in Figure (5).
Figure 5: The external non-q-Pochammer factors and their weight distributions for =
(10, 8) and μ = (5, 2)..
0.0.3 Non q-Pochhammer External Factors
The non-q-Pochhammer external factors consist of the following factors:
{q!(",μ), tμ2 , (1)|μ|} (75)
where q!(",μ) = q"1μ1−μ1
2 (μ1−1)+"2μ2−μ2
2 (μ2−1). It is determined that each of these factors
(where, using properties of exponents, q!(",μ) is further split into a product) can be defined
in terms of the weights w of q and the weights w0 of t.
32
Lemma 29 (Non q-Pochhammer External Factors). Each of the factors placed externally of
the summation and which are not q-Pochhammer can be defined in terms of the weights w
and w0.
q1μ1 =
Y
w2s
qw (76)
q2μ2 =
Y
w2s
qw (77)
q
μ1(μ11)
2 =
Y
w2s
qw/2 (78)
q
μ2(μ21)
2 =
Y
w2s
qw/2 (79)
tμ2 =
Y
w2s
tw (80)
(1)|μ| =
Y
w2s
(1)w (81)
Proof. The following is a description for each factor and the distribution of its weights in
the Young diagram of and μ.
First Non q-Pochhammer External Factor
q1μ1 =
Y
w2s
qw (82)
where s is each square in the first row of μ and w is the number of squares in the first row
of .
Second Non q-Pochhammer External Factor
q2μ2 =
Y
w2s
qw (83)
where s is each square in the first row of μ in the Durfee rectangle and w is the weight in
each s where w is the number of squares in the second row of .
33
Third Non q-Pochhammer External Factor
q
μ1(μ11)
2 =
Y
w2s
qw/2 (84)
where s is each square in the first row of μ and w is the weight in each s where w is one less
than the number of squares in the first row of μ.
Fourth Non q-Pochhammer External Factor
q
μ2(μ21)
2 =
Y
w2s
qw/2 (85)
where s is each square in the first row of μ in the Durfee rectangle and w is the weight in
each s where w is one less than the number of squares in the second row of μ.
Fifth Non q-Pochhammer External Factor
tμ2 =
Y
w2s
tw (86)
where s is each square in the first row of μ in the Durfee rectangle and w is the weight of
each s such that w is one.
Sixth Non q-Pochhammer External Factor
(1)|μ| =
Y
w2s
(1)w (87)
where s is all squares in the extension of μ and w is 1.
0.0.4 q-Pochhammer External Factors
The q-Pochhammer external factors consist of the following factors:
{(q−!1t−1)μ2 , (q−!2)μ2 , (q)−1
μ2 , (q"(μ)+1t)−1
μ2 , (q)−2
"(μ), (t)−1
"(μ)} (88)
34
The q-Pochhammer external factors all assign to each square, s, in the first row of μ in the
Durfee rectangle the weights w and w0. The following lemma is a list of each factor and its
definition in terms of its weights w and w0.
Lemma 30. Each factor is defined in terms of a certain weight distribution unique to that
factor.
(q−!1t−1)μ2 =
Q
s
(1 qwtw0)
q⌫(w)t⌫(w0) (89)
(q−!2)μ2 =
Y
s
(1 q−wtw0) (90)
(q)−1
μ2 =
Y
s
(1 qwtw0) (91)
(q#(μ)+1t)−1
μ2 =
Y
s
(1 qwtw0) (92)
(q)−2
#(μ) =
Y
s
(1 qwtw0)2 (93)
(t)−1
#(μ) =
Y
s
(1 qwtw0) (94)
A diagram of each q-Pochhammer external factor and their weight distributions is pro-vided
in Figure (6).
Proof. The weight distribution of each q-Pochhammer external factor is described below.
First q-Pochhammer External Factor
(q−!1t−1)μ2 =
Q
s
(1 qwtw0)
q⌫(w)t⌫(w0) (95)
where ⌫(w) =
P
s
w, s is each square in the first row of the Durfee rectangle of μ, w is one
more than the number of squares to the right of s, and w0 is 1.
35
Figure 6: The external q-Pochammer factors and their weight distributions for = (10, 8)
and μ = (5, 2).
Second q-Pochhammer External Factor
(q−!2)μ2 =
Y
s
(1 q−wtw0) (96)
where s is each square in the first row of the Durfee rectangle of μ, w is one more than the
number of squares to the right of s not in the extension of and w0 is 0.
Third q-Pochhammer External Factor
(q)−1
μ2 =
Y
s
(1 qwtw0) (97)
where s is each square in the first row of the Durfee rectangle of μ, w is one more than the
number of squares to the right of s in the Durfee rectangle and w0 is 0.
Fourth q-Pochhammer External Factor
(q"(μ)+1t)−1
μ2 =
Y
s
(1 qwtw0) (98)
36
where s is each square in the first row of the Durfee rectangle of μ, w is one more than the
number of squares to the right of s and w0 is 1.
Fifth q-Pochhammer External Factor
(q)−2
!(μ) =
Y
s
(1 qwtw0)2 (99)
where s is each square in the extension of μ, w is one more than the number of squares to
the left of s in the extension of μ, and w0 is 0.
Sixth q-Pochhammer External Factor
(t)−1
!(μ) =
Y
s
(1 qwtw0) (100)
where s is each square in the extension of μ, w is the number of squares to the right of s in
the extension of μ, and w0 is 1.
Internal Factors
The internal factors are those factors which are internal to the summation:
{t−⇢(μ), q−⇢(μ)!(#), (t)⇢(μ), (q$(μ)+1)⇢(μ), (qμ2−#2)⇢(μ), (q⇢(μ)+1)$(μ),
(t)$(μ), (q−$(#))$(μ)} (101)
The internal factors are then further broken down into the ↵ factors group and the beta
factors group.
The ↵ and " factors both assign weights w and w0 to each square, s, in the extension
of μ. Because the internal factors are internal to the summation which runs over all lattice
paths, each lattice path will impact which squares’ weights the factors will assume. The ↵
factors will assume the weights of the squares above the current lattice path while the "
factors assume the weights of the squares below the current lattice path.
37
0.0.5 ↵ Factors
The alpha internal factors are the following:
{(t)⇢(μ), (q"(μ)+1)⇢(μ), (qμ2−#2)⇢(μ), (qμ2−#2)⇢(μ)} (102)
As stated previously, the ↵ factors assign weights w and w0 to each square, s, in the extension
of μ and assume the weights of the squares above the current lattice path. The definition of
each factor in terms of its weights w and w0 is listed below in the following lemma.
Lemma 31. Each internal factor in the ↵ group can be defined in terms of a weight distri-bution
unique to that factor.
q−⇢(μ)$(#)t−⇢(μ) =
1
qwtw0 (103)
(t)⇢(μ) =
Y
s
(1 qwtw0) (104)
(q"(μ)+1)⇢(μ) =
Y
s
(1 qwtw0) (105)
(qμ2−#2)⇢(μ) =
Y
s
(1 q−wtw0) (106)
Proof. The following is a list of each factor, its definition in terms of its weight distribution,
and a description of how its weight is distributed.
Non q-Pochhammer Factor
q−⇢(μ)$(#)t−⇢(μ) =
1
qwtw0 (107)
where w is the number of squares in the extension of " and w0 is 1. An example is provided
in Figure (7).
38
Figure 7: t−⇢(μ)q−⇢(μ)"(#) for = (10, 8) and μ = (5, 2)
First q-Pochhammer Factor
(t)⇢(μ) =
Y
s
(1 qwtw0) (108)
where w is the number of squares to the left of s in the extension of μ and w0 is 1. An
example is provided in Figure (8).
Figure 8: (t)⇢(μ) for = (10, 8) and μ = (5, 2)
Second q-Pochhammer Factor
(q$(μ)+1)⇢(μ) =
Y
s
(1 qwtw0) (109)
where w is one more than the number of squares to the right of s in the extension of μ and
w0 is 0. An example is provided in Figure (9).
39
Figure 9: (q!(μ)+1)⇢(μ) for = (10, 8) and μ = (5, 2)
Third q-Pochhammer Factor
(qμ2−#2)⇢(μ) =
Y
s
(1 q−wtw0) (110)
where w is the number of squares to the right of s that are not in the extension and w0 is
0. An example is provided in Figure (10).
Figure 10: (qμ2−#2)⇢(μ) for = (10, 8) and μ = (5, 2)
40
0.0.6 Group
The group of internal factors are the following:
{(q⇢(μ)+1)"(μ), (t)"(μ), (q−"(#))"(μ)} (111)
As stated above, the factors assign weights w and w0 to each square, s, in the extension
of μ and assume the weights of the squares below the current lattice path. Each factor within
the group of internal factors is then defined in terms of these weight distributions as shown
in the below lemma.
Lemma 32. Each factor within the group of internal factors can be defined in terms of
the weight distribution unique to that factor.
(q⇢(μ)+1)"(μ) =
Y
s
(1 qwtw0) (112)
(t)"(μ) =
Y
s
(1 qwtw0) (113)
(q−"(#))"(μ) =
Y
s
(1 q−wtw0) (114)
First q-Pochhammer Factor
(q⇢(μ)+1)"(μ) =
Y
s
(1 qwtw0) (115)
where w is one more than the number of squares to the left of s in the extension of μ and
w0 is 0. An example is provided in Figure (11).
41
Figure 11: (q⇢(μ)+1)"(μ) for = (10, 8) and μ = (5, 2)
Second q-Pochhammer Factor
(t)"(μ) =
Y
s
(1 qwtw0) (116)
where w is the number of squares to the right of s in the extension of μ and w0 is 1. An
example is provided in Figure (12).
Figure 12: (t)"(μ) for = (10, 8) and μ = (5, 2)
42
Third q-Pochhammer Factor
(q−!("))!(μ) =
Y
s
(1 q−wtw0) (117)
where w is one more than the number of squares to the right of s and w0 is 0. An example
is provided in Figure (13).
Figure 13: (q−!("))!(μ) for ! = (10, 8) and μ = (5, 2)
A Complete Example
Using the new combinatorial interpretation presented in this paper, a complete demon-stration
is performed for the reader in this section with a complete description of each
external and internal factor and their weight distributions for the partitions ! = (4, 2) and
μ = (3, 1). The results of the product of the external non-q-Pochhammer factors, the exter-nal
q-Pochhammer factors, the product of the internal ↵ and # factors corresponding to each
lattice lath, and the sum of the internal factors over all lattice paths are separately discussed.
Finally, the product of each of these separate results is calculated and then compared to both
the Okounkov combinatorial interpretation and the Coskun definition.
0.0.7 External Non q-Pochhammer Factor
Diagrams of the external non-q-Pochhammer factors are provided in Figure (14).
43
Figure 14: The external non-q-Pochhammer factors for = (4, 2) and μ = (3, 1)
Each square in the first row of the Durfee rectangle of μ is assigned the weight w = 2 so that
q1μ1 = q12 (118)
Each square in the first row of the Durfee rectangle of μ is assigned the weight w = 2 so that
q2μ2 = q2 (119)
Each square in the first row of μ is assigned the weight w = 2 so that:
q μ1(μ11)
2 = q3 (120)
Each square in the first row of the Durfee rectangle of μ is assigned the weight w = 0 so
that:
q μ2(μ21)
2 = q0 = 1 (121)
44
Each square in the first row of the Durfee rectangle of μ is assigned the weight w0 = 1 so
that:
tμ2 = t1 = t (122)
Each square in the extension of μ is assigned the weight w = 1 so that:
(1)|μ| = (1)2 = 1 (123)
Multiplying all the end results of the above together outputs q11t as the product of the
all the external non-q-Pochhammer factors.
0.0.8 External q-Pochhammer Factor
A diagram displaying each factor and its weight distribution is provided in Figure (15)
Figure 15: The external q-Pochhammer factors for = (4, 2) and μ = (3, 1)
Each square in the first row of the Durfee rectangle of μ is assigned the weights w = {4}
and w0 = {1} respectively so that
(q−1t−1)μ2 = 1q−4t−1 (124)
45
Each square in the first row of the Durfee rectangle of μ is assigned the weights w = {2}
and w0 = {0} respectively so that
(q−!2)μ2 = 1q−2 (125)
Each square in the first row of the Durfee rectangle of μ is assigned the weights w = {1}
and w0 = {0} respectively so that
(q)−1
μ2 = 1q (126)
Each square in the first row of the Durfee rectangle of μ is assigned the weights w = {3}
and w0 = {1} respectively so that
(q"(μ)+1t)−1
μ2 =
1
(1 q3t)
(127)
Each square in the extension of the Durfee rectangle of μ is assigned the weights w = {1, 2}
and w0 = {0} respectively so that
(q)"(μ)2 =
1
(1 q)2(1 q2)2 (128)
Each square in the extension of the Durfee rectangle of μ is assigned the weights w = {1, 0}
and w0 = {1} respectively so that
(t)−1
"(μ) =
1
(1 t)(1 qt)
(129)
Multiplying all of these external q-Pochhammer factors results in
(1 q−2)(1 q−4)
(1 q)3(1 q2)2(1 t)(1 qt)(1 q3t)
. (130)
46
0.0.9 Internal Non q-Pochhammer Factor
Because the summation is taken over all lattice paths, the internal factors will be grouped
by lattice path and then added at the end of this section. However, the weight distributions
are discussed here, because no matter the lattice path the weight distribution will be the
same for each factor for all lattice paths. Also note that the weights for the internal factors
are always assigned to the squares in the extension of μ.
• For t−⇢(μ)q−⇢(μ)"(#) each square is assigned the weights w = {2} and w0 = {1} respec-tively.
• For (t)⇢(μ) each square is assigned the weights w = {0, 1} and w0 = {1} respectively.
• For (q$(μ)+1)⇢(μ) each square is assigned the weights w = {2, 1} and w0 = {1} respec-tively.
• For (qμ2−#2)⇢(μ) each square is assigned the weights w = {1, 0} and w0 = {0} respec-tively.
• For (q⇢(μ)+1)$(μ) each square is assigned the weights w = {1, 2} and w0 = {0} respec-tively.
• For (t)$(μ) each square is assigned the weights w = {2, 1} and w0 = {1} respectively.
• For (q−$(#))⇢(μ) each square is assigned the weights w = {3, 2} and w0 = {1} respectively.
First Lattice Path: A figure demonstrating the first lattice path and the internal factors
and their weight distributions is provided in Figure (16).
• t−⇢(μ)q−⇢(μ)"(#) = 1, because there are no squares above the first lattice path.
• (t)⇢(μ) = 1, because there are no squares above the first lattice path.
• (q$(μ)+1)⇢(μ) = 1, because there are no squares above the first lattice path.
47
• (qμ2!2)⇢(μ) = 1, because there are no squares above the first lattice path.
• (q⇢(μ)+1)#(μ) = (1 q)(1 q2), because the weights of the two squares beneath the
lattice path are adopted.
• (t)#(μ) = (1t)(1qt) because the weights of the two squares beneath the lattice path
are adopted.
• (q#(!))⇢(μ) = (1 q3)(1 q2), because the weights of the two squares beneath the
lattice path are adopted.
Therefore, the product of the factors resulting from the first lattice path is (1 q3)(1 q2)(1 q)(1 q2)(1 t)(1 qt).
Figure 16: The first lattice path for = (4, 2) and μ = (3, 1)
48
Second Lattice Path: A figure demonstrating the second lattice path and the internal
factors and their weight distributions is provided in Figure (17).
• t⇢(μ)q⇢(μ)"(#) = 1
q2t, because the weight of the one square above the second lattice is
adopted.
• (t)⇢(μ) = 1t, because the weight of the one square above the second lattice is adopted.
• (q$(μ)+1)⇢(μ) = 1, because the weight of the one square above the second lattice is
adopted.
• (qμ2#2)⇢(μ) = 1, because the weight of the one square above the second lattice is
adopted.
• (q⇢(μ)+1)$(μ) = (1q)(1q2), because the weight of the one square beneath the lattice
path is adopted.
• (t)$(μ) = (1 t)(1 qt) because the weight of the one square beneath the lattice path
is adopted.
• (q$(#))⇢(μ) = (1 q3)(1 q2), because the weight of the one square beneath the
lattice path is adopted.
Therefore, the product of the factors resulting from the second lattice path is
(1q2)(1q1)(1q2)2(1t)2
q2t .
Third Lattice Path: A figure demonstrating the third lattice path and the internal factors
and their weight distributions is provided in Figure (18).
• t⇢(μ)q⇢(μ)"(#) = 1
q4t2, because the weight of both squares above the second lattice are
adopted.
• (t)⇢(μ) = (1 t)(1 qt), because the weight of both squares above the second lattice
are adopted.
49
Figure 17: The second lattice path for = (4, 2) and μ = (3, 1)
• (q!(μ)+1)⇢(μ) = (1 q)(1 q2), because the weight of both squares above the second
lattice are adopted.
• (qμ2#2)⇢(μ) = 0, because the weight of both squares above the second lattice are
adopted.
• (q⇢(μ)+1)!(μ) = 1, because there are no more squares below the lattice path.
• (t)!(μ) = 1 because there are no more squares below the lattice path.
• (q!(#))⇢(μ) = 1, because there are no more squares below the lattice path.
Therefore, the product of the factors resulting from the third lattice path is 0.
50
Figure 18: The third lattice path for = (4, 2) and μ = (3, 1)
To finish with the internal factors, simply take their sum and simplify to receive
(1 + q)4(1 + q)2(1 + t)(1 q q2t + qt2 + q2t2 + q3t2)
q5t
. (131)
Finally, to complete the computation of the qt-binomial coecients using the new combi-natorial
interpretation simply find and simplify the product of the external non-q-Pochhammer
factors, the external q-Pochammer factors, and the sum of the internal factors to receive:
✓
μ
◆
=
(1 + q)(1 + q4t)(1 q q2t + qt2 + q2t2 + q3t2)
t(1 + qt)(1 + q3t)
(132)
which is the exact same answer as those found with Definitions (25) and (8). Additionally,
the answer was computed in 0.009 seconds–the fastest time of all three methods.
51
Chapter 5
FUTURE RESEARCH
As stated in the introduction, this new combinatorial interpretation of the qt-binomial
coecients theoretically makes the qt-binomial coecients more comprehensible and greatly
simplifies the computation of the qt-binomial coecients; however, a dilemma rests in the fact
that this combinatorial interpretation is only in terms of the second dimension. In order for
this interpretation to reach its fullest potential, it must be generalized to the nth-dimension.
This can feasibly be done following the same methods as the author using algebraic manip-ulation
and experimentation via Wolfram Mathematica (or any other programming tool).
Once this is done, combinatorial proofs of the properties of the qt-binomial coecients as
listed in Section 2.4 may be devised.
This combinatorial interpretation can also have further massive impact in the field of
combinatorics. Many classic cases of special sequences of numbers (such as Stirling, Lah, Bell,
Bernoulli, Fibonacci, Catalan, etc.) are defined in terms of the classic binomial coecients
[26]. Similarly, their q- and qt-analogues are defined in terms of the q- and qt-binomial
coecients. Therefore, it is expected that using this new combinatorial interpretation as a
foundation, the qt-analogues of many of these special numbers will find a new combinatorial
interpretation as well.
Lastly, as is typical of many topics of study in combinatorics, it is believed that this
combinatorial interpretation will find applications in fields of, not only mathematics, but also
applied fields such as operations research, computer science, electrical engineering and statics,
statistical physics, chemistry, and molecular biology [23] where combinatorial interpretations
are necessary to mathematically model real-world situations. Perhaps the generalized nature
of the qt-binomial coecients will open the way to its use in new fields as well.
52
REFERENCES
[1] G. Andrews, R. Roy, and R. Askey, Special functions., Encyclopedia of Mathematics
and Its Applications, Cambridge University Press, 1999.
[2] J. Azose, A tiling interpretation of q-binomial coecieints, Ph.D. thesis, Harvey Mudd
College, May 2007.
[3] E. Bender and S. Williamson, Foundations of applied combinatorics, Addison-Wesley
Publishing Company, 1991.
[4] A. Benjamin and J. Quinn, Proofs that really count: The art of combinatorial proof, The
Dociani Mathematical Expositions, no. 27, The Mathematical Association of America,
200.
[5] C. Berge, Principles of combinatorics, Mathematics in Science and Engineering, vol. 72,
Academic Press, 1971.
[6] G. Berman and K.D. Fryer, Introduction to combinatorics, Academic Press, 1972.
[7] N. Biggs, K. Lloyd, and R. Wilson, Handbook of combinatorics, ch. The History of
Combinatorics, The MIT Press, 1995.
[8] M. B´ona, Combinatorics of permutations, Discrete Mathematics and Its Applications,
CRC Press, 2012.
[9] R. Brualdi, Introductory combinatorics, North-Holland, 1977.
[10] V. Bryant, Aspects of combinatorics: A wide-ranging introduction, Cambridge Univer-sity
Press, 1993.
[11] D. Burton, The history of mathematics: An introduction, 7th ed. ed., McGraw-Hill,
2011.
53
[12] P. Cameron, Combinatorics: Topics, techniques, algorithms, Cambridge University
Press, 1994.
[13] , Notes on counting, Citeseer, 2010.
[14] S. Cooper, B. Berndt, N. Deka, T. Huber, and M. Schlosser (eds.), Ramanujan redis-covered:
Proceedings of a conference on elliptic functions, partitions, and q-series in
memory of k. venkatachaliengar, 2009.
[15] H. Coskun, Multiple bracket function stirling number, and lah number identities, Con-temporary
Mathematics (2000), 1–23.
[16] , Multiple analogues of binomial coecients and families of related special num-bers,
Discrete Mathematics 310 (2010), no. 17-18, 2280–2298.
[17] M. Erickson, Introduction to combinatorics, John Wiley Sons, Inc., 1996.
[18] L. Euler, Introductio in analysin infinitorum, auctore leonhardo eulero..., apudMarcum-
Michaelem Bousquet, 1748.
[19] D. Foata and G. Han, q-series in combinatorics; permutation statistics, Preliminary
version (2004).
[20] C.F. Gauss, Werke, Leipzig: Teubner 3 (1863).
[21] P. Goetgheluck, Computing binomial coecients, The American Mathematical Monthly
94 (1987), no. 4, 360–365.
[22] R.L. Graham and L. Grotschel, M.; Lovasz, Handbook of combinatorics, vol. 2, TheMIT
Press, 1995.
[23] , Handbook of combinatorics, vol. 1, The MIT Press, 1995.
[24] E. Heine, Untersuchungen u ber die reihe, J. Reine Angew. Math. 34 (1847), 285–328.
54
[25] B. Kisacanin, Mathematical problems and proofs: Combinatorics, number theory, and
geometry, Plenum Press, 1998.
[26] J. Konvalina, A unified interpretation of the binomial coecients, the stirling numbers,
and the gaussian coecients, The American Mathematical Monthly 107 (2000), no. 10,
901–910.
[27] A. Lascoux and S. Warnaar, Branching rules for symmetric functions and sln basic
hypergeometric series, Advances in Applied Mathematics 46 (2011), no. 1, 424–456.
[28] J.H. Lint and R.M. Wilson, A course in combinatorics, Cambridge University Press,
1992.
[29] I.G. Macdonald, Symmetric functions and hall polynomials, 2nd ed. ed., Oxford Uni-versity
Press, 1995.
[30] R. Merris, Combinatorics, PWS Publishing Company, 1995.
[31] A. Okounkov, Binomial formula for macdonald polynomials and its applications, Math-ematical
Research Letters 4 (1997), 533–553.
[32] A. Okounkov, Combinatorial formula for Macdonald polynomials, Bethe Ansatz, and
generic Macdonald polynomials, ArXiv Mathematics e-prints (2000).
[33] G. Polya, Lehmer D., M. Phister, J. Riordan, E. Montroll, N.G. Bruijn, F. Harary,
R. Bellman, R. Kalaba, E. Peterson, L. Breiman, A. Tucker, E. Beckenbach, M. Hall,
J. Wolfowitz, C. Tompkins, K. Trueblood, G. Gamow, and H. Weyl, Applied combina-torial
mathematics, John Wiley and Sons, Inc., 1964.
[34] A. Prasad, Counting subspaces of a finite vector space—2, Resonance 15 (2010), no. 12,
1074–1083.
55
[35] B.. Sagan and C. Savage, Combinatorial interpretations of binomial coecient ana-logues
related to lucas sequences, Integers: Electronic Journal of Combinatorial Number
Theory.
[36] M. Shattuck, On some relations satisfied by the p; q-binomial coecient, Siauliai Math-ematical
Seminar 6 (2011), no. 14, 69–84.
[37] R. Stanley, Enumerative combinatorics, vol. 1, Cambridge University Press, December
2011.
[38] , Enumerative combinatorics, vol. 2, Cambridge University Press, December
2011.
[39] D. Stanton and D. White, Constructive combinatorics, Undergraduate Texts in Math-ematics,
Springer-Verlag, 1986.
[40] RJ Wilson (ed.), Applications of combinatorics, Shiva Publishing Limited, 1981.
[41] A. Yong, What is a young tableau?, Notices of the AMS 54, no. 2.
56
VITA
Rachel Landers received two Bachelor of Arts degrees in Mathematics and Spanish,
respectively, in December 2012. She graduated cum laude with honors. In May 2015 she will
graduate with her Master of Science in Mathematics from Texas A&M University-Commerce.
Permanent Address:
Texas A&M University-Commerce
Department of Mathematics
P.O. Box 3011
Commerce, TX 75429
Email: rachel.landers12@gmail.com