THE MAJOR COUNTING OF NONINTERSECTING LATTICE PATHS AND GENERATING FUNCTIONS FOR TABLEAUX

Summary

(The full-length article will appear in Mem. Amer. Math. Soc.)

C. Krattenthaler Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria. e-mail: KRATT@PAP.UNIVIE.AC.AT

Abstract

A theory of counting nonintersecting lattice paths by the major index and generalizations of it is developed. We obtain determinantal expressions for the corresponding generating functions for families of nonintersecting lattice paths with given starting points and given final points, where the starting points lie on a line parallel to x + y = 0. In some cases these determinants can be evaluated to result into simple products. As applications we compute the generating function for tableaux with p odd rows, with at most c columns, and with parts between 1 and n. Besides, we compute the generating function for the same kind of tableaux which in addition have only odd parts. We thus also obtain a closed form for the generating function for symmetric plane partitions with at most n rows, with parts between 1 and c, and with p odd entries on the main diagonal. In each case the result is a simple product. By summing with respect to p we provide new proofs of the Bender–Knuth and MacMahon (ex-)Conjectures, which were first proved by Andrews, Gordon, and Macdonald. The link between nonintersecting lattice paths and tableaux is given by variations of the Knuth correspondence.

Summary of results and sketch of proofs

We announce the proof of the following refinements of the MacMahon (ex-)Conjecture and the Bender–Knuth (ex-)Conjecture. (All the definitions can be found in the Appendix.)

Theorem 1 (Refinement of the MacMahon (ex-)Conjecture) The generating function for tableaux with p odd rows (i.e. exactly p rows have odd length), with at most c columns, and with only odd parts which lie between 1 and 2n − 1, is given by

q^{p^{2}} \frac{[2r + 2p]_{q^{2}} [r]_{q^{2}}}{[2r + p]_{q^{2}} [r + p]_{q^{2}}} [ \begin{matrix}n \\ p \end{matrix} ]_{q^{2}} \begin{matrix}[ \begin{matrix}n + 2r \\ n \end{matrix} ] & q^{2} \\ [ \begin{matrix}n + 2r + p \\ n \end{matrix} ] & q^{2} \end{matrix}

× ∏_{i=1}^{n} \frac{[r + i]_{q^{2}}}{[i]_{q^{2}}} ∏_{1≤i<j≤n} \frac{[2r + i + j]_{q^{2}}}{[i + j]_{q^{2}}}  if c = 2r  (1.a)

and

q^{p^{2}} [ \begin{matrix}n \\ p \end{matrix} ]_{q^{2}} ∏_{i=1}^{n} \frac{[r + i]_{q^{2}}}{[i]_{q^{2}}} ∏_{1≤i<j≤n} \frac{[2r + i + j]_{q^{2}}}{[i + j]_{q^{2}}}  if c = 2r + 1.  (1.b)

An equivalent formulation is: The generating function for symmetric plane partitions with at most n rows, with parts between 1 and c, and with exactly p odd entries on the main diagonal, is given by the expressions in (1.a) respectively (1.b).

The formulation of this result in terms of Schur functions is that the sum ∑ s_{λ}(q^{2n−1}, q^{2n−3}, …, q), where the sum is over all partitions λ with exactly p odd parts, and where all the parts do not exceed c, is given by the expressions in (1.a) respectively (1.b).

Theorem 2 (Refinement of the Bender–Knuth (ex-)Conjecture) The generating function for tableaux with p odd rows, with at most c columns, and with parts between 1 and n is given by

q^{\binom{p+1}{2}} \frac{[2r]}{[2r + p]} [ \begin{matrix}n \\ p \end{matrix} ] \begin{matrix}[ & \begin{matrix}n + 2r \\ n \end{matrix} & ] \\ [ & \begin{matrix}n + 2r + p \\ n \end{matrix} & ] \end{matrix} ∏_{1≤i≤j≤n} \frac{[2r + i + j]}{[i + j]}  if c = 2r  (2.a)

and

q^{\binom{p+1}{2}} [ \begin{matrix}n \\ p \end{matrix} ] ∏_{1≤i≤j≤n} \frac{[2r + i + j]}{[i + j]}  if c = 2r + 1.  (2.b)

In terms of Schur functions: The sum ∑ s_{λ}(q^{n}, q^{n−1}, …, q), where the sum is over all partitions λ with p odd parts, where each part does not exceed c, equals the expressions (2.a) respectively (2.b).

In fact, by summing these expressions with respect to p we obtain new proofs of the MacMahon and Bender–Knuth (ex-)Conjectures itself.

Theorem 3 (MacMahon (ex-)Conjecture) The generating function for symmetric plane partitions with at most n rows and with parts between 1 and c is equal to

∏_{i=1}^{n} \frac{[c + 2i − 1]_{q}}{[2i − 1]_{q}} ∏_{1≤i<j≤n} \frac{[c + i + j − 1]_{q^{2}}}{[i + j − 1]_{q^{2}}} .  (3)

Equivalently, the generating function for tableaux with at most c columns and with only odd parts which lie between 1 and 2n − 1 is also given by (3).

Proof. The expressions (1.a) are summed by a special case of the very well-poised 6ϕ_{5}-summation (see [10, Appendix (II.21)]), the expressions (1.b) are summed by the q-binomial theorem (see e.g. [1, (3.3.7)]).

Theorem 4 (Bender–Knuth (ex-)Conjecture) The generating function for tableaux with at most c columns and with parts between 1 and n equals

∏_{1≤i≤j≤n} \frac{[c + i + j − 1]}{[i + j − 1]} .  (4)

Proof. The expressions (2.a) are summed by the q-Kummer summation (see [10, Appendix (II.9)]), the expressions (2.b) are summed by the q-binomial theorem (see e.g. [1, (3.3.7)]).

Remarks. Theorem 3 was conjectured by MacMahon [17, p. 270] and only much later proved independently by Andrews [2], Macdonald [18, Ex. 16 and 17, pp. 51/52], and Proctor [19, Proposition 7.3]. Theorem 4 was conjectured by Bender and Knuth [4, p. 50] and proved by Andrews [3], Gordon [13], Macdonald [18, Ex. 19, p. 53], and Proctor [19, Proposition 7.2]. The p = 0 cases of Theorems 1 and 2 were previously obtained by Désarménien [8, Théoréme 1.2], Proctor [20, Theorem 1, cases (CYH) and (CYI), respectively], and Stembridge [22, Corollary 4.3 (a,b)]. The c = 2r + 1 special cases of Theorems 1 and 2 have already been discovered by Désarménien [9, Théoréme 2].

In the sequel we give a brief outline of the proof of Theorems 1 and 2.

First Step. Bijectively we show that the generating functions in question are the same as certain generating functions for certain nonintersecting families of lattice paths. The ideas which are used in these bijections are the celebrated Knuth correspondences [15], one of Burge’s [5, p. 22] modifications of it, the geometric interpretations of Knuth’s and Burge’s correspondences due to Viennot [24] and Desainte-Catherine and Viennot [7] and a refinement of Choi and Gouyou–Beauchamps [6].

The first Proposition concerns Theorem 1 for even c.

Proposition 5 There is a bijection Δ_{1} between tableaux τ with p odd rows, with at most 2r columns, and with only odd parts which lie between 1 and 2n−1, and nonintersecting families P = (P_{1}, …, P_{r}) of lattice paths consisting only of double steps, P_{i} : (2i, −2i + 2) → (2n + 2i, 2n + 4 − 2i), i = 1, …, r − 1, P_{r} : (2r + 2p, −2r − 2p + 2) → (2n + 2r, 2n + 4 − 2r), which lie below x = y (being allowed to touch x = y), such that

n(τ) = maj Δ_{1}(τ) + p^{2}.

The next Proposition shows, that once we have proved the p = 0, c = 2r-case of Theorem 1, we have also proved the c = 2r + 1-case of Theorem 1.

Proposition 6 There is a bijection Δ_{2} between tableaux τ with p odd rows, with at most 2r + 1 columns, and with only odd parts which lie between 1 and 2n − 1, and pairs (τ_{e}, S), where τ_{e} is a tableaux with even rows, with at most 2r columns, and with only odd parts which lie between 1 and 2n−1, and where S is a p-subset of {1, 3, …, 2n−1}, such that

n(τ) = n(τ_{e}) + ∥S∥ if (τ_{e}, S) = Δ_{2}(τ),

where ∥S∥ denotes the sum of all elements of S.

What concerns the case of c being even in Theorem 2, we have the following.

Proposition 7 There is a bijection Δ_{3} between tableaux τ with p odd rows, with at most 2r columns, and with parts between 1 and n, and nonintersecting families P = (P_{1}, …, P_{r}) of lattice paths which lie below x = y (being allowed to touch x = y), P_{i} : (i, −i+1) → (n+i, n+2−i), i = 1, 2, …, r−1, P_{r} : (r+p, −r−p+1) → (n+r, n+2−r), such that

n(τ) = ymaj_{1;0}(Δ_{3}(τ)) + \binom{p + 1}{2}.

Also here, once we have proved the p = 0, c = 2r-case of Theorem 2, we have also proved the c = 2r + 1-case of Theorem 2, as the following Proposition shows.

Proposition 8 There is a bijection Δ_{4} between tableaux τ with p odd rows, with at most 2r + 1 columns, and with parts between 1 and n, and pairs (τ_{e}, S), where τ_{e} is a tableau with even rows, with at most 2r columns, and with parts between 1 and n, and where S is a p-subset of {1, 2, …, n}, such that

n(τ) = n(τ_{e}) + ∥S∥, if (τ_{e}, S) = Δ_{4}(τ).

where ∥S∥ denotes the sum of all elements of S.

Second Step. The preceding Propositions show that it is desirable to develop a theory of counting nonintersecting lattive paths by the strange major index. As a “warm-up” we prove a theorem about counting non-restricted nonintersecting lattice paths. This actually is not what we need in order to prove Theorems 1 and 2. But also this theorem has interesting consequences, which we will point out later.

Theorem 9 Let A_{i} = (A^{(i)} + D, −A^{(i)}) and E_{i} = (E_{1}^{(i)}, E_{2}^{(i)}), i = 1, 2, …, r, be lattice points in the integer lattice Z^{2} such that

A^{(1)} < A^{(2)} < ⋯ < A^{(r)} ,  (5.a)

and

E_{1}^{(1)} < E_{1}^{(2)} < ⋯ < E_{1}^{(r)} and E_{2}^{(1)} ≥ E_{2}^{(2)} ≥ ⋯ ≥ E_{2}^{(r)} .  (5.b)

If γ is an integer satisfying

D − E_{1}^{(1)} ≤ γ ≤ min_{1≤i≤r}(E_{2}^{(i)} + i − 1)

then the generating function ∑ q^{ymaj_{β;γ}(P)}, where the sum is over all nonintersecting families P = (P_{1}, …, P_{r}) of lattice paths, P_{i} : A_{i} → E_{i}, i = 1, 2, …, r, is equal to the expression

det_{1≤s,t≤r} (q^{s(A^{(s)}−A^{(t)})} ∑_{j≥0} q^{j(j+β+γ+A^{(t)}−s+1)} [ \begin{matrix}−β \\ j \end{matrix} ] [ \begin{matrix}β + E_{1}^{(s)} + E_{2}^{(s)} − D \\ E_{1}^{(s)} − A^{(t)} − D − j \end{matrix} ] ).  (6)

If the nonintersecting lattice paths are restricted by the line x = y we have the following.

Theorem 10 Let A_{i} = (A^{(i)} + D, −A^{(i)}) and E_{i} = (E_{1}^{(i)}, E_{2}^{(i)}), i = 1, 2, …, r, be lattice points in the integer lattice Z^{2} such that (5.a), (5.b), and

2A^{(i)} + D ≥ 0 and E_{1}^{(i)} ≥ E_{2}^{(i)}, i = 1, 2, …, r,

hold. Let γ be an integer which satisfies the inequalities

D − E_{1}^{(1)} ≤ γ ≤ min_{1≤i≤r}(E_{2}^{(i)} + i − 1), max_{1≤i≤r}(D − E_{2}^{(i)} − i) ≤ γ ≤ E_{1}^{(1)} − 1,
and  −A^{(1)} ≤ γ ≤ A^{(1)} + D.

The generating function ∑ q^{ymaj_{β;γ}(P)}, where the sum is over all nonintersecting families P = (P_{1}, …, P_{r}) of lattice paths which lie below the line x = y (being allowed to touch x = y), P_{i} : A_{i} → E_{i}, i = 1, 2, …, r, is equal to the expression

det_{1≤s,t≤r} (q^{s(A^{(s)}−A^{(t)})}( ∑_{j≥0} q^{j(j+β+γ+A^{(t)}−s+1)} [ \begin{matrix}−β \\ j \end{matrix} ] [ \begin{matrix}β + E_{1}^{(s)} + E_{2}^{(s)} − D \\ E_{1}^{(s)} − A^{(t)} − D − j \end{matrix} ]

−q^{s(2A^{(t)}+D+β+1)} ∑_{j≥0} q^{j(j+β+γ+A^{(t)}+s+1)} [ \begin{matrix}−β \\ j \end{matrix} ] [ \begin{matrix}β + E_{1}^{(s)} + E_{2}^{(s)} − D \\ E_{2}^{(s)} − A^{(t)} − D − j − 1 \end{matrix} ] )).

(7)

The preceding two theorems are proved in an (almost) purely combinatorial way. What we use are “strange major analogues” of the usual “interchanging procedure” for pairs of intersecting lattice paths (cf. [12, 11, 23]) and (for Theorem 10) a “strange major analogue” for the reflection principle.

What we need in order to finally prove Theorem 1 is Theorem 10 with β = 0, D = 1, A^{(i)} = i − 1, i = 1, …, r − 1, A^{(r)} = r + p − 1, E_{1}^{(i)} = n + i, E_{2}^{(i)} = n + 2 − i, and q replaced by q^{2}. Likewise, in order to prove Theorem 2 we need Theorem 10 with β = 1, γ = 0, D = 1, A^{(i)} = i − 1, i = 1, …, r − 1, A^{(r)} = r + p − 1, E_{1}^{(i)} = n + i, and E_{2}^{(i)} = n + 2 − i.

Third step. The expressions of Theorems 9 and 10 which we obtained for the strange major generating functions for nonrestricted respectively restricted nonintersecting lattice paths schematically are of the form

det (∑_{j≥0}⟨COMPLICATED⟩) .

We may use linearity of the determinant in the columns to get

det (∑_{j≥0}⟨COMPLICATED⟩) = ∑_{k_{1}≥0} ∑_{k_{2}≥0} ⋯ ∑_{k_{r}≥0} det(⟨COMPLICATED⟩).

We might hope that then we could evaluate the resulting determinants at the righthand side. Indeed, if the final points of the paths are separated by (1, −1)-steps, the determinants can be evaluated by means of the following determinant lemma.

Lemma 11 Let X_{1}, X_{2}, …, X_{r}, A_{2}, A_{3}, …, A_{r}, C be indeterminates. If p_{0}, p_{1}, …, p_{r−1} are Laurent polynomials with deg p_{j} ≤ j and p_{j}(C/X) = p_{j}(X) for j = 0, 1, …, r − 1, then

det_{1≤s,t≤r} ((A_{r} + X_{s}) ⋯ (A_{t+1} + X_{s})(A_{r} + C/X_{s}) ⋯ (A_{t+1} + C/X_{s}) · p_{t−1}(X_{s}))

= ∏_{1≤i<j≤r}(X_{i} − X_{j})(1 − C/X_{i}X_{j}) ∏_{i=1}^{r} A_{i}^{i−1} ∏_{i=1}^{r} p_{i−1}(−A_{i}) ,  (8)

with the convention that empty products (like (A_{r} + X_{t}) ⋯ (A_{s+1} + X_{t}) for s = r) are equal to 1. (The indeterminate A_{1}, which occurs at the right-hand side of (8), in fact is superflous since it occurs in the argument of a constant polynomial.) A Laurent polynomial is a series p(X) = ∑_{i=M}^{N} a_{i}x^{i}, M, N ∈ Z, a_{i} ∈ R. Provided a_{N} ≠ 0 the degree of p is defined by deg p := N.

This Lemma is proved by simple row and column operations. It is a far reaching generalization of the Vandermonde determinant, as might be guessed from the expression ∏_{1≤i<j≤r}(X_{i} − X_{j}) at the right-hand side of (8).

Using Lemma 11, from Theorems 9 respectively 10 we obtain the following two results.

Theorem 12 Let A_{i} = (A^{(i)} + D, −A^{(i)}) and E_{i} = (E_{1} + i, E_{2} − i), i = 1, 2, …, r, be lattice points in the integer lattice Z^{2} such that (5.a) holds.

If γ is an integer satisfying

D − E_{1} − 1 ≤ γ ≤ E_{2} − 1,

then the generating function ∑ q^{ymaj_{β;γ}(P)} where the sum is over all nonintersecting families P = (P_{1}, …, P_{r}) of lattice paths, P_{i} : A_{i} → E_{i}, i = 1, 2, …, r, is equal to the expression

∑_{k_{1},...,k_{r}≥0} ( ∏_{i=1}^{r} q^{k_{i}(k_{i}+β+γ+A^{(i)}−i+1)} [ \begin{matrix}−β \\ k_{i} \end{matrix} ]

×\frac{[β + E_{1} + E_{2} + i − D − 1]!}{[β + E_{2} + A^{(i)} + k_{i} − 1]! [E_{1} + r − D − A^{(i)} − k_{i}]!} ∏_{1≤i<j≤r}[A^{(j)} + k_{j} − A^{(i)} − k_{i}]) .

(9)

Theorem 13 Let A_{i} = (A^{(i)} + D, −A^{(i)}) and E_{i} = (E + i, E + 2 − i), i = 1, 2, …, r, be lattice points in the integer lattice Z^{2} such that (5.a) and

2A^{(i)} + D ≥ 0, i = 1, 2, …, r,

hold. If γ is an integer satisfying

D − E − 1 ≤ γ ≤ E and − A^{(1)} ≤ γ ≤ A^{(1)} + D,

then the generating function ∑ q^{ymaj_{β;γ}(P)} where the sum is over all nonintersecting families P = (P_{1}, …, P_{r}) of lattice paths which lie below the line x = y (being allowed to touch x = y), P_{i} : A_{i} → E_{i}, i = 1, 2, …, r, is equal to the expression

∑_{k_{1},...,k_{r}≥0} ∏_{i=1}^{r} q^{k_{i}(k_{i}+β+γ+A^{(i)}−i+1)} [ \begin{matrix}−β \\ k_{i} \end{matrix} ]

\frac{[β + 2E + 2i − D]!}{[E + r − A^{(i)} − k_{i} − D]! [β + E + r + 1 + A^{(i)} + k_{i}]!}

∏_{1≤i<j≤r}[A^{(j)} + k_{j} − A^{(i)} − k_{i}] ∏_{1≤i≤j≤r}[A^{(i)} + k_{i} + A^{(j)} + k_{j} + D + β + 1] . (10)

Setting β = 0, D = 1, A^{(i)} = i − 1, i = 1, …, r − 1, A^{(r)} = r + p − 1, E = n, and replacing q by q^{2} in Theorem 13, in view of Proposition 5, proves the c = 2r-case of Theorem 1. Because of Proposition 6 (see the remark before Proposition 6), thus also the c = 2r + 1-case is proved.

In order to finally prove Theorem 2, we need Theorem 13 with β = 1, γ = 0, D = 1, A^{(i)} = i − 1, i = 1, …, r − 1, A^{(r)} = r + p − 1, and E = n.

Fourth Step. If β = 1 and γ = (D − 1)/2, the following multifold basic hypergeometric summation enables us to evaluate the sum in Theorem 13.

Lemma 14 For r ≥ 1 there holds the summation formula

∑_{k_{1},...,k_{r}≥0} ∏_{i=1}^{r} (\frac{\sqrt{q}}{q^{i}A})^{k_{i}} ∏_{i=1}^{r} \frac{(m_{i}A)_{k_{i}}}{(qm_{i}/A)_{k_{i}}}

× ∏_{1≤i<j≤r} \frac{1 − \frac{m_{j}}{m_{i}} q^{k_{j}−k_{i}}}{1 − \frac{m_{j}}{m_{i}}} ∏_{1≤i≤j≤r} \frac{1 − m_{i}m_{j}q^{k_{i}+k_{j}}}{1 − m_{i}m_{j}}

= ∏_{1≤i<j≤r} \frac{1 − m_{i}m_{j}/q}{1 − m_{i}m_{j}} ∏_{i=1}^{r} \frac{(1 − m_{i}/\sqrt{q})(1 − m_{i}/A)}{(1 − m_{i}^{2})(1 − \sqrt{q}/q^{i}A)}  (11)

provided that there exist nonnegative integers n_{i} with n_{1} > n_{2} > ⋯ > n_{r} such that m_{i}A = q^{−n_{i}} for all i = 1, 2, …, r.

This summation is a special case of Gustafson’s C_{r} _{6}ψ_{6} summation (or in the old notation: Sp(r) _{6}ψ_{6} summation) [14, Theorem 5.1]. The derivation of (11) from Gustafson’s C_{r} _{6}ψ_{6} sum can be found in [16].

Using this summation we finally obtain.

Theorem 15 Provided the assumptions of Theorem 13 hold, the generating function ∑ q^{ymaj_{1;(D−1)/2}(P)} where the sum is over all nonintersecting families P = (P_{1}, …, P_{r}) of lattice paths which lie below the line x = y (being allowed to touch x = y), P_{i} : A_{i} → E_{i}, i = 1, 2, …, r, is equal to the expression

∏_{i=1}^{r} \frac{[2E + 2i − D + 1]!}{[E + r − A^{(i)} − D]! [E + r + 1 + A^{(i)}]!} ∏_{1≤i<j≤r}[A^{(j)} − A^{(i)}]

× ∏_{1≤i<j≤r}[A^{(i)} + A^{(j)} + D + 1] ∏_{i=1}^{r} \frac{[A^{(i)} + (D + 1)/2]}{[E + i − (D − 1)/2]} .  (12)

The proof of Theorem 2 can now be completed. For the c = 2r-case, in Theorem 15 set D = 1, A^{(i)} = i − 1, i = 1, …, r − 1, A^{(r)} = r + p − 1, E = n, and combine with Proposition 7. Again, because of Proposition 8 (see the remark before Proposition 8), thus also the c = 2r + 1-case is proved.

Finally we come to the promised consequences of Theorems 9 and 12. First we can prove the following two identities about the summation of squares of Schur functions.

Theorem 16 There hold

∑_{λ,λ_{1}≤r} s_{λ}^{2}(q^{n}, q^{n−1}, …, q)

= ∑_{k_{1},...,k_{r}≥0} ∏_{i=1}^{r}(−1)^{k_{i}}q^{\binom{k_{i}+1}{2}} \frac{[2n + i]!}{[n + i + k_{i}]! [n + r − i − k_{i}]!} ∏_{1≤i<j≤r}[j + k_{j} − i − k_{i}](13)

and

∑_{λ,λ_{1}≤r} s_{λ}^{2}(q^{2n−1}, q^{2n−3}, …, q) = ∏_{1≤i,j≤n} \frac{[r + i + j − 1]_{q^{2}}}{[i + j − 1]_{q^{2}}} .  (14)

Secondly, we implicitely proved a new A_{r} q-Gauß summation.

Theorem 17 There holds

∑_{k_{1},...,k_{r}≥0} (∏_{i=1}^{r} q^{k_{i}(1−i)} (\frac{C}{AB} )^{k_{i}} \frac{(A)_{k_{i}} (BX_{i})_{k_{i}}}{(q)_{k_{i}} (CX_{i})_{k_{i}}} ) ∏_{1≤i<j≤r} \frac{1 − \frac{X_{j}}{X_{i}} q^{k_{j}−k_{i}}}{1 − \frac{X_{j}}{X_{i}}}

= ∏_{i=1}^{r} \frac{(\frac{C}{B} q^{i−r})_{∞} (\frac{C}{A}X_{i})_{∞}}{(CX_{i})_{∞} (\frac{C}{AB} q^{i−r})_{∞}} ,  (15)

provided that none of the denominators vanish, |q| < 1, and |C/AB| < |q^{r−1}|.

Appendix: Definitions

An r-tuple λ = (λ_{1}, …, λ_{r}) of nonnegative integers satisfying λ_{1} ≥ λ_{2} ≥ … ≥ λ_{r} is called a partition. The components λ_{i} are called parts of the partition. Let λ be a partition. A tableau τ of shape λ is an array

\begin{matrix}τ_{11} & τ_{12} & . . . . . . . . . . . . . & τ_{1λ_{1}} \\ τ_{21} & τ_{22} & . . . . . . . . & τ_{2λ_{2}} \\ ⋮ & . . . . . . . . & ... \\ τ_{r1} & … & τ_{rλ_{r}} \end{matrix}  (A.1)

of positive integers τ_{ij}, 1 ≤ i ≤ r, 1 ≤ j ≤ λ_{i}, such that the rows are weakly and the columns are strictly increasing. The entries of τ are called parts of the tableau. The sum of all the parts of a tableau τ is called the norm, in symbols n(τ), of the tableau. Given a set T of tableaux, the norm generating function for T is defined to be ∑_{τ∈T} q^{n(τ)}. If we speak of the generating function for some set of tableaux we always mean the norm generating function.

A plane partition of shape λ is an array τ of positive integers τ_{ij} of the form (A.1) such that the rows and the columns are weakly decreasing. The notions part, norm, generating function are used for plane partitions in the same sense as with tableaux. A plane partition is called symmetric, if it is symmetric with respect to the main diagonal.

The Schur function s_{λ}(x_{1}, x_{2}, …) = s_{λ}(x) is a symmetric function (cf. [18, 21]) in the variables x_{1}, x_{2}, … and is combinatorially defined by

s_{λ}(x) = ∑_{τ} ∏ x_{τ_{ij}} ,

where the sum is over all tableaux τ of shape λ and the product is over all parts τ_{ij} of τ. The vector x of variables can be finite or infinite.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • •^{P_{0}} Figure 1

In this paper we always consider lattice paths in the plane consisting of unit horizontal and vertical steps in the positive direction. We frequently call them shortly paths. A family of lattice paths is called intersecting if there are two paths in the family which have a point in common, if not the family is called nonintersecting.

Any path in a natural way corresponds to a multiset permutation consisting of 1’s and 2’s. Let P be a path from A = (A_{1}, A_{2}) to E = (E_{1}, E_{2}). We frequently abbreviate the fact that a path P goes from A to E by P : A → E. P may be represented by a pair (A, π), where A is the starting point of P and π = π_{1}π_{2} … π_{E_{1}+E_{2}−A_{1}−A_{2}}, where π_{i} = 1 if the i’th step in the path P is a horizontal one and π_{i} = 2 if the i’th step in the path P is a vertical one. π is a multiset permutation consisting of E_{1} − A_{1} entries of 1 and E_{2} − A_{2} entries of 2. For example, the path P_{0} in Figure 1 is represented by ((1, −1), 221221112122). Of course, this representation of paths is unique. Hence, we may identify each path with its representation.

The major index (or “greater index”) of a multiset permutation π = π_{1}π_{2} … π_{n}, π_{i} ∈ N (set of positive integers), is defined by

maj π = ∑_{i=1}^{n−1} i · χ(π_{i} > π_{i+1}) ,

where χ is the usual truth function, χ(A) = 1 if A is true, and χ(A) = 0 otherwise.

Given a path P = (A, π), we extend the major index to P by defining maj P := maj π. For our path in Figure 1 we have maj P_{0} = 2 + 5 + 9 = 16.

By definition each couple 21 that occurs in a multiset permutation π, and only these, makes a contribution to the major index of π. Given a path P = (A, π), the occurence of 21 in π means that a vertical step is followed by a horizontal one. The point which is the end point of this vertical step (and at the same time the starting point of this horizontal step) will be called a North-East corner of the path P. The North-East corners of our path in Figure 1 are (1, 1), (2, 3), and (5, 4). By the above consideration we see that only North-East corners of a path make a contribution to the major index. Besides, the contribution of the North-East corner (a, b) is the number of steps from the starting point of the path to (a, b), or in symbols a + b − A_{1} − A_{2} provided that the starting point is (A_{1}, A_{2}).

Finally we introduce the strange major index ymaj_{β;γ} of a path and of families of paths. Let β be some real number, γ be an integer, and P be a path from A = (A_{1}, A_{2}) to E = (E_{1}, E_{2}). We define ymaj_{β;γ} by

ymaj_{β;γ}(P) = \{ \begin{matrix}maj P + β · |\{(p_{1}, p_{2}) : (p_{1}, p_{2}) ∈ NE(P) and p_{2} > γ\}| & if γ ≥ A_{2} \\ maj P + β · |\{(p_{1}, p_{2}) : (p_{1}, p_{2}) ∈ NE(P) \\ and p_{1} ≥ A_{1} + A_{2} − γ\}| + β(A_{2} − γ) & if γ < A_{2} \end{matrix}

where NE(P) denotes the set of North-East corners of P. The idea is that every North-East corner which lies strictly above respectively to the right-hand side of a fixed horizontal respectively vertical line contributes an extra weight to the ordinary major index. Clearly, ymaj_{0;γ} is identically with the major index itself. For example for the path P_{0} in our example in Figure 1 we have ymaj_{β;2}(P_{0}) = 16+2β, ymaj_{β;3}(P_{0}) = 16+β, or ymaj_{β;−2}(P_{0}) = 16 + 2β + β = 16 + 3β.

The strange major index is extended to families P = (P_{1}, …, P_{r}), P_{i} : A_{i} → E_{i}, i = 1, 2, …, r, by

ymaj_{β;γ}(P) = ∑_{i=1}^{r} ymaj_{β;γ−i+1}(P_{i}).

Similarly, the major index of the family P is defined by maj P := ∑_{i=1}^{r} maj P_{i}. The q-notations which are used are [α]_{q} = 1 − q^{α}, [n]_{q}! = [1]_{q}[2]_{q} ⋯ [n]_{q}, [0]_{q}! = 1,

(a; q)_{k} = ∏_{j=0}^{k−1}(1 − aq^{j}) , and (a; q)_{0} = 1,
(a; q)_{∞} = ∏_{j=0}^{∞}(1 − aq^{j}) ,

so that in particular [n]_{q}! = (q; q)_{n}, and

[ \begin{matrix}n \\ k \end{matrix} ]_{q} = \{ \begin{matrix}\frac{[n]_{q} · [n − 1]_{q} ⋯ [n − k + 1]_{q}}{[k]_{q}!} & k ≥ 0 \\ 0 & k < 0 \end{matrix} .

The base q in [α]_{q}, [n]_{q}!, (a; q)_{k}, (a; q)_{∞}, and \left[{n \atop k}\right]_{q} in most cases is omitted. Only if the base is different from q it is explicitely stated.

References

[1] G. E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and its Applications, Vol. 2, Addison–Wesley, Reading, 1976.

[2] G. E. Andrews, Plane partitions I: The MacMahon conjecture, in: Studies in foudations and combinatorics, G.-C. Rota ed., Adv. in Math. Suppl. Studies, Vol. 1, 1978, 131–150.

[3] G. E. Andrews, Plane partitions II: The equivalence of the Bender–Knuth and MacMahon conjectures, Pacific J. Math. 72, (1977), 283–291.

[4] E. A. Bender, D. E. Knuth, Enumeration of plane partitions, J. Combin. Theory A 13, (1972), 40–54.

[5] W. H. Burge, Four correspondences between graphs and generalized Young tableaux, J. Combin. Theory A 17, (1974), 12–30.

[6] S. H. Choi, D. Gouyou–Beauchamps, Enumération de tableaux de Young semistandard, Theoret. Comput. Science, 117, (1993), 137–151.

[7] M. Desainte–Catherine, G. Viennot, Enumeration of certain Young tableaux with bounded height, in: Combinatoire énumérative, G. Labelle, P. Leroux, Eds., Springer–Verlag, Berlin, Heidelberg, New York, 1986, 58–67.

[8] J. Désarménien, La démonstration des identités de Gordon et MacMahon et de deux identités nouvelles, in: Actes de 15e Séminaire Lotharingien, I. R. M. A. Strasbourg, 1987, 39–49.

[9] J. Désarménien, Une généralisation des fomules de Gordon et de MacMahon, Comptes Rendus Acad. Sci. Paris, Série I 309, (1989), 269–272.

[10] G. Gasper, M. Rahman, Basic hypergeometric series, Encyclopedia of Mathematics And Its Applications 35, Cambridge University Press, Cambridge, 1990.

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

[12] I. M. Gessel, G. Viennot, Determinants, paths, and plane partitions, preprint, 1989.

[13] B. Gordon, A proof of the Bender–Knuth conjecture, Pacific J. Math. 108, (1983), 99–113.

[14] R. A. Gustafson, The Macdonald identities for affine root systems of classical type and hypergeometric series very-well-poised on semisimple Lie algebras, in: Ramanujan International Symposium on Analysis (Dec. 26th to 28th, 1987, Pune, India), N. K. Thakare, ed., 1989, 187–224.

[15] D. E. Knuth, Permutations, matrices, and generalized Young tableaux, Pacific J. Math. 34, (1970), 709–727.

[16] G. M. Lilly, S. C. Milne, The C_{l} Bailey transform and Bailey Lemma, to appear in Constructive Approximation.

[17] P. A. MacMahon, Combinatory Analysis, Vol. 2, (Cambridge University Press, Cambridge, 1916; reprinted by Chelsea, New York, 1960.

[18] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, New York/London, 1979.

[19] R. A. Proctor, Bruhat lattices, plane partitions generating functions, and minuscule representations , Europ. J. Combin. 5, (1984), 331–350.

[20] R. A. Proctor, New symmetric plane partition identities from invariant theory work of DeConcini and Procesi, Europ. J. Combin. 11, (1990), 289–300.

[21] R. P. Stanley, Theory and applications of plane partitions: Part 1,2, Stud. Appl. Math 50, (1971), 167–188, 259–279.

[22] J. Stembridge, Hall–Littlewood functions, plane partitions and the Rogers– Ramanujan identities, Trans. Amer. Math. Soc. 319, (1990), 469–498.

[23] J. Stembridge, Nonintersecting lattice paths, pfaffians and plane partitions, Adv. Math. 83, (1990), 96–131.

[24] G. Viennot, Une forme géométrique de la correspondance de Robinson–Schensted, in: Combinatoire et Représentation du Groupe Symétrique, D. Foata ed., Lecture Notes in Math. Vol. 579, Springer–Verlag, New York, 1977, 29–58.