Non-crossing two-rowed arrays and

summations for Schur functions

(Summary)

C. Krattenthaler

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

Abstract. In the first part of this paper (sections 1,2) we give combinatorial proofs for determinantal formulas for sums of Schur functions “in a strip” that were originally obtained by Gessel, respectively Goulden, using algebraic methods. The combinatorial analysis involves certain families of two-rowed arrays, asymmetric variations of Sagan and Stanley’s skew Knuthcorrespondence, and variations of one of Burge’s correspondences. In the third section we specialize the parameters in these determinants to compute norm generating functions for tableaux in a strip. In case we can get rid of the determinant we obtain multifold summations that are basic hypergeometric series for A_{r} and C_{r} respectively. In some cases these sums can be evaluated. Thus in particular, an alternative proof for refinements of the Bender-Knuth and MacMahon (ex-)Conjectures, which were first obtained in another paper by the author, is provided. Although there are some parallels with the original proof, perhaps this proof is easier accessible. Finally, in section 4, we record further applications of our methods to the enumeration of paths with respect to weighted turns.

1. Generating functions for non-crossing two-rowed arrays. We consider tworowed arrays P = (p | q) of the form

\begin{aligned}p_{−a} & p_{−a+1} & … & p_{−1} & p_{1} & … & p_{k} \\ & & & & q_{1} & … & q_{k} & q_{−1} & … & q_{−b+1} & q_{−b} \end{aligned} ,  (1.1)

where a, k, b are some nonnegative integers and where the entries p_{i}, q_{i} are positive integers such that both rows of the array are weakly increasing. (To be precise, if k = 0, i.e. the “middle part” of the array is empty, for a c ≤ min{a, b} we also allow the entries p_{−1}, …, p_{−c} and q_{−1}, …, q_{−c} to be “empty”.) We say that P is of the type (a, b) and of the shape (a, k, b). If both rows of P are strictly increasing then we call P a strict two-rowed array. Given an array P_{1} = (p^{(1)} | q^{(1)}) of the shape (a_{1}, k_{1}, b_{1}) and an array P_{2} = (p^{(2)} | q^{(2)}) of the shape (a_{2}, k_{2}, b_{2}), we say that P_{1} dominates (resp. strictly dominates) P_{2} if the following three conditions hold:

(D1) a_{1} ≤ a_{2} and p_{l}^{(1)} ≤ p_{l}^{(2)} (resp. p_{l}^{(1)} < p_{l}^{(2)}) for all l = −1, −2, …, − min{a_{1}, a_{2}}. (By convention, these inequalities are also violated if p_{l}^{(1)} should be an “empty” entry.)

1980 Mathematics Subject Classification (1991 Revision). Primary 05E05; Secondary 05A10, 05A15, 05A17, 05A30, 05E10, 33D20..

Key words and phrases. Tableaux, plane partitions, symmetric functions, Schur functions, generating functions, skew Knuth-correspondence, basic hypergeometric series in U(n) and Sp(n), basic hypergeometric series for A_{l} and C_{l}.

(D2) b_{1} ≤ b_{2} and q_{l}^{(1)} ≥ q_{l}^{(2)} (resp. q_{l}^{(1)} > q_{l}^{(2)}) for all l = −1, −2, …, − min{b_{1}, b_{2}}. (By

convention, these inequalities are also violated if q_{l}^{(1)} should be an “empty” entry.) (D3) For each m, 1 ≤ m ≤ k_{2}, there is an l, 1 ≤ l ≤ k_{1}, such that p_{l}^{(1)} ≤ p_{m}^{(2)} and

q_{l}^{(1)} ≥ q_{m}^{(2)} (resp. p_{l}^{(1)} < p_{m}^{(2)} and q_{l}^{(1)} > q_{m}^{(2)}). Let α = (α_{r}, α_{r−1}, …, α_{1}) and β = (β_{r}, β_{r−1}, …, β_{1}) be r-tupels of nonnegative integers. A family P = (P_{1}, …, P_{r}) of two-rowed arrays is called of the type (α, β) if P_{i} is of the type (α_{i}, β_{i}), i = 1, 2, …, r. P is called strict if all P_{i}, i = 1, …, r, are strict. The family P is called non-crossing (resp. strictly non-crossing) if P_{i} dominates (resp. strictly dominates) P_{i+1}, i = 1, …, r − 1.

Our objects of interest are non-crossing strict families of two-rowed arrays (see the example in section 2) and strictly non-crossing (ordinary) two-rowed arrays. If α and β are partitions, the most convenient way to look at a non-crossing strict family P = (P_{1}, …, P_{r}) = ((p^{(1)} | q^{(1)}), …, (p^{(r)} | q^{(r)})) of the type (α, β) is by rephrasing the three conditions (D1)– (D3) of dominance in terms of the following three properties:

(NS1) The front part, the array (p_{−i}^{(r−j+1)})_{i,j≥1} is a column-strict plane partition of shape

α′/ν. (NS2) The tail, the array (q_{−i}^{(r−j+1)})_{i,j≥1} is a tableau of shape β′/ν. ν is the same partition

as in (NS1). (NS3) The middle part of P, interpreted as multiset {(p_{j}^{(i)}, q_{j}^{(i)}) : 1 ≤ i ≤ r, 1 ≤ j ≤ k_{i}},

can be viewed as a family of r pairwise non-crossing lattice paths in ℤ^{2} consisting of unit horizontal and vertical steps in the positive direction, all of which starting at (0, 0) and ending with an infinite horizontal part. (Thus the final points of the paths might be considered to be of the form (∞, y_{i}), for some nonnegative integers y_{i}.) This is seen as follows: For fixed i consider the points (p_{j}^{(i)}, q_{j}^{(i)}), j = 1, …, k_{i}. Now to these points apply Viennot’s [31] light and shadow procedure (with the sun being located in the North-West). For each i this yields a lattice path of the described type. The condition (D3) (ordinary dominance) simply says that these r paths are pairwise non-crossing (from here we are lead to call the arrays under consideration “non-crossing”), the first path lying “avove” the second, the second “above” the third, etc.

A similar interpretation holds for strictly non-crossing (ordinary) families P = (P_{1}, …, P_{r}). This time the conditions (D1)–(D3) can be rephrased in the following way.

(SN1) The front part, the array (p_{−j}^{(r−i+1)})_{i,j≥1} is a column-strict plane partition of shape

α/ν. (ν is allowed to differ from 0 only if the middle part (see (SN3)) of P is empty.) (SN2) The tail, the array (q_{−j}^{(r−i+1)})_{i,j≥1} is a tableau of shape β/ν. ν is the same partition

as in (SN1). (ν is allowed to differ from 0 only if the middle part (see (SN3)) of P is empty.)

(SN3) The middle part of P, interpreted as multiset {(p_{j}^{(i)}, q_{j}^{(i)}) : 1 ≤ i ≤ r, 1 ≤ j ≤ k_{i}}, can be viewed as a family of r pairwise non-touching path-like objects, which were called pathoids by Kulkarni [21]. This is done in the same way as before. We omit the details.

Finally let x = (x_{1}, x_{2}, …) and y = (y_{1}, y_{2}, …) be two infinite sequences of indeterminates. We define the weight w_{x,y}(P) of an array P of the form (1.1) to be the product ∏ x_{ε} ∏ y_{η} where ε runs over all elements of the first row of P and η runs over all elements of the second row of P. The weight w_{x,y}(P) of a family P = (P_{1}, …, P_{r}) is defined to be the product over the weights of all arrays of P, ∏_{i=1}^{r} w_{x,y}(P_{i}).

Now we are in the position to formulate the main theorems of this section.

Theorem 1. Let α, β be partitions. The generating function ∑ w_{x,y}(P) for non-crossing strict families P of the type (α, β) is

det_{1≤s,t≤r}(f_{α_{s}+s−β_{t}−t}(x, y)),  (1.2)

where f_{m}(x, y) = ∑_{k} e_{k+m}(x)e_{k}(y) with e_{n}(z) being the elementary symmetric function of order n in the variables z_{1}, z_{2}, . . ..

The generating function ∑ w_{x,x}(P) for non-crossing strict families P of the type (α, β) with the additional property p_{j}^{(i)} ≥ q_{j}^{(i)}, i = 1, …, r and j = 1, …, k_{i}, is

det_{1≤s,t≤r}(f_{α_{s}+s−β_{t}−t}(x, x) − f_{α_{s}+s+β_{t}+t}(x, x)).  (1.3)

Theorem 2. Let α, β be partitions. The generating function ∑ w_{x,y}(P) for strictly non-crossing families P of the type (α, β) is

det_{1≤s,t≤r}(g_{α_{s}+s−β_{t}−t}(x, y)),  (1.4)

where g_{m}(x, y) = ∑_{k} h_{k+m}(x)h_{k}(y) with h_{n}(z) being the complete homogenous symmetric function of order n in the variables z_{1}, z_{2}, . . ..

The generating function ∑ w_{x,x}(P) for strictly non-crossing families P of the type (α, β) with the additional property p_{j}^{(i)} > q_{j}^{(i)}, i = 1, …, r and j = 1, …, k_{i}, is

det_{1≤s,t≤r}(g_{α_{s}+s−β_{t}−t}(x, x) − g_{α_{s}+s+β_{t}+t}(x, x)).  (1.5)

Sketch of Proof. We imitate the usual procedure with nonintersecting lattice paths ([12], see also [28, section 1]. For the proof of (1.2) we consider strict families P = (P_{1}, …, P_{r}) of two-rowed arrays where P_{i} is of the type (a_{σ(i)} + σ(i) − i, β_{i}), i = 1, 2, …, r, for some permutation σ ∈ 𝔖_{r}. As with nonintersecting lattice paths we set up a weightpreserving involution on the crossing families of two-rowed arrays (where “crossing” means a violation against one of the conditions (D1)–(D3)), such that the corresponding permutations differ only by a transposition. After having observed that for σ ≠ id there are no non-crossing strict families of the above type, the usual arguments lead to (1.2).

In order to prove (1.3) we consider strict families P = (P_{1}, …, P_{r}) of two-rowed arrays where P_{i} is of the type (η_{i}(α_{σ(i)} + σ(i)) − i, β_{i}), i = 1, 2, …, r, for some permutation σ ∈ 𝔖_{r} and η_{i} ∈ {−1, 1}, i = 1, …, r. Also here we give a weight-preserving involution on the crossing families (where “crossings of the main diagonal”, i.e. violations against p_{j}^{(i)} ≥ q_{j}^{(i)}, have to be considered, too) such that either the corresponding permutations differ by a transposition and the corresponding η_{i}’s are identical, or the corresponding permutations are identical and exactly one of the corresponding η_{i}’s changes its sign.

The proofs for (1.4) and (1.5) are similar. Only at all places the roles of weak and strict order have to be exchanged.

The bijections of this section are inspired by ideas from [18]. □

2. Summations for Schur functions “in a strip”. In this section we relate Theorems 1 and 2 to summations for Schur functions. In the following given a partition μ the symbol μ′ denotes the conjugate of μ, as usual. The number of odd parts of μ is denoted by oddrows(μ), the number of odd parts of μ′ is denoted by oddcolumns(μ). (This terminology stems from visualizing partitions as Ferrer’s boards.)

Theorem 3. Let α, β be partitions.

∑_{λ,λ_{1}≤r} s_{λ/β′}(x)s_{λ/α′}(y) = det_{1≤s,t≤r}(f_{α_{s}+s−β_{t}−t}(x, y))  (2.1)

∑_{λ,λ_{1}≤c,oddrows(λ)=p} s_{λ}(x) = \{ \begin{matrix}det_{1≤s,t≤r}(f_{p·χ(s=r)+s−t}(x, x) \\ −f_{p·χ(s=r)+s+t}(x, x)) & c = 2r \\ e_{p}(x) det_{1≤s,t≤r}(f_{s−t}(x, x) − f_{s+t}(x, x)) & c = 2r + 1 \end{matrix}

(2.2)

∑_{λ,ℓ(λ)≤r} s_{λ/β}(x)s_{λ/α}(y) = det_{1≤s,t≤r}(g_{α_{s}+s−β_{t}−t}(x, y))  (2.3)

∑_{λ,ℓ(λ)≤c,oddcolumns(λ)=p} s_{λ}(x) = \{ \begin{matrix}det_{1≤s,t≤r}(g_{p·χ(s=r)+s−t}(x, x) \\ −g_{p·χ(s=r)+s+t}(x, x)) & c = 2r \\ h_{p}(x) det_{1≤s,t≤r}(g_{s−t}(x, x) − g_{s+t}(x, x)) & c = 2r + 1 \end{matrix}

(2.4)

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

Remark. Identity (2.3) is due to Gessel [10, Theorem 16, cf. the paragraph just before Theorem 16], while (2.4) is due to Goulden [14, Theorems 2.4 and 2.6]. Clearly (2.1) and (2.2) follow from (2.3) and (2.4), respectively, by application of the homomorphism on symmetric functions that interchanges the roles of elementary and complete homogenous symmetric functions (cf. [23, pp. 14/15]). However, it is our goal to give combinatorial proofs for all of these identities.

Sketch of Proof. For a proof of (2.1) we set up a “part”-preserving bijection between non-crossing strict families P = (P_{1}, …, P_{r}) of the type (α, β) and pairs (π, τ) of a columnstrict plane partition π of shape λ/β′ and a tableaux τ of shape λ/α′, with λ being a partition with λ_{1} ≤ r. (Of course “part”-preserving means that the multiset of the elements in P_{1}, …, P_{r} is identically with the multiset of parts in π and τ.) This bijection is a variation of Sagan and Stanley’s [27] skew Knuth correspondence. In the explanation of the bijection we refer to the Fomin–Roby [26, section 4.1; 8] description of the skew Knuth correpondence.

The bijection is best explained with a running example. Consider the family P^{(0)} = (P_{1}^{(0)}, P_{2}^{(0)}, P_{3}^{(0)}) where

P_{1}^{(0)} = {1 3 \atop 3 5 6} , P_{2}^{(0)} = {2 4 5 \atop 1 2 3 5} , P_{3}^{(0)} = {1 2 4 5 \atop 2 3 4} .

It is a non-crossing strict family of the type (α^{(0)}, β^{(0)}) = ((3, 1, 0), (2, 2, 1)). Now, given a non-crossing strict family interpret the front part as column-strict plane partition π̃ of shape α′/ν and the tail as tableau τ̃ of shape β′/ν as explained in (NS1) and (NS2), respectively, where ν is some partition. In our example the front part π̃^{(0)} and the tail τ̃^{(0)} are as follows,

π̃^{(0)} = 4 2 2 1 and τ̃^{(0)} = 3 3 6 4 5 .

Next write π̃ and τ̃ as multichains in Young’s lattice, i.e. as sequences of partitions, the length of the sequences being determined by m + 1, where m is the largest element in P. For the tableau τ̃ this is standard (cf. [23, pp. 4/5; 26, pp. 12/13]), for the column-strict plane partition π̃ the i-th partition in the sequence, i running from 0 to m, corresponds to the shape of the column-strict plane partition that results from π̃ by deleting the numbers {1, 2, …, m − i} in π̃. So in our example the sequence for π̃^{(0)} is 0, 0, 0, 1, 1, 21, 211, while the sequence for τ̃^{(0)} is 0, 0, 0, 2, 21, 22, 32. (Here we use a short notation for partitions. For instance, 211 is short for (2, 1, 1), 0 is short for the empty partition.)

3^{3}2^{2}1  3^{2}2^{3} 3^{2}2^{2} 32^{3} 322 32 32 ^{3^{2}2^{3}1}  1  ^{22} ^{32^{3}1^{2}  21} ^{32^{3}1} 1  ^{2} ^{2^{3}1}  2  ^{0} ^{221}  1  ^{0} ^{211  21  1  1  0  0  0}  π^{(0)} = 3 5 5 1 4 4 2 2 1 , τ^{(0)} = 3 1 5 2 6 2 3 3 5 4 Figure 1

Now we are able to fill the appropriate Fomin–Roby picture. The lower border corresponds to π̃, the right border to τ̃, the (s, t)-entry in the matrix corresponds to the number of pairs (p_{j}^{(i)}, q_{j}^{(i)}) in the middle part of P that equal (s, t). The left-hand diagram in Figure 1 shows the Fomin–Roby picture corresponding to our running example. The subdivision of rows and columns that contain “multiple entries” is done in direction South-East, (and not in direction North-East as in [26, section 4.1]). Figure 1a contains the “subdivided” Fomin– Roby picture that corresponds to the diagram in Figure 1. Also, in the diagram we are working upwards and to the left (and not upwards and to the right as in [26, section 4.1]). The rules for the algorithm are the same as in [26, Example 2.6.3]. From the upper border, in the same way as explained above, we read a column-strict plane partition π of shape λ/β′, from the left border a tableau τ of shape λ/α′, where λ is some partition. Examining the properties of this mapping it is not too difficult to see that thus we indeed obtain a part-preserving bijection between non-crossing strict families P = (P_{1}, …, P_{r}) of the type (α, β) and pairs (π, τ) where π is a column-strict plane partition of shape λ/β′ and τ is a tableaux of shape λ/α′, with λ being a partition with λ_{1} ≤ r. The pair (π^{(0)}, τ^{(0)}) resulting from our example is exhibited in Figure 1.

It is well-known that the skew Schur function s_{λ/β′} can be either defined as generating function for tableaux of shape λ/β′ or as generating function for column-strict plane partitions of shape λ/β′. (There is also a bijection basing on jeu de taquin which settles this equivalence of definitions for the Schur function.) Thus the above bijection by (1.2) proves (2.1).

\begin{matrix}^{3^{3}2^{2}1} & ^{3^{2}2^{3}1} & ^{3^{2}2^{3}} & ^{3^{2}2^{2}1} & ^{3^{2}2^{2}} & ^{32^{3}} & ^{32^{2}1} & ^{32^{2}} & ^{321} & ^{32} & ^{32} \\ ^{3^{2}2^{3}1} & ^{32^{4}1} & ^{32^{4}} & ^{32^{3}1} & ×^{32^{3}} & ^{2^{4}} & ^{2^{3}1} & ^{2^{3}} & ^{2^{2}1} & ^{22} & ^{22} \\ ^{32^{4}1} & ^{2^{5}1} & ^{2^{5}} & ^{2^{4}1} & ^{2^{4}} & ^{2^{4}} & ^{2^{3}1} & ^{2^{3}} & ^{2^{2}1} & ^{22} & ^{22} \\ ^{32^{3}1^{2}} & ^{2^{4}1^{2}} & ^{2^{4}1} & ^{2^{3}1^{2}} & ^{2^{3}1} & ^{2^{3}1} & ^{2^{2}1^{2}} & ^{2^{2}1} & ^{21^{2}} & ^{21} & ^{21} \\ ×^{32^{3}1} & ^{2^{4}1} & ^{2^{4}} & ^{2^{3}1} & ^{2^{3}} & ^{2^{3}} & ^{2^{2}1} & ^{22} & ^{21} & ^{2} & ^{2} \\ ^{2^{4}1} & ^{2^{4}1} & ^{2^{4}} & ^{2^{3}1} & ^{2^{3}} & ^{2^{3}} & ^{2^{2}1} & ^{22} & ^{21} & ^{2} & ^{2} \\ ^{2^{3}1^{2}} & ^{2^{3}1^{2}} & ^{2^{3}1} & ^{2^{2}1^{2}} & ^{2^{2}1} & ^{2^{2}1} & ^{21^{2}} & ^{21} & ^{11} & ^{1} & ^{1} \\ ^{2^{3}1} & ^{2^{3}1} & ^{2^{3}} & ^{2^{2}1} & ^{22} & ^{22} & ^{21} & ^{2}× & ^{1} & ^{0} & ^{0} \\ ^{2^{2}1^{2}} & ^{2^{2}1^{2}} & ^{2^{2}1} & ^{21^{2}} & ^{21} & ^{21} & ^{11} & ^{1} & ^{1}× & ^{0} & ^{0} \\ ^{2^{2}1} & ^{2^{2}1} & ^{22} & ^{21} & ^{2} & ^{2}× & ^{1} & ^{0} & ^{0} & ^{0} & ^{0} \\ ^{211} & ^{211} & ^{21} & ^{11} & ^{1} & ^{1} & ^{1} & ^{0} & ^{0} & ^{0} & ^{0} \end{matrix} Figure 1a

For the c = 2r case of (2.2) we use a bijection due to Choi and Gouyou–Beauchamps [6, proof of Théorème 3] (cf. [18, Proposition 32] for a detailed description) between tableaux with p odd rows and with at most 2r columns, and pairs (P, S), where P = (P_{1}, …, P_{r}) is a non-crossing strict family of r two-rowed arrays of the shape (0, 0), and S is a p-subset of {1, 2, …, h − 1} where h is the smallest element of the first row of P_{r}. (Also here 0 denotes the empty partition. But in this context of course it means that it is coded by the r-tuple (0, 0, …, 0).) Clearly S can be put at the beginning of the first row of P_{r} thus forming an array of the type (p, 0). Thus one obtains a bijection between tableaux with p odd rows and at most 2r columns and non-crossing strict families of the shape ((p, 0, …, 0), 0). Use of (1.3) with this shape establishes the c = 2r case of (2.2).

For the c = 2r + 1 case of (2.2) we use a bijection (cf. [18, proof of Theorem 21, last paragraph]) between tableaux with p odd rows and with at most 2r + 1 columns and pairs (P, S) where P is a non-crossing strict family of r two-rowed arrays of the shape (0, 0) and S is a p-subset of the positive integers. By (1.3) with α = β = 0 this yields the c = 2r + 1 case of (2.2), where S produces h_{p}(x) and P produces the determinant.

The bijections for establishing (2.2) base on one of Burge’s [5, p. 22] variations of the Knuth correspondences [17].

The arguments for proving (2.3) and (2.4) are similar. □

Also (1.3) and (1.5), for generic α, β, have interesting interpretations in terms of tableaux generating functions. For example, we can prove the following theorem.

Theorem 4. The generating function ∑_{τ} w(τ) over all oscillating semistandard tableaux τ = (τ^{(i)}), τ : β → α (cf. [30, 11, 26]), with at most r rows equals (1.5). The weight w(τ) is defined by ∏ x_{i}^{|τ^{(2i−1)}−τ^{(2i)}|+|τ^{(2i−1)}−τ^{(2i−2)}|}.

3. Norm generating functions for tableaux. Given a tableau τ we define the norm, n(τ), of τ to be the sum of all the entries of τ. In this section we list several results for norm generating functions that are obtained from (2.1)–(2.4) by specializing the indeterminates x and y. Clearly, whenever we set x_{i} = q^{M_{i}} and y_{i} = q^{N_{i}} in (2.1)–(2.4) we obtain a determinant for the norm generating function for some family of tableaux (resp. pairs of tableaux). However, the cases of interest are only those where the determinant simplifies. For the simplification of the determinants we use special cases of the following lemma from [18, Lemma 34].

Lemma 5. 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}) , (3.1)

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 (5.5.1), 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 ∈ ℤ, a_{i} ∈ ℝ. Provided a_{N} ≠ 0 the degree of p is defined by deg p := N. □

By this lemma we arrive at multifold sums. They are basically basic hypergeometric series for A_{r} respectively C_{r}. Sometimes even these series can be evaluated. These computations are very similar to those in [18].

From (2.1) we derive the following results.

Theorem 6. Let α be a fixed partition. The generating function ∑ q^{n(τ_{1})+τ_{2}} for pairs (τ_{1}, τ_{2}) of tableaux where τ_{1} is of shape λ and τ_{2} is of shape λ/α′ with λ being some partition with λ_{1} ≤ r, and where the parts of τ_{1} are ≡ m_{1} (mod a) and between m_{1} and m_{1} + (M_{1} − 1)a, and where the parts of τ_{2} are ≡ m_{2} (mod a) and between m_{2} and m_{2} + (M_{2} − 1)a, is

∑_{λ,λ_{1}≤r} s_{λ}(q^{m_{1}}, q^{m_{1}+a}, …, q^{m_{1}+(M_{1}−1)a})s_{λ/α′}(q^{m_{2}}, q^{m_{2}+a}, …, q^{m_{2}+(M_{2}−1)a}) =

= q^{a ∑_{i=1}^{r}(\binom{α_{i}}{2}+m_{1}α_{i}/a)} ∑_{k_{1},...,k_{r}≥0} ∏_{i=1}^{r} q^{ak_{i}(k_{i}+α_{i}+μ−1)} [ \begin{matrix}−μ + 1 \\ k_{i} \end{matrix} ]_{q^{a}}

\frac{(q^{a(M_{2}+μ+α_{i}+k_{i}+i−1)}; q^{a})_{M_{1}−α_{i}−k_{i}}}{(q^{a}; q^{a})_{M_{1}+r−α_{i}−k_{i}−i}} ∏_{1≤i<j≤r}[α_{j} + k_{j} + j − α_{i} − k_{i} − i]_{q^{a}}, (3.2)

where μ := (m_{1} + m_{2})/a, (A; q)_{n} := (A; q)_{∞}/(Aq^{n}; q)_{∞} with (A; q)_{∞} = ∏_{i=0}^{∞}(1 − Aq^{i}), and [n]_{q} := (1 − q^{n}), by definition. An alternative expression for the right-hand side of (3.2) is

q^{a ∑_{i=1}^{r}(\binom{α_{i}}{2}+m_{1}α_{i}/a)} ∑_{k_{1},...,k_{r}≥0} ∏_{i=1}^{r} q^{ak_{i}(k_{i}+α_{i}+μ−1)} [ \begin{matrix}M_{2} \\ k_{i} \end{matrix} ]_{q^{a}}

\frac{[M_{1} + i − 1]_{q^{a}}!}{[M_{1} + r − α_{i} − k_{i} − i]_{q^{a}}! [α_{i} + k_{i} + i − 1]_{q^{a}}!} ∏_{1≤i<j≤r}[α_{j} + k_{j} + j − α_{i} − k_{i} − i]_{q^{a}} . (3.3)

If m_{1} + m_{2} = a the identities (3.2) (respectively (3.3)) reduce to

∑_{λ,λ_{1}≤r} s_{λ}(q^{m_{1}}, q^{m_{1}+a}, …, q^{m_{1}+(M_{1}−1)a})s_{λ/α′}(q^{a−m_{1}}, q^{2a−m_{1}}, …, q^{M_{2}a−m_{1}})

= q^{a ∑_{i=1}^{r}(\binom{α_{i}}{2}+m_{1}α_{i}/a)} ∏_{i=1}^{r} \frac{[M_{1} + M_{2} + i − 1]_{q^{a}}!}{[M_{2} + α_{i} + i − 1]_{q^{a}}! [M_{1} + r − α_{i} − i]_{q^{a}}!} ∏_{1≤i<j≤r}[α_{j}+j−α_{i}−i]_{q^{a}}. (3.4)

In particular, for α = 0 this can be written as

∑_{λ,λ_{1}≤r} s_{λ}(q^{m_{1}}, q^{m_{1}+a}, …, q^{m_{1}+(M_{1}−1)a})s_{λ}(q^{a−m_{1}}, q^{2a−m_{1}}, …, q^{M_{2}a−m_{1}})

= ∏_{1≤i≤M_{1},1≤j≤M_{2}} \frac{[r + i + j − 1]_{q^{a}}}{[i + j − 1]_{q^{a}}} . (3.5)

Remark. The special cases a = 1, m_{1} = m_{2} = 1, M_{1} = M_{2} of (3.2) and a = 2, m_{1} = 1, M_{1} = M_{2} of (3.5) first appeared in [18, Theorems 20, 9].

Sketch of Proof. In (2.1) set x_{i} = q^{m_{1}+(i−1)a} for i = 1, …, M_{1}, x_{i} = 0 for i > M_{1}, and y_{i} = q^{m_{2}+(i−1)a} for i = 1, …, M_{2}, y_{i} = 0 for i > M_{2}. With these specializations the elementary symmetric functions reduce to q-binomial coefficients times some power of q (cf. [23, p. 19, Ex. 3]). Next to each of the entries (which are q-binomial summations) of the determinant one of Heine’s _{2}ϕ_{1}-transformations [9, Appendix (III.2)] is applied. In the resulting determinant we use the linearity in the rows to take out the summations, thus arriving at a multifold sum of determinants. The determinants are evaluated by taking some factors out of the determinants and then applying Lemma 5 with C → 0, X_{s} = −q^{−a(k_{s}+α_{s}+s)}, A_{t} = q^{−a(M_{1}+t)}, p_{i−1}(X) = ∏_{j=2}^{i}(q^{a(M_{2}+μ−j)} + X). This gives (3.2) after some simplification. The expression in (3.3) results from the following A_{r} analogue of one of Heine’s _{2}ϕ_{1}-transformations [9, Appendix (III.2)], newly discovered by Gustafson [16],

∑_{k_{1},...,k_{r}≥0} (∏_{i=1}^{r} q^{k_{i}(1−i)}Z^{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{(Cq^{i−r}/B)_{∞} (BZX_{i})_{∞}}{(Zq^{i−r})_{∞} (CX_{i})_{∞}}

∑_{k_{1},...,k_{r}≥0} (∏_{i=1}^{r} q^{k_{i}(1−i)} (\frac{C}{B} )^{k_{i}} \frac{(ABZ/C)_{k_{i}} (BX_{i})_{k_{i}}}{(q)_{k_{i}} (BZX_{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}}} .

If m_{1} + m_{2} = a, i.e. μ = 1, due the q-binomial coefficient the series in (3.2) only consists of the term for k_{1} = ⋯ = k_{r} = 0. This immediately gives (3.4). For α = 0 the product can be written in the form (3.5). □

Now we turn to implications of (2.2).

Theorem 7. The generating function ∑ q^{n(τ)} for tableaux τ with p odd rows, with at most c columns, and with parts ≡ m (mod a) and between m and m + (M − 1)a, for c = 2r is

∑_{λ,λ_{1}≤2r,oddrows(λ)=p} s_{λ}(q^{m}, q^{m+a}, …, q^{m+(M−1)a})

= q^{a\binom{p}{2}+mp} ∑_{k_{1},...,k_{r}≥0} ∏_{i=1}^{r} q^{ak_{i}(k_{i}−1+p·χ(i=r)+μ)} [ \begin{matrix}−μ + 1 \\ k_{i} \end{matrix} ]_{q^{a}}

\frac{(q^{a(M+r+p·χ(i=r)+k_{i}+i+μ)}; q^{a})_{M−r−p·χ(i=r)−k_{i}+i−1}}{(q^{a}; q^{a})_{M+r−p·χ(i=r)−k_{i}−i}}

∏_{1≤i<j≤r}[p · χ(j = r) + k_{j} + j − p · χ(i = r) − k_{i} − i]_{q^{a}}

∏_{1≤i≤j≤r}[p · χ(j = r) + k_{j} + j + p · χ(i = r) + k_{i} + i + μ − 1]_{q^{a}}, (3.6a)

where μ = 2m/a, and for c = 2r + 1

∑_{λ,λ_{1}≤2r+1,oddrows(λ)=p} s_{λ}(q^{m}, q^{m+a}, …, q^{m+(M−1)a})

= q^{a\binom{p}{2}+mp} [ \begin{matrix}M \\ p \end{matrix} ]_{q^{a}} ∑_{k_{1},...,k_{r}≥0} ∏_{i=1}^{r} q^{ak_{i}(k_{i}−1+μ)} [ \begin{matrix}−μ + 1 \\ k_{i} \end{matrix} ]_{q^{a}} \frac{(q^{a(M+r+k_{i}+i+μ)}; q^{a})_{M−r−k_{i}+i−1}}{(q^{a}; q^{a})_{M+r−k_{i}−i}}

∏_{1≤i<j≤r}[k_{j} + j − k_{i} − i]_{q^{a}} ∏_{1≤i≤j≤r}[k_{j} + j + k_{i} + i + μ − 1]_{q^{a}}, (3.6b)

In case 2m = a the identities (3.6a,b) reduce to

∑_{λ,λ_{1}≤2r,oddrows(λ)=p} s_{λ}(q, q^{3}, …, q^{2M−1}) = q^{p^{2}} \frac{[2r + 2p]_{q^{2}} [r]_{q^{2}}}{[2r + p]_{q^{2}} [r + p]_{q^{2}}} [ \begin{matrix}M \\ p \end{matrix} ]_{q^{2}} \begin{matrix}[ \begin{matrix}M + 2r \\ M \end{matrix} ] & q^{2} \\ [ \begin{matrix}M + 2r + p \\ M \end{matrix} ] & q^{2} \end{matrix}

× ∏_{i=1}^{M} \frac{[r + i]_{q^{2}}}{[i]_{q^{2}}} ∏_{1≤i<j≤M} \frac{[2r + i + j]_{q^{2}}}{[i + j]_{q^{2}}} (3.7a)

and

∑_{λ,λ_{1}≤2r+1,oddrows(λ)=p} s_{λ}(q, q^{3}, …, q^{2M−1}) = q^{p^{2}} [ \begin{matrix}M \\ p \end{matrix} ]_{q^{2}} ∏_{i=1}^{M} \frac{[r + i]_{q^{2}}}{[i]_{q^{2}}} ∏_{1≤i<j≤M} \frac{[2r + i + j]_{q^{2}}}{[i + j]_{q^{2}}}

(3.7b)

where without loss of generality we let a = 2.

In case m = a the identities (3.6a,b) simplify to

∑_{λ,λ_{1}≤2r,oddrows(λ)=p} s_{λ}(q, q^{2}, …, q^{M})

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

and

∑_{λ,λ_{1}≤2r+1,oddrows(λ)=p} s_{λ}(q, q^{2}, …, q^{M}) = q^{\binom{p+1}{2}} [ \begin{matrix}M \\ p \end{matrix} ]_{q} ∏_{1≤i≤j≤M} \frac{[2r + i + j]_{q}}{[i + j]_{q}} , (3.8b)

where without loss of generality we let a = 1.

Sketch of Proof. To prove (3.6a) we do the same as before in the proof of (3.2). The only difference is that now Lemma 5 with C = 1, X_{s} = q^{a(p·χ(s=r)+k_{s}+s+μ/2−1/2)}, A_{t} = −q^{a(−M−μ/2+1/2−t)}, p_{i−1}(X) := ( ∏_{j=1}^{i}(1/A_{j} +1/X) ∏_{j=−i+2}^{0}(A_{j} +X)−∏_{j=1}^{i}(1/A_{j} +

X) ∏_{j=−i+2}^{0}(A_{j} + 1/X))/ (X − \frac{1}{X} ) has to be applied. Obviously, the p = 0 case of (3.6a)

immediately yields (3.6b). For m = 2a, i.e. μ = 2, due to the q-binomial coefficient the sums in (3.6a,b) reduce to the respective terms for k_{1} = ⋯ = k_{r} = 0. This leads to (3.7a,b). For m = a, i.e. μ = 1, the sums in (3.6a,b) can be evaluated by a special case of Gustafson’s [15, Theorem 5.1] C_{r} _{6}ψ_{6} summation (see also [22; 18, subsection 5.6]). After some simplification one arrives at (3.8a,b). □

Remark. Identity (3.7) is a refinement of the MacMahon (ex-)Conjecture which was first proved in another paper of the author [18, Theorem 11]. (The MacMahon Conjecture was proved by Andrews [4], Macdonald [23, pp. 51/52, Ex. 16,17], and Proctor [25, Proposition 7.3].) Likewise, identity (3.8) is a refinement of the Bender–Knuth (ex-)Conjecture which the author also first proved in the same paper [18, Theorem 21]. (The Bender–Knuth Conjecture was proved by Andrews [3], Gordon [13], Macdonald [23, pp. 51–53, Ex. 16,18], and Proctor [25, Proposition 7.2].) As was remarked in [18] by summing the expressions in (3.7) respectively (3.8) with respect to p we get new proofs of the MacMahon respectively the Bender–Knuth Conjecture. We formulate the MacMahon Conjecture in an equivalent form. The original formulation is in terms of symmetric plane partitions.

Corollary 8. The generating function for tableaux with at most c columns, and with only odd parts which lie between 1 and 2M − 1, is given by

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

(MacMahon Conjecture)

The generating function for tableaux with at most c columns, and with parts which lie between 1 and M, is given by

∏_{1≤i≤j≤M} \frac{[c + i + j − 1]_{q}}{[i + j − 1]_{q}} .  (Bender–Knuth Conjecture)

Sketch of Proof. In order to obtain the MacMahon Conjecture the sum over all p of the expressions in (3.7a) is evaluated by a special case of the very well-poised_{6}ϕ_{5}-summation (cf. [9, Appendix (II.21)]) while the sum over all p of the expressions in (3.7b) is evaluated by the q-binomial summation (cf. [2, (3.3.7)]). Similarly, in order to obtain the Bender–Knuth Conjecture the sum over all p of the expressions in (3.8a) is evaluated by the q-Kummer summation (cf. [9, Appendix (II.9)]), while the sum over all p of the expressions in (3.8b) is again evaluated by the q-binomial summation. □

Finally we turn to the implications of (2.3) and (2.4). In the same special cases as before we can get rid of the determinants thus arriving at A_{r}- respectively C_{r}-type sums. But unfortunately here it does not seem to be possible to find any nontrivial cases in which these sums can be evaluated to result into closed forms. But it should be noted that these sums are finite.

Theorem 9. Let α be a fixed partition. The generating function ∑ q^{n(τ_{1})+τ_{2}} for pairs (τ_{1}, τ_{2}) of tableaux where τ_{1} is of shape λ and τ_{2} is of shape λ/α with λ being some partition with ℓ(λ) ≤ r, and where the parts of τ_{1} are ≡ m_{1} (mod a) and between m_{1} and m_{1} +(M_{1} − 1)a, and where the parts of τ_{2} are ≡ m_{2} (mod a) and between m_{2} and m_{2} + (M_{2} − 1)a, for M_{1} ≥ r − α_{1} is

∑_{λ,ℓ(λ)≤r} s_{λ}(q^{m_{1}}, q^{m_{1}+a}, …, q^{m_{1}+(M_{1}−1)a})s_{λ/α}(q^{m_{2}}, q^{m_{2}+a}, …, q^{m_{2}+(M_{2}−1)a})

= \frac{q^{m_{1} ∑_{i=1}^{r} α_{i}}}{(q^{a}; q^{a})_{M_{1}−1}^{r} (q^{m_{1}+m_{2}}; q^{a})_{M_{2}}^{r}}

∑_{k_{1},...,k_{r}≥0} ∏_{i=1}^{r} q^{ak_{i}(M_{1}+α_{i})} \frac{(q^{a(1−M_{1})}; q^{a})_{k_{i}} (q^{m_{1}+m_{2}}; q^{a})_{k_{i}}}{(q^{a}; q^{a})_{k_{i}} (q^{aM_{2}+m_{1}+m_{2}}; q^{a})_{k_{i}}} ∏_{1≤i<j≤r}(1 − q^{a(k_{j}−k_{i})}). (3.9)

Remark. The restriction M_{1} ≥ r − α_{1} actually is not a serious restriction. Obviously the tableaux τ_{1} have at most M_{1} rows. Therefore, if M_{1} < r we may replace r by M_{1} and then apply (3.9).

Sketch of Proof. We proceed in analogy with the proof of Theorem 6. In (2.3) set x_{i} = q^{m_{1}+(i−1)a} for i = 1, …, M_{1}, x_{i} = 0 for i > M_{1}, and y_{i} = q^{m_{2}+(i−1)a} for i = 1, …, M_{2}, y_{i} = 0 for i > M_{2}. With these specializations the complete homogenous symmetric functions reduce to q-binomial coefficients times some power of q (cf. [23, p. 19, Ex. 3]). This time a limiting case of another one of Heine’s _{2}ϕ_{1}-transformations [9, Appendix (III.1)] is applied. In the resulting determinant we use the linearity in the rows to take out the summations thus arriving at a multifold sum of determinants. Upon taking some factors out of these determinants, they reduce to Vandermonde determinants and are therefore easily evaluated. □

Theorem 10. The generating function ∑ q^{n(τ)} for tableaux τ with p odd columns, with at most c rows, and with parts ≡ m (mod a) and between m and m + (M − 1)a, for c = 2r and M ≥ r is

∑_{λ,ℓ(λ)≤2r,oddcolumns(λ)=p} s_{λ}(q^{m}, q^{m+a}, …, q^{m+(M−1)a})

= \frac{q^{mp}}{(q^{a}; q^{a})_{M−1}^{r} (q^{2m}; q^{a})_{M}^{r}} ∑_{k_{1},...,k_{r}≥0} ∏_{i=1}^{r} q^{ak_{i}(M+p·χ(i=r))} \frac{(q^{a(1−M)}; q^{a})k_{i} (q^{2m}; q^{a})_{k_{i}}}{(q^{a}; q^{a})_{k_{i}} (q^{aM+2m})_{k_{i}}}

× ∏_{1≤i<j≤r}(1 − q^{a(k_{j}−k_{i})}) ∏_{1≤i≤j≤r}(1 − q^{a(k_{i}+k_{j})+2m}), (3.10a)

and for c = 2r + 1 and M ≥ r

∑_{λ,ℓ(λ)≤2r+1,oddcolumns(λ)=p} s_{λ}(q^{m}, q^{m+a}, …, q^{m+(M−1)a})

= \frac{q^{mp}}{(q^{a}; q^{a})_{M−1}^{r} (q^{2m}; q^{a})_{M}^{r}} [ \begin{matrix}M + p − 1 \\ p \end{matrix} ]_{q^{a}} ∑_{k_{1},...,k_{r}≥0} ∏_{i=1}^{r} q^{ak_{i}M} \frac{(q^{a(1−M)}; q^{a})k_{i} (q^{2m}; q^{a})_{k_{i}}}{(q^{a}; q^{a})_{k_{i}} (q^{aM+2m})_{k_{i}}}

× ∏_{1≤i<j≤r}(1 − q^{a(k_{j}−k_{i})}) ∏_{1≤i≤j≤r}(1 − q^{a(k_{i}+k_{j})+2m}). (3.11a)

Remark. Again the restriction M ≥ r is not serious since if M < r we may replace r by ⌈\frac{M}{2} ⌉.

Sketch of Proof. We do the same as before in the proof of Theorem 9. Here the determinants which have to be computed are

det_{1≤s,t≤r}(q^{−at(m+k_{s})} − q^{at(m+k_{s})}).

This is done by using Lemma 5 with C = 1, X_{s} = q^{−a(m+k_{s})}, A_{t} → 0, p_{i−1}(X) = (X^{i} − 1/X^{i})/(X − 1/X) (see also [24, p. 10, (I)]). □

4. “Flagged” non-crossing two-rowed arrays and enumeration of nonintersecting lattice paths with given number of turns. Theorems 1 and 2 can be generalized to “flagged” families of non-crossing two-rowed arrays by using the same proof. By “flagged” we mean that the entries in the i-th two-rowed array P_{i} of a family P are bounded by different lower and upper bounds. (This resembles the definition for flagged Schur functions (cf. e.g. [32]) in terms of tableaux with different lower and upper bounds on the entries in each row of the tableaux.) We do not have the space to write down the results. Instead, we record three interesting applications of these results in the enumeration of nonintersecting lattice paths with a given number of turns. These results are related to the computation of Hilbert polynomials of determinantal ideals (cf. [20, 7]). Similar results can be derived for the path-like objects that were called pathoids in [21]. For the interested reader we remark that enumeration results for pairs of nonintersecting lattice paths with a given number of EN-corners (see the definition below) of the “upper” path and a given number of NE-corners (see the definition below) of the “lower” path are given in [29, 19].

As in [18] a point X of a lattice path is called NE-corner, if X is the end point of a step in North direction and at the same time starting point of a step in East direction. Analogously, X is called EN-corner, if X is the end point of a step in East direction and at the same time starting point of a step in North direction.

Theorem 11. Let A_{i} = (A_{1}^{(i)}, A_{2}^{(i)}) and E_{i} = (E_{1}^{(i)}, E_{2}^{(i)}) be lattice points satisfying A_{1}^{(1)} ≤ A_{1}^{(2)} ≤ ⋯ ≤ A_{1}^{(r)}, A_{2}^{(1)} > A_{2}^{(2)} > ⋯ > A_{2}^{(r)}, and E_{1}^{(1)} < E_{1}^{(2)} < ⋯ < E_{1}^{(r)}, E_{2}^{(1)} ≥ E_{2}^{(2)} ≥ ⋯ ≥ E_{2}^{(r)}. The number of all families P = (P_{1}, …, P_{r}) of nonintersecting lattice paths P_{i} : A_{i} → E_{i}, such that the paths of P altogether contain exactly K NE-corners, is

∑_{k_{1}+···+k_{r}=K} det_{1≤s,t≤r} (\binom{E_{1}^{(t)} − A_{1}^{(s)} + s − t}{k_{s} + s − t}\binom{E_{2}^{(t)} − A_{2}^{(s)} − s + t}{k_{s}}).  □  (4.1)

Remark. A special case of this result is of relevance in the computation of Hilbert polynomials of determinantal ideals. In fact, Kulkarni [20, Main Theorem 5] derived this special case (r = p, K = E, A_{i} = (0, a_{p−i+1}), E_{i} = (m(2)−b_{p−i+1}, m(1))) from Abhyankar’s formula [1, (20.14.4), p. 484], while Conca and Herzog [7] used it to give an alternative proof of Abhyankar’s formula. A special case of the “pathoid” analogue of Theorem 11 is also related to Abhyankar’s formula (cf. [21, Main Theorem 7]).

Theorem 12. Let A_{i} = (A_{1}^{(i)}, A_{2}^{(i)}) and E_{i} = (E_{1}^{(i)}, E_{2}^{(i)}) be lattice points satisfying A_{1}^{(1)} ≤ A_{1}^{(2)} ≤ ⋯ ≤ A_{1}^{(r)}, A_{2}^{(1)} > A_{2}^{(2)} > ⋯ > A_{2}^{(r)}, E_{1}^{(1)} < E_{1}^{(2)} < ⋯ < E_{1}^{(r)}, E_{2}^{(1)} ≥ E_{2}^{(2)} ≥ ⋯ ≥ E_{2}^{(r)}, and A_{1}^{(i)} ≥ A_{2}^{(i)}, E_{1}^{(i)} ≥ E_{2}^{(i)}, i = 1, …, r. The number of all families P = (P_{1}, …, P_{r}) of nonintersecting lattice paths P_{i} : A_{i} → E_{i}, which do not cross the line x = y, and where the paths of P altogether contain exactly K NE-corners, is

∑_{k_{1}+···+k_{r}=K} det_{1≤s,t≤r} (\binom{E_{1}^{(t)} − A_{1}^{(s)} + s − t}{k_{s} + s − t}\binom{E_{2}^{(t)} − A_{2}^{(s)} − s + t}{k_{s}}

− \binom{E_{1}^{(t)} − A_{2}^{(s)} − s − t + 1}{k_{s} − t}\binom{E_{2}^{(t)} − A_{1}^{(s)} + s + t − 1}{k_{s} + s}). □ (4.2)

Theorem 13. Let A_{i} = (A_{1}^{(i)}, A_{2}^{(i)}) and E_{i} = (E_{1}^{(i)}, E_{2}^{(i)}) be lattice points satisfying A_{1}^{(1)} < A_{1}^{(2)} < ⋯ < A_{1}^{(r)}, A_{2}^{(1)} ≥ A_{2}^{(2)} ≥ ⋯ ≥ A_{2}^{(r)}, E_{1}^{(1)} ≤ E_{1}^{(2)} ≤ ⋯ ≤ E_{1}^{(r)}, E_{2}^{(1)} > E_{2}^{(2)} > ⋯ > E_{2}^{(r)}, and A_{1}^{(i)} ≥ A_{2}^{(i)}, E_{1}^{(i)} ≥ E_{2}^{(i)}, i = 1, …, r. The number of all families P = (P_{1}, …, P_{r}) of nonintersecting lattice paths P_{i} : A_{i} → E_{i}, P_{i} : A_{i} → E_{i}, which do not cross the line x = y, and where the paths of P altogether contain exactly K EN-corners, is

∑_{k_{1}+···+k_{r}=K} det_{1≤s,t≤r} (\binom{E_{1}^{(t)} − A_{1}^{(s)} + s − t}{k_{s} + s − t}\binom{E_{2}^{(t)} − A_{2}^{(s)} − s + t}{k_{s}}

− \binom{E_{1}^{(t)} − A_{2}^{(s)} − s − t + 3}{k_{s} − t + 1}\binom{E_{2}^{(t)} − A_{1}^{(s)} + s + t − 3}{k_{s} + s − 1}). □ (4.3)

References

1. S. S. Abhyankar, Enumerative combinatorics of Young tableaux, Marcel Dekker, New York, Basel, 1988.

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

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

4. G. E. Andrews, Plane partitions (I): The MacMahon conjecture, Studies in Foundations and Combinatorics (G.-C. Rota, ed.), Adv. in Math. Suppl. Studies, Vol.1, 1978, pp. 131–150.

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

6. S. H. Choi and D. Gouyou–Beauchamps, Enumération de tableaux de Young semi-standard, Actes de 3eme Colloque de Series Formelles et Combinatoire Algebrique, Bordeaux 1991, M. Delest, G. Jacob, P. Leroux, Eds., LabRI, Université Bordeaux I, 1991, pp. 229—243.

7. A. Conca and J. Herzog, On the Hilbert function of determinantal rings and their canonical module, preprint, 1992.

8. S. Fomin, Schensted algorithms for graded graphs, preprint.

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

10. I. M. Gessel, Symmetric functions and P -recursiveness, J. Combin. Theory A 53 (1990), 257—285.

11. I. M. Gessel, Counting paths in Young’s lattice, J. Statist. Plann. Inference 34 (1993).

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

13. B. Gordon, Notes on plane partitions IV. Multirowed partitions with strict decrease along columns, Combinatorics, Proc. Sympos. Pure Math. vol. XIX, Univ. California, Los Angeles, California, 1968, Amer. Math. Soc., Providence, R. I., 1971, pp. 91–100.

14. I. P. Goulden, A linear operator for symmetric functions and tableaux in a strip with given trace, Discrete Math. 99 (1992), 69—77.

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

16. R. A. Gustafson, private communication.

17. D. E. Knuth, Permutations, matrices, and generalized Young tableaux, Pacific J. Math. 34 (1970), 709—727.

18. C. Krattenthaler, The major counting of nonintersecting lattice paths and generating functions for tableaux, preprint.

19. C. Krattenthaler and R. A. Sulanke, Counting pairs of nonintersecting lattice paths with respect to weighted turns, presented at the poster session of the 5th Conference for Formal Power Series and Algebraic Combinatorics, Florence 1993.

20. D. M. Kulkarni, Counting of paths and coefficients of Hilbert polynomial of a determinantal ideal, preprint.

21. D. M. Kulkarni, Counting of path-like objects and coefficients of Hilbert polynomial of a determinantal ideal, preprint.

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

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

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

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

26. T. W. Roby, Applications and extensions of Fomin’s generalization of the Robinson–Schensted correspondence to differential posets, Ph.D. thesis, M.I.T., Cambridge, Massachusetts, 1991.

27. B. E. Sagan and R. P. Stanley, Robinson–Schensted algorithms for skew tableaux, J. Combin. Theory Ser. A 55 (1990), 161–193.

28. J. R. Stembridge, Nonintersecting paths, pfaffians and plane partitions, Adv. in Math. 83 (1990), 96—131.

29. R. A. Sulanke, Refinements of the Narayana numbers, Bull. Inst. Combin. Appl. 7 (1993), 60–66.

30. S. Sundaram, On the combinatorics of representations of Sp(2n, ℂ), Ph. D. Thesis, Massachusetts Institute of Technology, 1986.

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

32. M. L. Wachs, Flagged Schur functions, Schubert polynomials, and symmetrizing operators, J. Combin. Theory Ser. A 40 (1985), 276–289.