ENUMERATION AND SPECIAL FUNCTIONS

DENNIS STANTON

Abstract. These notes for the August 12–16, 2002 Euro Summer School in OPSF at Leuven have three sections with basic introductions to

(1) Enumeration and q-series

(2) Enumeration and orthogonal polynomials

(3) Symmetric functions.

No prior exposure to these areas is assumed. Three excellent textbooks for these three topics are [1], [7], and [17]. Several exercises and open problems are given throughout these notes.

Contents

1. Enumeration and q-series 2 1.1. q-binomial coefficients 3 1.2. Unimodality 4 1.3. Congruences for the partition function 6 1.4. The Jacobi triple product identity 9 1.5. The Rogers-Ramanujan identities and the involution principle 11 1.6. q-Hermite polynomials and the Rogers-Ramanujan identities 13 1.7. Another q-binomial theorem 16 2. Orthogonal polynomials 18 2.1. General orthogonal polynomials and lattice paths 18 2.2. Hankel determinants 21 2.3. Continued fractions 22 3. Symmetric functions 23 3.1. Combinatorial applications 25 3.2. The Jacobi-Trudi identity 26 3.3. Alternating sign matrices 26 3.4. The Borwein conjecture 27 References 27

Research partially supported by NSF grant DMS 0203282.

1. Enumeration and q-series

In this section an introduction to q-series and integer partitions is given, with an emphasis on the properties and applications of the q-binomial coefficient. subsections are coefficients partition function principle identities

An integer partition is a decreasing sequence λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{m} of positive integers. The sum of these integers is the number that λ partitions, λ = 4221 is a partition of 9. Many generating functions involving integer partitions are q-series, or basic hypergeometric series [14].

As our first example, let a_{m} be the number of ways to write a non-negative integer m as a sum of distinct integers which are decreasing, namely the number of partitions of m into distinct parts. If m = 6, the partitions are

6, 51, 42, 321,

so a_{6} = 4. We have

(1.1)  ∑_{m=0}^{∞} a_{m}q^{m} = (1 + q)(1 + q^{2})(1 + q^{3}) ⋯ = ∏_{j=1}^{∞}(1 + q^{j})

since each part of size j appears exactly once or not at all. A refinement of (1.1) can be made by considering how many parts appear, and writing x^{i} for a partition with i parts. In our example a_{6}(x) = x + 2x^{2} + x^{3},

(1.2)  ∑_{m=0}^{∞} a_{m}(x)q^{m} = ∏_{j=1}^{∞}(1 + xq^{j}).

If we reorganize (1.2) to a power series in x it becomes

(1.3)  ∑_{m=0}^{∞} b_{m}(q)x^{m} = ∏_{j=1}^{∞}(1 + xq^{j}),

where b_{m}(q) is the generating function for partitions with exactly m distinct parts. By subtracting one from the mth part, two from the (m − 1)st part, …, up to m from the first part, we obtain a partition where the parts may be equal. In the diagram below (called the Ferrers diagram of a partition) we start with λ = 6531, m = 4, and remove 4321.

\begin{matrix}× & × & × & × & × & × \\ × & × & × & × & × \\ × & × & × \\ × \end{matrix} ⟶ \begin{matrix}× & × \\ × & × \\ × \end{matrix}

We have removed a triangular array of \binom{m+1}{2} squares; what remains is an arbitrary partition with at most m parts. So

b_{m}(q) = q^{\binom{m+1}{2}}b̂_{m}(q),

where b̂_{m}(q) is the generating function for all partitions with at most m parts. We may explicitly find b̂_{m}(q) by considering the conjugate of the Ferrers diagram of a partition with at most m parts: the columns can have any lengths from 1 to m. Letting n_{i} be the number of times that i occurs and using the geometric series we see that

b̂_{m}(q) = ∑_{n_{1},n_{2},··· ,n_{m}≥0} q^{1n_{1}+2n_{2}+···+mn_{m}} = \frac{1}{(1 − q)(1 − q^{2}) ⋯ (1 − q^{m})},

thus

∑_{m=0}^{∞} \frac{q^{\binom{m+1}{2}}}{(1 − q) ⋯ (1 − q^{m})}x^{m} = ∏_{j=1}^{∞}(1 + xq^{j}).

1.1. q-binomial coefficients. We may also ask the same question as in the introduction, putting a maximum size N on the partition with distinct parts. The generating function now is

(1.4)  ∏_{i=1}^{N}(1 + xq^{i}) = ∑_{m=0}^{∞} b_{m}(q, N)x^{m},

where b_{m}(q, N) is the generating function for partitions with exactly m distinct parts, and largest part at most N. By subtracting one from the mth part, …, 1 from the largest part as before, we must consider partitions with at most m parts, and largest part at most N − m.

Definition 1.1. The q-binomial coefficient

[\begin{matrix}N \\ m \end{matrix}]_{q}

is the generating function for all partitions with at most m parts, and largest part at most N − m.

Clearly [\begin{matrix}N \\ m \end{matrix}]_{q} is a polynomial in q of degree m(N − m), whose constant term is 1,

corresponding to the empty partition.

We see that (1.4) can be rewritten as (the q-binomial theorem)

(1.5)  ∏_{i=1}^{N}(1 + xq^{i}) = ∑_{m=0}^{N} [\begin{matrix}N \\ m \end{matrix}]_{q} q^{\binom{m+1}{2}}x^{m}.

This is a q-analogue of the binomial theorem, which is the q → 1 limit. In fact there is an explicit “rational formula” for these coefficients.

Proposition 1.2. The q-binomial coefficient has the explicit formula

[\begin{matrix}N \\ m \end{matrix}]_{q} = \frac{N!_{q}}{m!_{q}(N − m)!_{q}} = \frac{(q; q)_{N}}{(q; q)_{m}(q; q)_{N−m}}

where

n!_{q} = ∏_{i=1}^{n}(1 + q + ⋯ + q^{i−1}), (a; q)_{n} = ∏_{i=0}^{n−1}(1 − aq^{i}).

Exercise 1. To verify Proposition 1.2, one can just show that each side satisfies the same recurrence and initial conditions, here the Pascal triangle relation

[\begin{matrix}N \\ m \end{matrix}]_{q} = [\begin{matrix}N − 1 \\ m \end{matrix}]_{q} + q^{N−m} [\begin{matrix}N − 1 \\ m − 1 \end{matrix}]_{q} .

Can you find another Pascal triangle relation for the q-binomial coefficients?

Exercise 2. Prove the q-binomial theorems in the forms

(1.6)  \frac{1}{(1 − xq)(1 − xq^{2}) ⋯ (1 − xq^{N})} = ∑_{k=0}^{∞} [\begin{matrix}N + k − 1 \\ k \end{matrix}]_{q} x^{k}q^{k},

and

(1.7)  \frac{(ax; q)_{∞}}{(x; q)_{∞}} = ∑_{m=0}^{∞} \frac{(a; q)_{m}}{(q; q)_{m}} x^{m}.

Exercise 3. Show that the number of vector spaces of dimension m which lie inside a vector space of dimension N over a finite field of order q is

[\begin{matrix}N \\ m \end{matrix}]_{q} .

Exercise 4. Show that the generating function for all partitions with exactly m parts (λ_{1}, λ_{2}, ⋯, λ_{m}) such that λ_{1} − λ_{k+1} ≤ i (where k ≤ m) is

q^{m} \frac{(q^{i+1}; q)_{k}}{(q; q)_{m}} .

1.2. Unimodality. The q-binomial coefficient is a polynomial in q whose coefficients are symmetric, and form a unimodal sequence. For example,

(1.8) [\begin{matrix}7 \\ 3 \end{matrix}]_{q} = 1 + q + 2q^{2} + 3q^{3} + 4q^{4} + 4q^{5} + 5q^{6} + 4q^{7} + 4q^{8} + 3q^{9} + 2q^{10} + q^{11} + q^{12}.

The symmetry is easy to see, by considering the complement of a Ferrers diagram of a partition inside a rectangle. There is an involved analytic [26] and combinatorial proof [19] of the unimodal property, but it may be shown more easily algebraically. Here is one such proof, which presupposes knowledge of the finite dimensional irreducible representations of the Lie algebra sl_{2}, the three dimensional algebra of traceless 2 × 2 matrices, sl_{2} = span{e, f, h}. (See the lecture notes of Joris Van der Jeugt in this volume.) We shall use the q-binomial theorem in the proof.

Proof. For each non-negative integer m there is exactly one irreducible representation of sl_{2} of dimension m+1, denoted V_{m} = {v_{−m}, v_{−m+2}, ⋯, v_{m}}. The basis of V_{m} may be chosen so that h(v_{i}) = iv_{i}/2. The formal character of V_{m}, char(V_{m}), is the generating function of the dimensions of the h-eigenspaces

char(V_{m})(q) = ∑_{μ} dim(μ eigenspace of h in V_{m})q^{μ} = q^{−m/2} + q^{−m/2+1} + ⋯ + q^{m/2}.

Note that char(V_{m})(1) = dim(V_{m}) = m + 1.

We fix m to be an even positive integer, so that char(V_{m}) is a Laurent polynomial in q. We consider the kth exterior power ∧^{k}(V_{m}) of the space V_{m}, on which sl_{2} also acts. This means that ∧^{k}(V_{m}) is the vector space of dimension \binom{m+1}{k} whose basis is

v_{i_{1}} ∧ v_{i_{2}} ∧ ⋯ ∧ v_{i_{k}}, {v_{i_{1}}, v_{i_{2}}, ⋯, v_{i_{k}}} ⊂ {v_{−m}, ⋯, v_{m}}.

(Recall that a Lie algebra acts on a tensor by summing its action on each component.) What is the formal character char(∧^{k}(V_{m}))(q)? If we take all possible k, from 0 to m+1, then each basis vector v_{i} may be chosen once or not at all, just as in our original question about partitions with distinct parts, thus

∑_{k=0}^{m+1} char(∧^{k}(V_{m}))(q)t^{k} = (1 + tq^{−m/2})(1 + tq^{−m/2+1}) ⋯ (1 + tq^{m/2}).

Using the q-binomial theorem we see that

(1.9)  char(∧^{k}(V_{m}))(q) = q^{−km/2+\binom{k}{2}} [\begin{matrix}m + 1 \\ k \end{matrix}]_{q} = ∑_{i=0}^{k(m+1−k)} c_{i}q^{−k(m+1−k)/2+i},

where

[\begin{matrix}m + 1 \\ k \end{matrix}]_{q} = ∑_{i=0}^{k(m+1−k)} c_{i}q^{i}.

Our job is to show that c_{i} ≤ c_{i+1} for 0 ≤ i + 1 ≤ k(m + 1 − k)/2. Note that char(∧^{k}(V_{m}))(q) is a Laurent polynomial in q since we have taken m to be even.

Now decompose ∧^{k}(V_{m}) into irreducibles,

∧^{k}(V_{m}) = ⨁_{s≥0} m_{s}V_{s},

where m_{s} is the multiplicity of V_{s}. We have

char(∧^{k}(V_{m}))(q) = ∑_{s≥0} m_{s}(q^{−s/2} + q^{−s/2+1} + ⋯ + q^{s/2}).

Since no half-integer weight occurs in (1.9), we have c_{s} = 0 for s odd. Thus for i + 1 ≤ k(m + 1 − k)/2,

c_{i} = ∑_{s≥k(m+1−k)−2i} m_{s}

so that

c_{i+1} − c_{i} = m_{k(m+1−k)−2i−2} ≥ 0.
□

As an example of this proof, we have just shown that (1.9) corresponds to the decomposition

∧^{3}(V_{6}) = V_{12} ⊕ V_{8} ⊕ V_{6} ⊕ V_{4} ⊕ V_{0},

q^{−6} [\begin{matrix}7 \\ 3 \end{matrix}]_{q} = (q^{−6} + q^{−5} + ⋯ + q^{6}) + (q^{−4} + q^{−3} + ⋯ + q^{4})
+ (q^{−3} + q^{−2} + ⋯ + q^{3}) + (q^{−2} + q^{−1} + ⋯ + q^{2}) + 1.

Unimodality is closely related to the following open problem, see [23]. Fix an m × (N − m) rectangle, and consider all partitions whose Ferrers diagrams fit inside this rectangle. Define a partial order L(m, N − m) on these partitions by containment of the respective diagrams. Thus L(m, N − m) has a unique minimal element, the empty partition ∅, which is covered by the partition 1, which in turn is covered by 11 and 2, until we reach the unique maximum element, the entire rectangle. A symmetric chain C in L(m, N − m) is a collection of partitions

C = {λ_{i}, λ_{i+1}, ⋯, λ_{m(N−m)−i}}

such that λ_{j} is a partition of j for i ≤ j ≤ m(N − m) − i and λ_{j} is covered in L(m, N − m) by λ_{j+1} for i ≤ j < m(N − m) − i − 1. You can imagine C as a saturated chain on the Hasse diagram of L(m, N − m) which is symmetrically located about the middle. A symmetric chain decomposition of L(m, N − m) is a collection of disjoint symmetric chains {C_{s}} whose union is L(m, N −m). Because the q-binomial coefficient is unimodal it is conceivable that L(m, N −m) has such a decomposition. It is unknown if L(m, N − m) has a symmetric chain decomposition for m ≥ 5, although they have been found for m ≤ 4.

Exercise 5. Show that if 1 < k < n, gcd(n, k) = 1, then

\frac{1}{[n]_{q}} [\begin{matrix}n \\ k \end{matrix}]_{q}

is a polynomial in q with non-negative coefficients. (Open problem: Which partitions does it enumerate?)

1.3. Congruences for the partition function. As another application of the qbinomial theorem we consider p(n), the total number of partitions of n, whose generating function is

∑_{n=0}^{∞} p(n)q^{n} = \frac{1}{(q; q)_{∞}} .

The values of p(n) for 0 ≤ n ≤ 29 are tabulated below.

\begin{matrix}n & p(n) & n & p(n) \\ 0 & 1 & 15 & 176 \\ 1 & 1 & 16 & 231 \\ 2 & 2 & 17 & 297 \\ 3 & 3 & 18 & 385 \\ 4 & 5 & 19 & 490 \\ 5 & 7 & 20 & 627 \\ 6 & 11 & 21 & 792 \\ 7 & 15 & 22 & 1002 \\ 8 & 22 & 23 & 1255 \\ 9 & 30 & 24 & 1575 \\ 10 & 42 & 25 & 1958 \\ 11 & 56 & 26 & 2436 \\ 12 & 77 & 27 & 3010 \\ 13 & 101 & 28 & 3718 \\ 14 & 135 & 29 & 4565 \end{matrix}

Ramanujan proved that

p(5n + 4) ≡ 0 mod 5.

We now give a proof of this congruence using the q-binomial theorem. The idea is to find a generating function for p(5n + 4) with a quadratic form whose symmetry group contains a 5-cycle.

Proof. We start by considering the “sieved” q-binomial theorem: fix non-negative integers M, N, t, r, and s, where 0 ≤ r < t, and consider

(1.10)  (−xq; q)_{(M+N)t+r} = ∏_{i=1}^{r}(−xq^{i}; q^{t})_{M+N+1} ∏_{i=r+1}^{t}(−xq^{i}; q^{t})_{M+N}.

Finding the coefficient of x^{Mt+s} in (1.10) we have

(1.11) [\begin{matrix}(M + N)t + r \\ Mt + s \end{matrix}]_{q} q^{\binom{s}{2}} = ∑_{n⃗, 1·n⃗=s} q^{Q(n⃗)} ∏_{i=0}^{r−1} [\begin{matrix}M + N + 1 \\ M + n_{i} \end{matrix}]_{q^{t}} ∏_{i=r}^{t−1} [\begin{matrix}M + N \\ M + n_{i} \end{matrix}]_{q^{t}} .

where

n⃗ = (n_{0}, ⋯, n_{t−1}), Q(n⃗) = t||n⃗||^{2}/2 + b⃗ · n⃗ − st/2, b⃗ = (0, 1, ⋯, t − 1).

The M → ∞, N → ∞ limit of (1.11) is

(1.12)  \frac{q^{\binom{s}{2}}}{(q; q)_{∞}} = \frac{1}{(q^{t}; q^{t})_{∞}^{t}} ∑_{n⃗, n⃗·1=s} q^{Q(n⃗)}.

Since

Q(n⃗) = t(n_{1}^{2} + ⋯ + n_{t−1}^{2}) + t ∑_{1≤i<j≤t−1} n_{i}n_{j} + t\binom{s}{2} − ts ∑_{i=1}^{t−1} n_{i} + b⃗ · n⃗,

the r modulo t terms in (1.12) must occur only when b⃗ · n⃗ ≡ r mod t.

∑_{m,m+\binom{s}{2}≡r mod t} p(m)q^{m+\binom{s}{2}} = \frac{1}{(q^{t}; q^{t})_{∞}^{t}} ∑_{n⃗,n⃗·1=s,b⃗·n⃗≡r mod t} q^{Q(n⃗)}.

Choose t = 5, s = 0 and r = 4,

∑_{m=0}^{∞} p(5m + 4)q^{5m+4} = \frac{1}{(q^{5}; q^{5})_{∞}^{5}} ∑_{n⃗,n⃗·1=0,b⃗·n⃗≡4 mod 5} q^{Q(n⃗)}.

The five n⃗ vectors for p(4) = 5 are

v_{0} = (1, −1, 0, 0, 0), v_{1} = (0, 1, −1, 0, 0), v_{2} = (0, 0, 1, −1, 0),
v_{3} = (0, 0, 0, 1, −1), v_{4} = (1, 1, 0, −1, −1).

If a change of basis is made to m_{0}v_{0} + m_{1}v_{1} + m_{2}v_{2} + m_{3}v_{3} + m_{4}v_{4}, the new quadratic form is

Q̂(m⃗) = 5||m⃗||^{2} − 5(m_{0}m_{1} + m_{1}m_{2} + m_{2}m_{3} + m_{3}m_{4} + m_{4}m_{0}) − 1,

with m⃗ · 1 = 1. This clearly has a symmetry group including a 5-cycle, with no fixed points. □

This argument also proves p(7n + 5) ≡ 0 mod 7 and p(11n + 6) ≡ 0 mod 11, see [13]. Dyson proposed a combinatorial proof of Ramanujan’s congruence, using the rank of a partition,

rank(λ) = largest part of λ − number of parts of λ.

It has been proven that the rank modulo 5 splits the partitions of 5n + 4 into 5 equal classes, for example

rank(4) = 3, rank(31) = 1, rank(22) = 0, rank(211) = −1, rank(1111) = −3.

It is an open problem to find an explicit bijection between these 5 equinumerous rank classes.

Exercise 6. Show that the generating function for all partitions whose rank is r ≥ 0 is

∑_{m≥1} q^{2m+r−1} [\begin{matrix}2m + r − 2 \\ m − 1 \end{matrix}]_{q} = \frac{1}{(q; q)_{∞}} ∑_{s=1}^{∞}(−1)^{s−1}q^{s(3s−1)/2+rs}(1 − q^{s}).

1.4. The Jacobi triple product identity. One of the most useful results for partitions is the Jacobi triple product identity

(1.13)  (−x; q)_{∞}(−q/x; q)_{∞}(q; q)_{∞} = ∑_{m=−∞}^{∞} q^{\binom{m}{2}}x^{m}.

We sketch three proofs for this result. The first proof again uses the q-binomial theorem,

(−x; q)_{N}(−q/x; q)_{N} = ∑_{m=−N}^{N} [\begin{matrix}2N \\ N + m \end{matrix}]_{q} q^{\binom{m}{2}}x^{m},

and then lets N → ∞ using

lim_{N→∞} [\begin{matrix}2N \\ N + m \end{matrix}]_{q} = \frac{1}{(q; q)_{∞}}

for any fixed m.

A simple combinatorial proof of (1.13) in the form

(1.14)  (−x; q)_{∞}(−q/x; q)_{∞} = \frac{1}{(q; q)_{∞}} ∑_{m=−∞}^{∞} q^{\binom{m}{2}}x^{m}

is due to Sylvester-Hathaway. The left side of (1.14) is the generating function for pairs of partitions with distinct parts, while the right side is the generating function for pairs: a triangular partition, and an arbitrary partition. A bijection may be given between these two sets of pairs, by placing a triangle atop a partition, and cutting the resulting diagram it into a pair of partitions with distinct parts. In the example below our triangle 21 has been placed atop 7622, and then cut along the triangle’s diagonal to obtain two partitions with distinct parts, 6521 (reading along columns), and 42 (reading along rows).

\begin{matrix}× \\ × & × \\ × & × & × & × & × & × & × \\ × & × & × & × & × & × \\ × & × \\ × & × \end{matrix} ⟶ (\begin{matrix}× \\ × & × \\ × & × & × \\ × & × & × & × \\ × & × \\ × & × \end{matrix} , \begin{matrix}× & × & × & × \\ & × & × \end{matrix})

Some details need to be checked, but this is the main idea of the proof.

A third proof of (1.13) follows by verifying the functional equation xF (qx) = F (x) for

F (x) = (−x; q)_{∞}(−q/x; q)_{∞} = ∑_{n=−∞}^{∞} f_{n}x^{n}.

The functional equation implies that f_{n} = q^{n−1}f_{n−1}, thus f_{n} = q^{\binom{n}{2}}f_{0} and we need only find the constant term f_{0} = 1/(q; q)_{∞} to finish the proof. This may be accomplished combinatorially using the Frobenius notation for partitions, or by using the Durfee square in Exercise 7.

Exercise 7. Show that Exercise 2 implies that

(−x; q)_{∞} = ∑_{k=0}^{∞} \frac{q^{\binom{k}{2}}}{(q; q)_{k}}

and conclude that

f_{0} = ∑_{k=0}^{∞} \frac{q^{k^{2}}}{(q; q)_{k}^{2}} .

Finally use the Durfee square of a partition—the largest NW justified square in the Ferrers diagram—to conclude that f_{0} = 1/(q; q)_{∞}.

Exercise 8. Use the Jacobi triple product identity (1.13) to find an expansion for (q; q)_{∞}, and find an involution on partitions with distinct parts which proves this identity. Hopefully you found the Euler Pentagonal Number Theorem.

The Macdonald identities [18] generalize the Jacobi triple product identity (1.13) to root systems. The infinite product is now

∏_{α∈Φ^{+}}(e^{α}; q)_{∞}(qe^{−α}; q)_{∞}.

In the case of the root system Φ of type A_{1}, there is one positive root Φ^{+} = {α}, and if e^{α} = −x, we have F (x). The statement of the theorem is an exact sum expansion for this infinite product. For the root system A_{n−1}, the function to be expanded is

(1.15)  F (x⃗) = F (x_{1}, ⋯, x_{n}) = ∏_{1≤i<j≤n}(x_{i}/x_{j}; q)_{∞}(qx_{j}/x_{i}; q)_{∞}.

The third proof of (1.13) also works for the Macdonald identities. First you find a functional equation which reduces the unknown expansion constants to a finite number, then you show that the constant term is sufficient to determine all of these non-zero constants, and finally you evaluate the constant term. For type A_{n−1} the constant term is 1/(q; q)_{∞}^{n−1}. It is an open problem to find a combinatorial argument, analogous to either the Frobenius or Durfee square proof for (1.13), which shows that the constant term in F (x⃗) is 1/(q; q)_{∞}^{n−1}.

Here we give the details for the Macdonald identity of type B_{2}, where the positive roots are Φ^{+} = {e_{1}, e_{2}, e_{2} − e_{1}, e_{1} + e_{2}}, e_{1} = (1, 0), e_{2} = (0, 1). Let

F (x, y) = (x, q/x, y, q/y, y/x, qx/y, xy, q/xy; q)_{∞} = ∑_{i,j} f_{i,j}x^{i}y^{j}.

The functional equations are

−qx^{3}F (qx, y) = F (x, y), −y^{3}F (x, qy) = F (x, y),

which imply

−q^{i−2}f_{i−3,j} = f_{i,j}, −q^{j−3}f_{i,j−3} = f_{i,j},

so that a fundamental domain for the constants f_{i,j} is 0 ≤ i, j ≤ 2.

We next use the Weyl group (see Margit Rösler’s lectures in this volume), which is generated by reflections in the hyperplanes perpendicular to the roots e_{1} and e_{2} − e_{1}. These become

(1.16)  −xF (1/x, y) = F (x, y),  −f_{1−i,j} = f_{i,j},
(1.17)  −yF (y, x) = xF (x, y), −f_{j−1,i} = f_{i−1,j}.

Equation (1.17) implies that f_{0,1} = f_{1,2} = f_{2,0} = 0, along with f_{0,0} = f_{2,1}, f_{1,0} = f_{2,2}, f_{1,1} = f_{0,2}, while (1.16) implies f_{0,0} = −f_{1,0}, f_{0,1} = −f_{1,1}, f_{0,2} = −f_{1,0}. Thus, the only possible non-zero values are taken f_{0,0} = −f_{1,0} = f_{2,1} = −f_{2,2}, and we need only evaluate the constant term f_{0,0} in

F (x, y) = f_{0,0} ∑_{i,j} q^{3\binom{j}{2}+3\binom{i}{2}+i}(−1)^{i+j}(x^{3i}y^{3j} − x^{3i+1}y^{3j} + x^{3i+2}y^{3j+1} − x^{3i+2}y^{3j+2}).

Exercise 9. By summing the above identity at x = 1, ω, ω^{2}, where ω^{3} = 1, show that

f_{0,0} = \frac{1}{(q; q)_{∞}^{2}} .

The q-Dyson conjecture is a finite form of the constant term of the Macdonald identity of type A_{n−1}. Zeilberger and Bressoud [29] proved that the constant term of

∏_{1≤i<j≤n}(x_{i}/x_{j}; q)_{a_{i}}(qx_{j}/x_{i}; q)_{a_{j}}

is the q-multinomial coefficient

[\begin{matrix}a_{1} + ⋯ + a_{n} \\ a_{1}, ⋯, a_{n} \end{matrix}]_{q} .

Their proof uses combinatorial methods similar to the q-series example in Section 1.6. No other proof is known!

1.5. The Rogers-Ramanujan identities and the involution principle. The Rogers-Ramanujan identities are

(1.18)  ∑_{n=0}^{∞} \frac{q^{n^{2}}}{(q; q)_{n}} = \frac{1}{(q; q^{5})_{∞}(q^{4}; q^{5})_{∞}} ,

(1.19)  ∑_{n=0}^{∞} \frac{q^{n^{2}+n}}{(q; q)_{n}} = \frac{1}{(q^{2}; q^{5})_{∞}(q^{3}; q^{5})_{∞}} .

Macmahon found a combinatorial interpretation of these identities.

Proposition 1.3 (Macmahon’s Interpretation of RR). The number of integer partitions of n into parts which differ by at least two is equal to the number of partitions of n into parts congruent to 1 or 4 mod 5. Moreover an analogous result holds if no 1’s are allowed for the difference partitions and the mod 5 parts must be 2 or 3.

If n = 9, the equinumerous partitions in this statement are

9 9  9 72
81 6111
72 441  72 333
63 411111  63 3222.
531 111111111

Schur gave a combinatorial proof of the Rogers-Ramanujan identities in the following form. He considered a generating function for pairs of partitions (λ, μ), where λ has distinct parts and μ has parts which differ by at least two, (λ, μ) ∈ Distinct × Diff_{2},

(q; q)_{∞} ∑_{n=0}^{∞} \frac{q^{n^{2}}}{(q; q)_{n}} = GF (Distinct × Diff_{2}).

The partition λ, which has distinct parts, also has a minus sign attached to each part. Thus the set Distinct × Diff_{2} may be considered as a “signed” set,

sign((λ, μ)) = (−1)^{# parts of λ}.

For example,

(∅, 94), (43, 752) are positive, (532, 741), (8, 97531) are negative.

Schur combinatorially defined an involution on the pairs (λ, μ) which changed the number of parts of λ by one, thereby changing its sign, but preserved the number of cells in λ ∪ μ. His involution cancels all pairs, except for the fixed points, which turn out to be

(1.20)  ((2p − 1, 2p − 2, ⋯, p), (2p − 1, 2p − 3, ⋯, 3, 1)), p ≥ 0,
(1.21)  ((2p, 2p − 2, ⋯, p + 1), (2p − 1, 2p − 3, ⋯, 3, 1)), p ≥ 1.

Thus Schur proved that

(q; q)_{∞} ∑_{n=0}^{∞} \frac{q^{n^{2}}}{(q; q)_{n}} = 1 + ∑_{p=1}^{∞}(−1)^{p}(q^{p(5p−1)/2} + q^{p(5p+1)/2})

and the Jacobi triple product identity (1.13) completes the proof of (1.18). Schur’s clever involution on (λ, μ) was defined in two steps [20].

Step 1: Compare the largest parts λ_{1} and μ_{1}. (1) If λ_{1} > μ_{1} + 1 move λ_{1} to μ.

(2) If μ_{1} > λ_{1}, then move μ_{1} to λ.

For example Step 1 matches (43, 752) ↔ (743, 52) and (832, 51) ↔ (32, 851). Step 1 is not defined if λ_{1} = μ_{1} or if λ_{1} = μ_{1} + 1, and Step 2 takes care of this possibility.

• Let lr(λ) be the length of the leading run of λ. (For example if λ = 87652, lr(λ) = 4, from the leading 8765 of λ.)

• Let sp(λ) be the smallest part of λ (sp(87652) = 2).

• Let ldr(μ) be the length of the leading double run of μ. (If μ = 9752, then ldr(μ) = 3, from the leading double run 975 of μ.)

Step 2A: (λ_{1} = μ_{1})

(1) If sp(λ) = min{sp(λ), lr(λ), ldr(μ)}, move the smallest part of λ adjacent to the leading run of λ. (For example (87652, 8642) → (9865, 8642).)

(2) If ldr(μ) = min{sp(λ), lr(λ), ldr(μ)} < sp(λ), move the leading double run of μ under the smallest part of λ. (For example (874, 862) → (8742, 752).)

(3) If lr(λ) = min{sp(λ), lr(λ), ldr(μ)} < min{sp(λ), ldr(μ)}, move the leading run of λ to parts 2, 3, ⋯, lr(λ)+1 of μ, and then move the largest part of μ to a new largest part of λ. (For example, (984, 9753) → (9874, 863).)

The result of Step 2A always gives λ_{1} = μ_{1} + 1. Step 2B: (λ_{1} = μ_{1} + 1)

(1) If lr(λ) = min{sp(λ), lr(λ), ldr(μ)} < sp(λ), move the leading run of λ to a new smallest part of λ.

(2) If sp(λ) = min{sp(λ), lr(λ), ldr(μ)}, attach the smallest part of λ to the leading double run of μ.

(3) If ldr(μ) = min{sp(λ), lr(λ), ldr(μ)} < min{sp(λ), lr(λ)}, move the leading double run of μ to parts 2, 3, ⋯, ldr(μ) + 1 of λ, and then move the largest part of λ to a new largest part of μ.

Steps 2A(i) and 2B(i) are inverses for i = 1, 2, 3. It is an exercise to see that Step 2 is not defined only for the sets (1.20) and (1.21).

While Schur’s proof is marvelous, it does not give a direct bijection for Macmahon’s interpretation of the Rogers-Ramanujan identities. As of today there is no direct bijection for the Rogers-Ramanujan identities (1.18)–(1.19)! There is an indirect one by Garsia and Milne [12], which uses the involution principle.

Here is the general setup for the involution principle. Let A = A^{+}∪A^{−} be a finite set, consisting of some positive (A^{+}) and negative (A^{−}) elements. A sign-reversing involution ϕ is a map ϕ : A → A such that ϕ^{2} = ϕ and if ϕ(x) ≠ x then sign(x)sign(ϕ(x)) = −1. This just means that ϕ changes sign on its orbits of size 2. Suppose that ϕ_{1} and ϕ_{2} are two sign-reversing involutions on A, with fixed point sets F P (ϕ_{1}) ⊂ A^{+} and F P (ϕ_{2}) ⊂ A^{+} respectively. Note that |A^{+}| − |A^{−}| = |F P (ϕ_{1})| = |F P (ϕ_{2})| so there is a bijection b : F P (ϕ_{1}) → F P (ϕ_{2}).

The involution principle guarantees an algorithm to define such a bijection b. If x ∈ F P (ϕ_{1}) ∩ F P (ϕ_{2}), then B(x) = x, otherwise apply ϕ_{1} ∘ ϕ_{2} until you reach F P (ϕ_{2}). This is guaranteed to occur, since A is finite.

Garsia and Milne showed how to apply this method to Schur’s involution [12]. Another involution is necessary to cancel the infinite product (q; q)_{∞} when you move it to the other side, thus two involutions are involved.

There are generalizations of the Rogers-Ramanujan identities (1.18)–(1.19) to all moduli involving multisums (see [1]). For example for mod 7 we have

∑_{n_{1}≥n_{2}≥0} \frac{q^{n_{1}^{2}+n_{2}^{2}}}{(q; q)_{n_{1}−n_{2}}(q; q)_{n_{2}}} = \frac{(q^{3}, q^{4}, q^{7}; q^{7})_{∞}}{(q; q)_{∞}} .

1.6. q-Hermite polynomials and the Rogers-Ramanujan identities. There are many proofs of the Rogers-Ramanujan identities [3]. Rogers’ original proof used a set of orthogonal polynomials, the continuous q-Hermite polynomials. In this section we give a modern version [24] of Rogers’ proof, starting from the well-known integral

(1.22)  I(t) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−xt+t^{2}/2}e^{−x^{2}/2} dx = e^{t^{2}}.

Note that although (1.22) is easy to prove by completing the square, we are interested in another proof, whose q-analogue will be apparent. The rescaled Hermite polynomials Ĥ_{n}(x) = H_{n}(x/\sqrt{2})/2^{n/2} have the orthogonality relation

(1.23)  \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} Ĥ_{m}(x)Ĥ_{n}(x)w(x) dx = n!δ_{mn}, w(x) = e^{x^{2}/2},

and the generating function

(1.24)  G(x, t) = ∑_{n=0}^{∞} Ĥ_{n}(x)\frac{t^{n}}{n!} = e^{xt−t^{2}/2},

thus (1.22) is the integral of the inverse of the Hermite generating function times the Hermite weight.

We will write down a natural q-analogue of this integral. Evaluating it in two different ways gives the two sides of the Rogers-Ramanujan identities. So we need a q-analogue of the Hermite polynomials, their measure and generating function:

H_{n}(x|q) = ∑_{k=0}^{n} [\begin{matrix}n \\ k \end{matrix}]_{q} e^{i(n−2k)θ}, x = cos θ,

is a polynomial in x = cos θ, because it may be rewritten as a sum of Chebyshev

polynomials T_{n−2k}(x) = cos((n − 2k)θ) due to [\begin{matrix}n \\ k \end{matrix}]_{q} = [\begin{matrix}n \\ n − k \end{matrix}]_{q} . These polynomials

satisfy the 3-term recurrence relation

(1.25)  2xH_{n}(x|q) = H_{n+1}(x|q) − (1 − q^{n})H_{n−1}(x|q),

with initial values H_{0}(x|q) = 1, H_{1}(x|q) = 2x. One can use (1.25) to show that

lim_{q→1^{−}} \frac{H_{n}(x\sqrt{1 − q}/2|q)}{(1 − q)^{n/2}} = Ĥ_{n}(x).

The generating function for H_{n}(x|q) can easily be found from (1.25):

∑_{n=0}^{∞} H_{n}(x|q)\frac{t^{n}}{(q; q)_{n}} = ∏_{k=0}^{∞}(1 − 2xtq^{k} + t^{2}q^{2k})^{−1} = (te^{iθ}, te^{−iθ}; q)_{∞}^{−1}.

The orthogonality relation for H_{n}(x|q) is known [14] to be

∫_{0}^{π} H_{m}(cos θ|q)H_{n}(cos θ|q)w_{q}(cos θ) dθ = (q; q)_{n}δ_{mn},

w_{q}(cos θ) = \frac{(q; q)_{∞}}{2π} (e^{2iθ}, e^{−2iθ}; q)_{∞}.

So the exact analogue of (1.22) for H_{n}(x|q) is

I_{q}(t) = \frac{(q; q)_{∞}}{2π} ∫_{0}^{π}(te^{iθ}, te^{−iθ}, e^{2iθ}, e^{−2iθ}; q)_{∞} dθ.

We must evaluate I_{q}(t) and understand why it is a q-analogue of e^{t^{2}}. Since we are integrating with respect to the q-Hermite weight, we must find the constant term in the q-Hermite expansion of (te^{iθ}, te^{−iθ}; q)_{∞}. However

(te^{iθ}, te^{−iθ}; q)_{∞} = ∑_{n=0}^{∞} H_{n}(x|q^{−1})\frac{q^{\binom{n}{2}}(−t)^{n}}{(q; q)_{n}} ,

so we just need to find the q-Hermite constant term for H_{n}(x|q^{−1}). Fortunately, Rogers [14] found all of the expansion coefficients

H_{n}(x|q^{−1}) = ∑_{k=0}^{n/2} \frac{q^{k(k−n)}(q; q)_{n}}{(q; q)_{k}(q; q)_{n−2k}} H_{n−2k}(x|q),

so that

I_{q}(t) = ∑_{n≥0, even} \frac{q^{\binom{n}{2}}(−t)^{n}}{(q; q)_{n}} \frac{q^{−n^{2}/4}(q; q)_{n}}{(q; q)_{n/2}}

= ∑_{m=0}^{∞} \frac{q^{m^{2}−m}t^{2m}}{(q; q)_{m}} .

This is clearly a q-analogue of e^{t^{2}}, and gives the sum side of (1.18) and (1.19) if t = \sqrt{q}, q.

We need an alternative evaluation for I_{q}(\sqrt{q}) and I_{q}(q) to give the product sides of (1.18) and (1.19). We use exponential orthogonality on [−π, π] instead of q-Hermite orthogonality. For t = \sqrt{q} the Jacobi triple product identity (1.13) implies

(q, \sqrt{q}e^{iθ}, \sqrt{q}e^{−iθ}; q)_{∞} = ∑_{k=−∞}^{∞}(−1)^{k}q^{k^{2}/2}e^{−ikθ},

(q, e^{2iθ}, e^{−2iθ}; q)_{∞} = (1 − e^{2iθ}) ∑_{j=−∞}^{∞}(−1)^{j}q^{(j^{2}+j)/2}e^{2ijθ}.

so that

I_{q}(\sqrt{q}) = \frac{1}{2(q; q)_{∞}} ∑_{j=−∞}^{∞}(q^{2j^{2}}q^{(j^{2}+j)/2} − q^{2(j+1)^{2}}q^{(j^{2}+j)/2})(−1)^{j}

= \frac{1}{(q; q)_{∞}} ∑_{j=−∞}^{∞} q^{2j^{2}}q^{(j^{2}+j)/2}(−1)^{j} = \frac{1}{(q; q^{5})_{∞}(q^{4}; q^{5})_{∞}} .

Note that from the point of view of this proof, the mod 5 condition appears because the q-Hermite weight function involves e^{2iθ} and 1 + 2^{2} = 5.

Exercise 10. Verify the exponential details to show that I_{q}(q) does yield (1.19).

1.7. Another q-binomial theorem. We have seen several applications of the qbinomial theorem. Here we give another q-binomial theorem, and shall see it is equivalent to the original q-binomial theorem.

Suppose that x and y are non-commuting variables, but do satisfy yx = qxy, where q commutes with x and y. Then any word in x and y can be permuted to x^{i}y^{j} at the expense of a power of q, for example, yxxyyxx = q^{8}x^{4}y^{3}, because we moved the first y past 4 x’s, and the second and third y’s past 2 x’s.

Theorem 1.4. If yx = qxy where q commutes with x and y, then

(1.26)  (x + y)^{N} = ∑_{m=0}^{N} [\begin{matrix}N \\ m \end{matrix}]_{q} x^{m}y^{N−m}.

Proof. Each word w of m x’s and N −m y’s corresponds to a partition which lies inside an (N − m) × m rectangle. Moreover any such partition corresponds to a unique word w. In our example of w = yxxyyxx the partition is 422. If w = q^{e}x^{m}y^{N−m}, then e is the sum of the parts of the partition. The generating function for all partitions which lie inside an (N − m) × m rectangle is the definition of the q-binomial coefficient

[\begin{matrix}N \\ N − m \end{matrix}]_{q} = [\begin{matrix}N \\ m \end{matrix}]_{q} . □

If we imagine y as a letter larger than x, then (1.26) can be restated as

∑_{words w with m x’s, N − m y’s} q^{inv(w)} = [\begin{matrix}N \\ m \end{matrix}]_{q} .

where

inv(w) = |{(i, j) : i < j, w_{i} > w_{j}}|.

Exercise 11. Let W (a_{1}, a_{2}, ⋯, a_{m}) = W (a⃗) be the set of all words w of length a_{1} + a_{2} + ⋯ + a_{m} with exactly a_{1} 1’s, a_{2} 2’s, ⋯, a_{m} m’s. Show that

∑_{w∈W (a⃗)} q^{inv(w)} = [\begin{matrix}a_{1} + a_{2} + ⋯ + a_{m} \\ a_{1}, a_{2}, ⋯, a_{m} \end{matrix}]_{q} = \frac{(a_{1} + a_{2} + ⋯ + a_{m})!_{q}}{a_{1}!_{q} a_{2}!_{q} ⋯ a_{m}!_{q}} .

Let’s prove the q-analogue of the Pfaff-Saalschütz sum for a 1-balanced _{3}ϕ_{2} terminating basic hypergeometric sum using Exercise 11. (This proof is due to Zeilberger [27]).

(1.27) [\begin{matrix}a + b \\ a + k \end{matrix}]_{q} [\begin{matrix}a + c \\ c + k \end{matrix}]_{q} [\begin{matrix}b + c \\ b + k \end{matrix}]_{q}

= ∑_{n=k}^{min(a,b,c)} q^{n^{2}−k^{2}} \frac{[a + b + c − n]!_{q}}{[a − n]!_{q}[b − n]!_{q}[c − n]!_{q}[n + k]!_{q}[n − k]!_{q}} .

Proof. Let S = A_{1} × A_{2} × A_{3} be the set where (1) A_{1} consists of all words with a + k 1’s, and b − k 2’s,

(2) A_{2} consists of all words with a − k 1’s, and c + k 3’s,

(3) A_{3} consists of all words with b + k 2’s, and c − k 3’s.

We weigh each word by its inversion number, so that the LHS of (1.27) is the generating function of S. We need a bijection from S to words of length a + b + c − n with 5 types of letters, with multiplicities a − n, b − n, c − n, n + k and n − k for some n between k and min{a, b, c}. We shall see that we may take words in the five symbols

(\begin{matrix}1 \\ 1 \\ − \end{matrix}) , (\begin{matrix}1 \\ 3 \\ 2 \end{matrix}) , (\begin{matrix}2 \\ − \\ 2 \end{matrix}) , (\begin{matrix}2 \\ 1 \\ 3 \end{matrix}) , (\begin{matrix}− \\ 3 \\ 3 \end{matrix}) .

The algorithm for the bijection is following. Let s = (w_{1}, w_{2}, w_{3}) ∈ S, and write w_{2} under w_{1}, and w_{3} under w_{2}, all left justified. Scan this “triple word” left to right. If we see

(\begin{matrix}1 \\ 1 \\ 2 \end{matrix}) or (\begin{matrix}1 \\ 1 \\ 3 \end{matrix})

replace it by

(\begin{matrix}1 \\ 1 \\ − \end{matrix}) ,

and cross off the 1’s in the first 2 rows. Similarly, replace

(\begin{matrix}2 \\ 1 \\ 2 \end{matrix}) or (\begin{matrix}2 \\ 3 \\ 2 \end{matrix}) by (\begin{matrix}2 \\ − \\ 2 \end{matrix}) ,

and replace

(\begin{matrix}1 \\ 3 \\ 3 \end{matrix}) or (\begin{matrix}2 \\ 3 \\ 3 \end{matrix}) by (\begin{matrix}− \\ 3 \\ 3 \end{matrix}) .

Keep any (\begin{matrix}1 \\ 3 \\ 2 \end{matrix}) or (\begin{matrix}2 \\ 1 \\ 3 \end{matrix}) .

For example if a = 3, b = 4, c = 3, k = 1 and our three words are

w_{1} = 1 2 1 2 2 1 1
w_{2} = 1 3 3 1 3 3
w_{3} = 3 2 2 2 3 2 2

the bijection gives the word in the 5 symbols

(\begin{matrix}1 \\ 1 \\ − \end{matrix}) (\begin{matrix}− \\ 3 \\ 3 \end{matrix}) (\begin{matrix}2 \\ − \\ 2 \end{matrix}) (\begin{matrix}1 \\ 3 \\ 2 \end{matrix}) (\begin{matrix}2 \\ − \\ 2 \end{matrix}) (\begin{matrix}2 \\ 1 \\ 3 \end{matrix}) (\begin{matrix}1 \\ 3 \\ 2 \end{matrix}) (\begin{matrix}1 \\ 3 \\ 2 \end{matrix}) .

To find out what n is we just solve the equations

e_{1} + e_{2} = a + k, e_{1} + e_{4} = a − k, e_{3} + e_{4} = b − k, e_{2} + e_{5} = c + k,
e_{2} + e_{3} = b + k, e_{4} + e_{5} = c − k,

to obtain

e_{1} = a − n, e_{2} = n + k, e_{3} = b − n, e_{4} = n − k, e_{5} = c − n, for some n.

Our alphabet on the 5 symbols respects inversion, except for (\begin{matrix}2 \\ 1 \\ 3 \end{matrix}) (\begin{matrix}1 \\ 3 \\ 2 \end{matrix}) , which has

2 inversions instead of 1, thus we must multiply by q^{e_{2}e_{4}} = q^{n^{2}−k^{2}}. □

Exercise 12. Show that the major index, maj(w) defined by

maj(w) = ∑_{w_{i}>w_{i+1}} i

also satisfies

∑_{all w with m 1′s,N−m 0′s} q^{maj(w)} = [\begin{matrix}N \\ m \end{matrix}]_{q} .

Is there a q-multinomial version?

Exercise 13. Give at least two combinatorial proofs (partitions, inv, maj, or finite fields) that

∑_{k=0}^{C} [\begin{matrix}A \\ k \end{matrix}]_{q} [\begin{matrix}B \\ C − k \end{matrix}]_{q} q^{k(B−C+k)} = [\begin{matrix}A + B \\ C \end{matrix}]_{q} .

2. Orthogonal polynomials

The classical orthogonal polynomials may be interpreted combinatorially using the exponential formula [9], [10], [11]. One may also give interpretations for general orthogonal polynomials. In this section we consider this general case.

2.1. General orthogonal polynomials and lattice paths. Monic orthogonal polynomials satisfy the 3-term recurrence relation

(2.1)  p_{n+1}(x) = (x − b_{n})p_{n}(x) − λ_{n}p_{n−1}(x)

with the initial values p_{−1}(x) = 0, p_{0}(x) = 1. Clearly (2.1) implies that p_{n}(x) is a polynomial in x, with coefficients which are polynomials in the coefficients b_{n} and λ_{n}. We give an interpretation for these polynomials using lattice paths in the plane.

Definition 2.1. A p-lattice path is a lattice path which starts at (0, 0), and has steps NN = (0, 2), N = (0, 1), and NE = (1, 1).

The weight of a p-lattice path, wt(P), is the product of the weights of the individual edges,

wt((k, j − 1) → (k, j + 1)) = −λ_{j},
wt((k, j) → (k, j + 1) = −b_{j},
wt((k, j) → (k + 1, j + 1) = x.

Definition 2.2. Let Path_{n} be the set of all p-lattice paths which end at y = n.

Proposition 2.3. The polynomials p_{n}(x) which satisfy (2.1) with the initial conditions p_{−1}(x) = 0 and p_{0}(x) = 1 are given by

p_{n}(x) = ∑_{P ∈Path_{n}} wt(P).

Even though this proposition is nearly tautological, it is useful. “The” measure dμ(x) for the polynomials p_{n}(x) may not be uniquely defined but the moments

μ_{n} = ∫_{−∞}^{∞} x^{n}dμ(x)

are, and are also given by a polynomial in b_{n} and λ_{n}. (We always assume that μ_{0} = 1.) The first few are

μ_{1} = b_{0}
μ_{2} = b_{0}^{2} + λ_{1}
μ_{3} = b_{0}^{3} + 2b_{0}λ_{1} + b_{1}λ_{1}
μ_{4} = b_{0}^{4} + 3b_{0}^{2}λ_{1} + 2b_{0}b_{1}λ_{1} + b_{1}^{2}λ_{1} + λ_{1}^{2} + λ_{1}λ_{2}.

Note that (somewhat unexpectedly) all of the coefficients in the moment monomials are non-negative. We shall give a set of lattice paths which are counted by these coefficients.

Definition 2.4. A Motzkin path is a lattice path which starts at (0,0), lies at or above the x-axis, ends on the x-axis, and has steps NE = (1, 1), E = (1, 0), and SE = (1, −1).

Definition 2.5. Let Motz_{n} be the set of all Motzkin paths from (0, 0) → (n, 0). The weight of a path is the product of the weights of the individual edges, where

wt((k, j) → (k + 1, j + 1)) = 1,
wt((k, j) → (k + 1, j) = b_{j},
wt((k, j) → (k + 1, j − 1) = λ_{j}.

Theorem 2.6 (Viennot [25]). The nth moment μ_{n} is the generating function for Motzkin paths from (0, 0) → (n, 0),

μ_{n} = ∑_{P ∈Motz_{n}} wt(P).

We do not give the proof of Viennot’s theorem here. It uses a sign-reversing involution to show that the combinatorial definition of μ_{n} given above, combined with the combinatorial interpretation of the polynomials p_{n}(x), does have the appropriate orthogonality relation.

The above proposition and theorem imply that integrals of polynomials (or formal power series) with respect to the the measure dμ(x) may be evaluated using arguments on lattice paths. To convince you that non-trivial computations can be done with this technique, the Askey-Wilson integral

\frac{(q; q)_{∞}}{2π} ∫_{0}^{π} \frac{(e^{2iθ}, e^{2iθ}; q)_{∞}}{(ae^{iθ}, ae^{−iθ}, be^{iθ}, be^{−iθ}, ce^{iθ}, ce^{−iθ}, de^{iθ}, de^{−iθ}; q)_{∞}} dθ

= \frac{(abcd; q)_{∞}}{(ab, ac, ad, bc, bd, cd; q)_{∞}}

can be evaluated combinatorially [16].

Here are some examples.

Example 2.7. If b_{n} = 0 and λ_{n} = 1, the polynomials p_{n}(x) = U_{n}(x/2) (the Chebyshev polynomials), and

μ_{n} = \begin{cases}0, & if n is odd, \\ C_{N}, & if n = 2N is even. \end{cases}

where C_{n} = \frac{1}{n+1} \binom{2n}{n} is the nth Catalan number.

Here since b_{n} = 0, the Motzkin paths have only NE and SE edges, each with weight one. So μ_{n} is the total number of such paths, it is well-known [22] that this is a Catalan number.

Example 2.8. If b_{n} = 0 and λ_{n} = n, the polynomials p_{n}(x) = H_{n}(x/\sqrt{2})/2^{n/2} (the Hermite polynomials), and

μ_{n} = \begin{cases}0, & if n is odd, \\ ∏_{i=1}^{N}(2i − 1), & if n = 2N is even. \end{cases}

Note that μ_{n} is the number of complete matchings m on n objects, which is the number of ways of matching all n points on the x-axis with ⌊n/2⌋ edges. Here is how to see this. Label the points 1, 2, ⋯, n. If the kth step of the Motzkin path is NE, then draw an edge emanating from k, to be connected to some point to the right. If the kth step of the Motzkin path is SE, then draw an edge ending at k, to be connected to some earlier point to the left. If the SE edge starts at y = j, the weight of the edge is λ_{j} = j. This corresponds to the j previous unconnected points, we have j choices for earlier points.

Example 2.9. If b_{n} = 2n + α and λ_{n} = n(n + α − 1), the polynomials p_{n}(x) = n!(−1)^{n}L_{n}^{α−1}(x) (the Laguerre polynomials), and

μ_{n} = α(α + 1) ⋯ (α + n − 1).

If α = 1, we have μ_{n} = n!, the number of permutations of length n. This can be seen by a combinatorial argument not unlike Example 2.8. Here, however, we can do more, by weighing certain choices while building the permutation by α instead of 1, what results are permutation statistics, in this case the number of cycles of a permutation (see [21]).

Example 2.10. If b_{n} = n + a and λ_{n} = an, the polynomials p_{n}(x) = C_{n}^{a}(x) (the Charlier polynomials), and

μ_{n} = ∑_{k=1}^{n} S(n, k)a^{k}.

This example is similar to Example 2.9. Instead of permutations being in 1-1 correspondence with the weighted Motzkin paths, set partitions are. The Stirling numbers of the second kind S(n, k) is the number of set partitions of {1, 2, ⋯, n} into k blocks.

Example 2.11. If b_{n} = 0 and λ_{n} = [n]_{q}, the polynomials p_{n}(x) = H_{n}(\frac{1}{2} \sqrt{1 − q}x|q)/(1 − q)^{n/2} (the continuous q-Hermite polynomials), and

μ_{n} = ∑_{complete matchings m on {1,2,··· ,n}} q^{cross(m)}.

Here cross(m) is the crossing number of a complete matching m. For example, if m = (13)(25)(46) and we imagine three arcs above the x-axis, these arcs cross twice, cross(m) = 2. In Example 2.8, the j choices now have weights 1, q, ⋯, q^{j−1}. If you connect to the rightmost available previous point, no crossing is produced, as one moves left along the available points, the number of crossings increases by one, thus the choices of 0, 1, ⋯ (j − 1) crossings.

2.2. Hankel determinants. Monic orthogonal polynomials can be defined in terms of the moments μ_{n},

(2.2)  p_{n}(x) = \begin{matrix}det & [\begin{matrix}μ_{0} & μ_{1} & ⋯ & μ_{n} \\ μ_{1} & μ_{1} & ⋯ & μ_{n+1} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ μ_{n−1} & μ_{n} & ⋯ & μ_{2n−1} \\ 1 & x & ⋯ & x^{n} \end{matrix}] \\ det & [\begin{matrix}μ_{0} & μ_{1} & ⋯ & μ_{n−1} \\ μ_{1} & μ_{1} & ⋯ & μ_{n} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ μ_{n−1} & μ_{n} & ⋯ & μ_{2n−2} \end{matrix}] \end{matrix}.

The coefficient of x^{p} in the numerator of (2.2) is a minor of the infinite Hankel matrix. Lattice paths give a combinatorial interpretation [25] for any minor.

Theorem 2.12. The Hankel minor consisting of rows {a_{1}, a_{2}, ⋯, a_{k}} and columns {b_{1}, b_{2}, ⋯, b_{k}} (in increasing order) is the generating function for k-tuples of nonlattice point intersecting Motzkin paths (P_{1}, ⋯, P_{k}) such that P_{i} : (−a_{i}, 0) → (b_{σ(i)}, 0) for some permutation σ. The sign of a tuple is given by

sign((P_{1}, ⋯, P_{k})) = sign(σ).

In this theorem if we take rows (0, 1, 2, ⋯, n − 1) and columns (0, 1, 2, ⋯, n − 1), there is a unique set of paths, and we find the classical fact

λ_{1}^{n−1}λ_{2}^{n−2} ⋯ λ_{n−1}^{1} = det [\begin{matrix}μ_{0} & μ_{1} & ⋯ & μ_{n−1} \\ μ_{1} & μ_{1} & ⋯ & μ_{n} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ μ_{n−1} & μ_{n} & ⋯ & μ_{2n−2} \end{matrix}] .

2.3. Continued fractions. The generating function for the moments

M(t) = ∑_{n=0}^{∞} μ_{n}t^{n}

is known to have a continued fraction representation

(2.3)  M(t) = \frac{1}{1 − b_{0}t − \frac{λ_{1}t^{2}}{1 − b_{1}t − \frac{λ_{2}t^{2}}{1 − b_{2}t − ⋯}}} .

Although some care must be taken to consider (2.3) as a complex function of t, as a formal power in t it converges, and we shall see why. This has a very nice combinatorial interpretation which is due to Flajolet [8].

Consider all possible Motzkin paths. Imagine chopping the paths at the line y = 1. What remains is a sequence of either (a) horizontal edges along y = 0, or (b) paths starting at y = 1, ending at y = 1, along with a precursor NE edge, and a successor SE edge. Since the weight a horizontal edge along the x-axis is b_{0}, and the NE-SE pair has weight λ_{1}, we have

(2.4)  M(t) = ∑_{k=0}^{∞}(b_{0}t + λ_{1}t^{2}M^{∗}(t))^{k},

where M^{∗}(t) is the generating function for all Motzkin paths whose weights (b_{n} and λ_{n}) have been replaced by (b_{n+1} and λ_{n+1}). Clearly (2.4) is

(2.5)  M(t) = \frac{1}{1 − b_{0}t − λ_{1}t^{2}M^{∗}(t)}.

Upon iterating (2.5) k times, and then eliminating all paths which go above the line y = k, we have the rational function approximation to the continued fraction,

(2.6)  M_{k}(t) = \frac{1}{1 − b_{0}t − \frac{λ_{1}t^{2}}{1 − b_{1}t − \frac{λ_{2}t^{2}}{\frac{... − λ_{k−1}t^{2}}{1 − b_{k−1}t − λ_{k}t^{2}}}}} .

Proposition 2.13. Let μ_{n}(k) be the generating function for Motzkin paths of length n which stay at or below y = k. Then the generating function

M_{k}(t) = ∑_{n=0}^{∞} μ_{n}(k)t^{n}

is the kth iterate of the continued fraction (2.3).

It is clear that as formal power series in t,

lim_{k→∞} M_{k}(t) = M(t).

Fix any n, then μ_{n}(k) = μ_{n} for k ≥ n.

3. Symmetric functions

In this section a quick introduction to symmetric functions is given. The standard reference with a wealth of information is [17].

A polynomial in n variables x_{1}, ⋯, x_{n} with complex coefficients which is invariant under all n! permutations may be considered as sum of monomials m_{λ}, for a partition λ, for example

4(x_{1}^{2}x_{2}^{1} + x_{1}^{2}x_{3}^{1} + x_{2}^{2}x_{1}^{1} + x_{2}^{2}x_{3}^{1} + x_{3}^{2}x_{1}^{1} + x_{3}^{2}x_{2}^{1}) − 7(x_{1}^{3} + x_{2}^{3} + x_{3}^{3}) = 4m_{21} − 7m_{3},

where

m_{21}(x_{1}, x_{2}, x_{3}) = x_{1}^{2}x_{2}^{1} + x_{1}^{2}x_{3}^{1} + x_{2}^{2}x_{1}^{1} + x_{2}^{2}x_{3}^{1} + x_{3}^{2}x_{1}^{1} + x_{3}^{2}x_{2}^{1}
m_{3}(x_{1}, x_{2}, x_{3}) = x_{1}^{3} + x_{2}^{3} + x_{3}^{3}.

The Schur function s_{λ}(x_{1}, ⋯, x_{n}) is a symmetric polynomial which may be defined as a quotient of generalized Vandermonde determinants

(3.1)  s_{λ}(x_{1}, ⋯, x_{n}) = \frac{det(x_{i}^{λ_{j}+n−j})_{1≤i,j≤n}}{det(x_{i}^{n−j})_{1≤i,j≤n}} .

Note that the denominator of (3.1) is the Vandermonde determinant

Δ(x⃗) = ∏_{1≤i<j≤n}(x_{i} − x_{j}),

and that a quotient of skew-symmetric functions must be symmetric. The Schur functions

{s_{λ} : λ is a partition of m, λ has at most n parts}

form a basis for the vector space of symmetric polynomials in x_{1}, ⋯, x_{n} of degree m. Special choices for λ give well-known symmetric functions,

s_{1^{k}}(x⃗) = e_{k}(x⃗), the elementary symmetric function of degree k,
s_{k}(x⃗) = h_{k}(x⃗), the homogeneous symmetric function of degree k.

For example

e_{2}(x_{1}, x_{2}, x_{3}) = x_{1}x_{2} + x_{1}x_{3} + x_{2}x_{3},
h_{2}(x_{1}, x_{2}, x_{3}) = x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{1}x_{2} + +x_{1}x_{3} + x_{2}x_{3} = m_{2} + m_{11}.

If we expand the Schur functions in terms of the monomial symmetric functions

(3.2)  s_{λ}(x⃗) = ∑_{μ} K_{λμ}m_{μ}(x⃗)

the coefficients K_{λμ} are called Kostka coefficients. These have the algebraic interpretation as the dimension of the weight space μ in an irreducible representation of GL_{n} that corresponds to λ. Thus they are non-negative integers.

There is also a combinatorial interpretation of K_{λμ}. It is the number of column strict tableaux of shape λ and content μ. Take a Ferrers diagram of shape λ, and fill the cells with μ_{1} 1’s, μ_{2} 2’s,..., so that the entries in each row weakly increase and those in each column strictly increase. Here is a column strict tableau of shape λ = 421 and content μ = 2221.

1 1 2 4 2 3 3

Equation (3.1) is a special case of the Weyl denominator formula for the characters of the general linear group, thus there are analogues of Schur functions and Kostka coefficients for other classical groups.

The characters of the symmetric group S_{n} may also be found using Schur functions. It is not surprising that such a formula should exist, since the complex irreducible representations of S_{n} are in 1-1 correspondence with the conjugacy classes of S_{n}, which are the cycle types, thus partitions of n.

This time we expand the Schur functions in terms of the power sum symmetric functions,

p_{λ} = p_{λ_{1}}p_{λ_{2}} ⋯ p_{λ_{m}},

where

p_{k} = x_{1}^{k} + x_{2}^{k} + ⋯ + x_{n}^{k}.

For example p_{21}(x_{1}, x_{2}, x_{3}) = (x_{1}^{2} + x_{2}^{2} + x_{3}^{2})(x_{1} + x_{2} + x_{3}). We have

(3.3)  s_{λ}(x⃗) = \frac{1}{n!} ∑_{μ} c_{μ}χ^{λ}(μ)p_{μ}(x⃗).

where c_{μ} is the the size of the conjugacy class of permutations with cycle type μ,

c_{μ} = \frac{n!}{∏_{k} k^{m_{k}}m_{k}!}, μ = 1^{m_{1}}2^{m_{2}} ⋯,

and χ^{λ}(μ) is the irreducible character χ^{λ} evaluated at the conjugacy class μ. One example of (3.3) is

s_{21} = m_{21} + 2m_{111} = \frac{1}{6}(−2p_{3} + 2p_{111}),

which gives the χ^{21} row of the character table for S_{3}. Recall that as functions on the symmetric group the characters form an orthonormal basis for the functions constant on conjugacy classes.

3.1. Combinatorial applications. Here I will give two applications of Schur functions to plane partitions (see [17]).

The hook-content formula evaluates the principle specialization of a Schur function

s_{λ}(1, q, ⋯, q^{n−1}) = q^{n(λ)} ∏_{cells x∈λ} \frac{1 − q^{n+c(x)}}{1 − q^{h(x)}} .

The hook numbers h(x) can be defined by h(x) = λ_{i} − i + λ′_{j} − j + 1 if x = (i, j). Pictorially h(x) is the number of cells in the same row or column as x, to the right or below, including x. Here are the hook numbers of each cell for λ = 421.

6 4 2 1 3 1 1

The content numbers c(x) are defined by c(x) = j − i if x = (i, j). Here they are for λ = 421.

\begin{matrix}0 & 1 & 2 & 3 \\ −1 & 0 \\ −2 \end{matrix}

The constant n(λ) = ∑_{i}(i − 1)λ_{i}. The hook-content formula implies

h_{k}(1, q, ⋯, q^{n−1}) = [\begin{matrix}n + k − 1 \\ k \end{matrix}]_{q} , e_{k}(1, q, ⋯, q^{n−1}) = [\begin{matrix}n \\ k \end{matrix}]_{q} q^{\binom{k}{2}},

thus the principally specialized Schur function may be considered as a generalization of the q-binomial coefficient. In fact s_{λ}(1, q, ⋯, q^{n−1}) is also a symmetric unimodal [17] polynomial in q.

One may also use the hook-content formula to derive the generating function for all plane partitions

∑_{n=0}^{∞} pp(n)q^{n} = ∏_{k=1}^{∞}(1 − q^{k})^{−k},

and the Macmahon Box Theorem which gives the generating function for all plane partitions which lie inside an m × n × p box

∑_{P inside m×n×p box} q^{size(P)} = ∏_{1≤i≤m} ∏_{1≤j≤n} ∏_{1≤k≤p} \frac{1 − q^{i+j+k−1}}{1 − q^{i+j+k−2}} .

An example of a plane partition which lies inside a 5 × 3 × 4 box is

P = 4 4 3 4 2 3 2 1 1.

Here the entries of P lie inside a 5 × 3 rectangle, and the largest entry is at most 4.

3.2. The Jacobi-Trudi identity. A very useful result, which also has a representation interpretation, is the Jacobi-Trudi identity which gives a Schur function as a single determinant

s_{λ}(x⃗) = det(h_{λ_{i}−i+j}(x⃗))_{1≤i,j≤m},

for example

s_{421} = |\begin{matrix}h_{4} & h_{5} & h_{6} \\ h_{1} & h_{2} & h_{3} \\ 0 & h_{0} & h_{1} \end{matrix}| .

This may also be proven using a “tail-swapping” argument [15] to get nonintersecting lattice paths which correspond to column strict tableaux. This argument is very similar to the involution proofs necessary in Section 2. Moreover realizing plane partitions and column strict tableaux as non-intersecting lattice paths has been a fruitful idea for the study of symmetry classes of plane partitions [6].

3.3. Alternating sign matrices. An n×n alternating sign matrix is a 0, 1, −1 matrix whose row and column sums are 1, and whose non-zero entries alternate in sign in every row and column. One example is

(\begin{matrix}0 & 1 & 0 & 0 \\ 1 & −1 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{matrix}) .

Permutation matrices are examples of alternating sign matrices. Thus alternating sign matrices (ASM) may be considered as generalizations of permutations. A theorem of Zeilberger (see [6] for the whole story) gives the number of n × n alternating sign matrices as

(3.4)  ASM(n) = ∏_{i=0}^{n−1} \frac{(3i + 1)!}{(n + i)!}.

As of today there is no elementary proof of this result! Perhaps even more surprising is that (3.4) also counts the number of totally symmetric self-complementary plane partitions (TSSCPP) which lie inside a 2n × 2n × 2n box. It is an open problem to find a bijection between ASM and TSSCPP, which would allow one to carry over many of the properties of ASM to TSSCPP.

It is remarkable that a generalized determinant, called the λ-determinant [6] may be defined as a sum over alternating sign matrices instead of a sum over permutations. The individual terms are Laurent monomials in the entries of the matrix,

det_{λ}(M) = ∑_{A∈ASM(n)} λ^{inv(A)}(1 + λ^{−1})^{#−1′s in (A)} ∏_{i,j} M_{ij}^{A_{ij}}.

Clearly det_{−1}(M) = det(M).

3.4. The Borwein conjecture. A final elementary open problem is the Borwein conjecture [2, 5]. Let

∏_{i=1}^{n}(1 − q^{3i−2})(1 − q^{3i−1}) = A_{n}(q^{3}) − qB_{n}(q^{3}) − q^{2}C_{n}(q^{3}).

It is conjectured that the coefficients of the polynomials A_{n}, B_{n}, and C_{n} are nonnegative. (For n = ∞ it is easy to prove from the Jacobi triple product identity (1.13).) This problem is closely related to hook differences of partitions and statistical physics. Explicit forms for the polynomials may be found (again from the q-binomial theorem), for example

A_{n}(q) = ∑_{k=−n/3}^{n/3}(−1)^{k}q^{k(9k+1)/2} [\begin{matrix}2n \\ n + 3k \end{matrix}]_{q}

and A_{n}(1) = 2 × 3^{n−1}. Many possible sets of objects can be given which are counted by A_{n}(1), what is needed is an appropriate statistic. If the quadratic power of q were to change from k(9k + 1)/2, such a program does work [4].

References

[1] G. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and Its Applications, Vol. 2 (G.-C. Rota ed.), Addison-Wesley, Reading, Mass., 1976 (reissued by Cambridge Univ. Press, London and New York, 1985).

[2] , On a conjecture of Peter Borwein, J. Symbolic Computation 20 (1995), 487–501.

[3] , On the proofs of the Rogers-Ramanujan identities, in ‘q-Series and Partitions’, IMA Vol. Math. 18, Springer, New York, 1989, pp. 1–14.

[4] G. Andrews, R. Baxter, D. Bressoud, W. Burge, P. Forrester, G. Viennot, Partitions with prescribed hook differences, Eur. J. Comb. 8 (1987), 341–350.

[5] D. Bressoud, The Borwein conjecture and partitions with prescribed hook differences, Elec. J. Comb. 3 (1996), 14 pp.

[6] , Proofs and confirmations. The story of the alternating sign matrix conjecture, Cambridge University Press, Cambridge, 1999.

[7] T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, New York, 1978.

[8] P. Flajolet, Combinatorial aspects of continued fractions, Disc. Math. 32 (1980), 125–161.

[9] D. Foata, A combinatorial proof of the Mehler formula, J. Comb. A 24 (1978), 367–376.

[10] D. Foata and P. Leroux, Polynômes de Jacobi, interpretation combinatoire et fonction génératrice, Proc. Amer. Math. Soc. 87 (1983), 47–53.

[11] D. Foata and V. Strehl, Combinatorics of Laguerre polynomials, in ‘Enumeration and Design’, Academic Press, Toronto, 1984, pp. 123–140.

[12] A. Garsia and S. Milne, Method for constructing bijections for classical partition identities, Proc. Nat. Acad. Sci. U.S.A. 78 (1981), 2026–2028.

[13] F. Garvan, D. Kim, and D. Stanton, Cranks and t-cores, Inv. Math. 101 (1990), 1–17.

[14] G. Gasper and M. Rahman, Basic Hypergeometric Series, Cambridge University Press, Cambridge, 1990.

[15] I. Gessel and G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), 300–321.

[16] M. Ismail, D. Stanton, and G. Viennot, The combinatorics of the q-Hermite polynomials and the Askey-Wilson integral, Eur. J. Comb. 8 (1987), 379–392.

[17] I. G. Macdonald, Symmetric functions and Hall polynomials, Oxford University Press, Oxford, [18] , Affine root systems and Dedekind’s η-function, Inv. Math. 15 (1972), 91–143.

[19] K. O’Hara, Unimodality of Gaussian coefficients: a constructive proof, J. Comb. A 53 (1990), 29–52.

[20] I. Schur, Ein Beitrag zur additiven Zahlentheorie und zur Theorie der Kettenbrüche, reprinted in ‘I. Schur, Gesammelte Abhandlungen’, volume 2, Springer, Berlin, 1973, pp. 117–136.

[21] R. Simion and D. Stanton, Octabasic Laguerre polynomials and permutation statistics, J. Comput. Appl. Math. 68 (1996), 297–329.

[22] R. Stanley, Enumerative Combinatorics, Wadsworth, Monterey, 1986.

[23] , Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Alg. Disc. Methods 1 (1980), 168–183.

[24] D. Stanton, Gaussian integrals and the Rogers-Ramanujan identities, in ‘ Symbolic computation, number theory, special functions, physics, and combinatorics’ (F. Garvan and M. Ismail, eds.), Kluwer, Dordrecht, 2001, pp. 255–266.

[25] G. Viennot, Une Théorie Combinatoire des Polynômes Orthogonaux Généraux, Lecture Notes, University of Quebec at Montreal, 1983.

[26] D. Zeilberger, A one-line high school algebra proof of the unimodality of the Gaussian polynomials

[\begin{matrix}n \\ k \end{matrix}] for k < 20, in ‘q-Series and Partitions’, IMA Vol. Math. 18, Springer, New York, 1989,

pp. 67–72.

[27] , A q-Foata proof of the q-Saalschütz identity, Eur. J. Comb. 8 (1987), 461–463.

[28] , Proof of the alternating sign matrix conjecture, Elec. J. Comb. 3 (1996), 1–84.

[29] D. Zeilberger and D. Bressoud, A proof of Andrews’ q-Dyson conjecture, Disc. Math. 54 (1985), 201–224.

School of Mathematics, University of Minnesota, Minneapolis, Minnesota 55455, U.S.A.

  E-mail address: stanton@math.umn.edu