Oscillating tableaux and nonintersecting lattice paths

C. Krattenthaler

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria. e-mail: KRATT@Pap.Univie.Ac.At

Abstract. We give alternative proofs of determinantal formulas for certain up-down tableaux and down-up tableaux generating functions, which were first given in another paper by the author. These new proofs are based on interpreting up-down and down-up tableaux as certain families of nonintersecting lattice paths with three types of steps.

1. Introduction and definitions. We provide proofs by nonintersecting lattice paths for two formulas in [20, 19] (see (1.1) and (1.2) below) about the generating functions for certain oscillating tableaux. However, before we are able to reproduce the formulas we have to recall some definitions. A partition is a sequence λ = (λ_{1}, λ_{2}, …) of nonnegative integers which are in decreasing order, i.e. λ_{1} ≥ λ_{2} ≥ ⋯, where only finitely many entries differ from zero. Zeros in the “tail” of a partition are frequently omitted. For instance, (6, 4, 4, 1, 0, 0, …) = (6, 4, 4, 1, 0) = (6, 4, 4, 1). Partitions can be viewed pictorially as left-justified arrays of cells where the number of cells in the i-th row of the array is given by λ_{i}. This array of cells is called Ferrers diagram of the partition λ. For example, the Ferrers diagram of (6, 4, 4, 1) is displayed in Figure 1.

Figure 1

The partition conjugate to a partition λ is the partition λ′ = (λ′_{1}, λ′_{2}, …) where λ′_{i} is the number of cells in the i-th column of λ. Equivalently, the Ferrers diagram of λ′ is the Ferrers diagram of λ reflected in its main diagonal. For example, the partition conjugate to (6, 4, 4, 1) is (4, 3, 3, 3, 1, 1). On the set of partitions a partial order ⊆ is defined by: μ ⊆ λ if and only if μ_{i} ≤ λ_{i} for all i. Equivalently, μ ⊆ λ if and only if the Ferrers diagram of μ is contained in the Ferrers diagram of λ.

1980 Mathematics Subject Classification (1991 Revision). Primary 05E10; Secondary 05A15, 20C33, 22E45.

Key words and phrases. Oscillating tableaux, nonintersecting lattice paths.

A (generalized) up-down tableau from μ to λ [13, 31, 32, 37] is a sequence T = (τ_{0}, τ_{1}, …, τ_{2n−1}, τ_{2n}) of partitions (Ferrers diagrams), for some n, such that

μ = τ_{0} ⊆ τ_{1} ⊇ τ_{2} ⊆ ⋯ ⊆ τ_{2n−1} ⊇ τ_{2n} = λ,

and τ_{i−1} and τ_{i} differ by a horizontal strip for each i = 1, 2, …, 2n. A horizontal strip (cf. [25, p. 4]) is an arrangement of cells with at most one cell in each column. The number 2n is called the length of the up-down tableau T.

Similarly, a (generalized) down-up tableau from μ to λ is a sequence T = (τ_{0}, τ_{1}, …, τ_{2n−1}, τ_{2n}) of partitions, for some n, such that

μ = τ_{0} ⊇ τ_{1} ⊆ τ_{2} ⊇ ⋯ ⊇ τ_{2n−1} ⊆ τ_{2n} = λ,

and τ_{i−1} and τ_{i} differ by a horizontal strip for each i = 1, 2, …, 2n. Again, the number 2n is called the length of the down-up tableau T. Examples for an up-down tableau and a down-up tableau from (2, 1, 1) to (2, 2, 1, 1) are given in Figure 2. Both have length 4.

( ,  ,  ,  ,  )  up-down tableau

( , ,  , ,  )  down-up tableau

Figure 2

We say that an up-down tableau (respectively down-up tableau) T = (τ_{0}, τ_{1}, …, τ_{2n−1}, τ_{2n}) has at most r columns (respectively rows) if each τ_{i}, i = 0, 1, …, 2n, has at most r columns (rows). So for example, the up-down tableau in Figure 2 has at most 5 (6, 7, …) columns and the down-up tableau in Figure 2 has at most 4 (5, 6, …) rows.

The weight w(T) of an up-down or down-up tableau T is defined by

w(T) := x_{1}^{| |τ_{0}|−|τ_{1}| |}x_{1}^{| |τ_{1}|−|τ_{2}| |}x_{2}^{| |τ_{2}|−|τ_{3}| |}x_{2}^{| |τ_{3}|−|τ_{4}| |} · · · .

Thus the weight of the up-down tableau in Figure 2 is given by x_{1}^{2}x_{1}^{0}x_{2}^{4}x_{2}^{4} = x_{1}^{2}x_{2}^{8}, while the weight of the down-up tableau in Figure 2 is given by x_{1}^{2}x_{1}^{3}x_{2}^{1}x_{2}^{2} = x_{1}^{5}x_{2}^{3}. Let us write x for the sequence of variables x_{1}, x_{2}, . . ..

Now we are able to state the formulas of [20, 19]. Let ud_{μ→λ}^{(r)}(x) denote the generating function ∑_{T} w(T) summed over all up-down tableaux T from μ to λ with at most r columns. Then for any partitions α = (α_{r}, α_{r−1}, …, α_{1}) and β = (β_{r}, β_{r−1}, …, β_{1}) we have

ud_{β′→α′}^{(r)}(x) = det_{1≤s,t≤r} ( ∑_{k} e_{α_{s}+s−β_{t}−t+k}(x)e_{k}(x) − ∑_{k} e_{α_{s}+s+β_{t}+t+k}(x)e_{k}(x)),

(1.1) where e_{m}(x) denotes the elementary symmetric function of order m in the variables x_{1}, x_{2}, … (cf. [25, p. 12]). Note that we definitely want the entries of α and β to be indexed in reverse order.

Likewise, let du_{μ→λ}^{(r)}(x) denote the generating function ∑_{T} w(T) summed over all down-up tableaux T from μ to λ with at most r rows. Then for partitions α and β as above we have

du_{β→α}^{(r)}(x) = det_{1≤s,t≤r} ( ∑_{k} h_{α_{s}+s−β_{t}−t+k}(x)h_{k}(x)−∑_{k} h_{α_{s}+s+β_{t}+t+k}(x)h_{k}(x)), (1.2)

where h_{m}(x) denotes the complete homogeneous symmetric function of order m in the variables x_{1}, x_{2}, … (cf. [25, p. 14]).

The significance of the formulas (1.1) and (1.2) is elaborated in [20]. In particular, from these formulas enumeration results for standard oscillating tableaux with a bounded number of rows can be derived. These standard oscillating tableaux play an important role in Berele’s decomposition formula [1] for powers of defining representations of the complex symplectic groups. Also, if α or β are rectangular shapes the determinant in (1.1) basically is an irreducible symplectic character. This led to a new combinatorial description of irreducible symplectic characters in terms of oscillating tableaux [20].

The formulas (1.1) and (1.2) were proved in [20] by interpreting the right-hand side determinants of (1.1) and (1.2) as generating functions for certain families of two-rowed arrays and then setting up a bijection between these families of two-rowed arrays and up-down and down-up tableaux. These bijections were based on Robinson– Schensted type algorithms. In the next section we shall prove (1.1) and (1.2) by using nonintersecting lattice paths and variations of the so-called reflection principle (cf. e.g. [6, p. 22]). The method of nonintersecting lattice paths, due to Gessel and Viennot [15, 16] (cf. also [34, sec. 1]), has been successfully utilized in numerous papers [2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 14, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 33, 34, 35, 36, 38]. So this paper might be considered as a further contribution to this list of papers (which very likely is incomplete). Combinations of the nonintersecting lattice path method and variants of the reflection principle earlier appeared in [12, 19, 20, 21].

2. Nonintersecting lattice paths. To begin with, we introduce some lattice path notation. Given a set S of steps we denote the set of all lattice paths from A to E with steps from the set S by P(A → E; S). We frequently shall write P : A → E to indicate that the lattice path P runs from A to E. A set of paths is said to be nonintersecting if no two paths of this set have a point in common. Otherwise it is called intersecting. If to each step s ∈ S a weight w(s) is assigned, the weight w(P) of a path P is defined to be the product of the weights of all its steps. The weight w(P) of a family P = (P_{1}, …, P_{r}) of paths is defined to be the product ∏_{i=1}^{r} w(P_{i}) of the weights of all the paths in the family. Given any weight function w defined on a set M, by the generating function GF (M; w) we mean ∑_{x∈M} w(x).

Proof of (1.1). Here we consider lattice paths in the plane integer lattice with steps from the set S_{1} = {(i, j) → (i, j+1), (i, 2j−2) → (i+1, 2j−1), (i, 2j−1) → (i−1, 2j), where i, j run through the integers}. In words, the set of steps consists of vertical steps north, forward diagonal steps northeast from even height to odd height, and backward diagonal steps northwest from odd height to even height. In the sequel, when we say ‘lattice path’ we always mean a lattice path with steps from the set S_{1}.

First we set up a one-to-one correspondence between up-down tableaux from β′ to α′ with at most r columns and families P = (P_{1}, P_{2}, …, P_{r}) of nonintersecting lattice paths where P_{i} runs from A_{i} = (β_{i} + i, 0) to E_{i} = (α_{i} + i, ∞) and never touches the y-axis, i = 1, 2, …, r. Let T = (τ_{0}, τ_{1}, …, τ_{2n}) be an up-down tableau from β′ to α′ with at most r columns. The bijection is defined in a way such that the i-th path encodes the growth and shrink of the (r − i + 1)-st column of T. To be more precise, starting with A_{i} = (β_{i} + i, 0) for j = 1, 2, …, n do the following procedure: If τ_{2j−1} has one cell more in the (r − i + 1)-st column than τ_{2j−2} then add a forward diagonal step to P_{i}, otherwise a vertical step. If τ_{2j} has one cell less in the (r −i+1)-st column than τ_{2j−1} then add a backward diagonal step, otherwise a vertical step. Finally, an infinite number of vertical steps is added to each path to connect to the end points (α_{i} + i, ∞). Thus, given r = 5, the up-down tableau in Figure 2 corresponds to the set of nonintersecting lattice paths displayed in Figure 3. Note that in this example we have α = (4, 2, 0, 0, 0) and β = (3, 1, 0, 0, 0), i.e. α_{1} = α_{2} = α_{3} = 0, α_{4} = 2, α_{5} = 4, β_{1} = β_{2} = β_{3} = 0, β_{4} = 1, β_{5} = 3.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; A_{1}; A_{2}; A_{3}; A_{4}; A_{5}; E_{1}; E_{2}; E_{3}; E_{4}; E_{5}; ↑; ↑; ↑; ↑; ↑; P_{1}; P_{2}; P_{3}; P_{4}; P_{5}] Figure 3

Clearly this operation sets up the claimed bijection. It becomes weight-preserving if we define the weight w(v) of a vertical step v to be 1, the weight w(f) of a forward diagonal step f : (i, 2j − 2) → (i + 1, 2j − 1) as well as the weight w(b) of a backward diagonal step b : (i, 2j − 1) → (i − 1, 2j) to be x_{j}. Recall that this weight function w on the step set S_{1} induces a weight w on families of lattice paths as was explained at the beginning of this section.

Next we give a combinatorial description of the determinant in (1.1). Because of

GF (P((a, 0) → (b, ∞); S_{1}); w) = ∑_{k} e_{b−a+k}(x)e_{k}(x)

we may write the determinant in (1.1) as

det (GF (P(A_{t} → E_{s}; S_{1}); w) − GF (P(ℜA_{t} → E_{s}; S_{1}); w)),  (1.3)

where ℜ is the reflection in the y-axis. By expanding the determinant, (1.3) can be written in the form

∑_{σ∈𝔖_{r}} ; η∈{1,−1}^{r} sgn σ ∏_{i=1}^{r} η_{i} ∏_{i,η_{i}=1} GF (P(A_{σ(i)} → E_{i}; S_{1}); w)

∏_{i,η_{i}=−1} GF (P(ℜA_{σ(i)} → E_{i}; S_{1}); w),

or

∑_{σ∈𝔖_{r}, η∈{0,1}^{r}} ; P=(P_{1},...,P_{r}), P_{i}:ℜ^{η_{i}} A_{σ(i)}→E_{i}(−1)^{∥η∥} sgn σ w(P),  (1.4)

where ∥η∥ = ∑_{i=1}^{r} η_{i}. Of course, ℜ^{0} means the identity map.

By (1.4) we have written the determinant in (1.1) as a generating function for families P = (P_{1}, P_{2}, …, P_{r}) of lattice paths, P_{i} : ℜ^{η_{i}}A_{σ(i)} → E_{i}, for some σ ∈ 𝔖_{r} and η ∈ {0, 1}^{r}. Let us call σ the permutation associated to P and η the reflection indicator associated to P. In the sum (1.4) many terms will cancel. We shall construct a sign-reversing (with respect to (−1)^{∥η∥} sgn σ) and weight-preserving (with respect to w) involution on the set of all families P = (P_{1}, P_{2}, …, P_{r}) of lattice paths that were described above, which are either intersecting or contain a path that touches the y-axis. Suppose that this had been done. Then in the sum (1.4) only the terms which come from nonintersecting families of lattice paths that do not touch the y-axis will survive. In particular, none of the starting points of such a family P could be located to the left of the y-axis. Hence, the reflection indicator associated to P must equal (1, 1, …, 1). Besides, because P is nonintersecting the location of the starting and end points of the paths of P implies that the permutation associated to P must be the identity permutation. But these families P of lattice paths exactly correspond to the up-down tableaux under consideration, as was shown above. This would establish (1.1).

Now we define the involution, which we denote by Θ_{1}. Let P = (P_{1}, P_{2}, …, P_{r}) be a family of lattice paths, P_{i} : ℜ^{η_{i}}A_{σ(i)} → E_{i}, for some σ ∈ 𝔖_{r} and η ∈ {0, 1}^{r}, which is either intersecting or contains a path that touches the y-axis. First consider all meeting points of a path of P and the y-axis. Let M be the highest of these meeting points. Among the paths which go through M choose P_{I} with I being minimal. Note that the y-coordinate of M must be even. Now, to P_{I}’s initial portion up to M we apply the following modified reflection in the y-axis (see Figure 4). Beginning from the starting point of P_{I} up to M consider the steps of P_{I} in groups of two. There are four different cases. Replace two vertical steps by two vertical steps, a vertical step and a backward diagonal step by a forward diagonal step and a vertical step, a forward diagonal step and a vertical step by a vertical step and a backward diagonal step, a forward diagonal step and a backward diagonal step by a forward diagonal step and a backward diagonal step. What is obtained by this procedure is joined with the terminal portion of P_{I} beginning from M. In Figure 4 the circled points indicate the grouping of the steps into groups of two that was described above. Let the image of P_{I} under application of this modified reflection be denoted by P′_{I}. We then obtain the new family Θ_{1}(P) = (P_{1}, …, P′_{I}, …, P_{r}). Since the new starting point of P′_{I} is the reflection of the starting point of P_{I} in the y-axis, the permutation associated to Θ_{1}(P) in this case is still σ while the reflection indicator associated to Θ_{1}(P) is given by (η_{1}, …, 1 − η_{I}, …, η_{r}).

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ∘; ∘; ∘; ℜ^{η_{I}} A_{σ(I)}; M; E_{I}; P_{I}; ⟶; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ∘; ∘; ∘; ℜ^{1−η_{I}} A_{σ(I)}; M; E_{I}; P′_{I}] Figure 4

If none of the paths of P meet the y-axis consider all meeting points between any two paths of P. Choose the highest meeting points, and among those the left-most. Denote this meeting point by M. Now we apply the usual Gessel–Viennot interchanging procedure. To be more precise, among the pairs of paths which have M in common, choose (P_{I}, P_{J}), with (I, J) being minimal with respect to the lexicographic order of pairs of integers. Next we decompose P_{I} into P_{I}^{(1)} and P_{I}^{(2)}, where P_{I}^{(1)} is the portion of P_{I} going from ℜ^{η_{I}} A_{σ(I)} to M, and where P_{I}^{(2)} is the portion of P_{I} between M and E_{I}. Analogously, P_{J} is decomposed by M into P_{J}^{(1)} and P_{J}^{(2)}. Then by concatenation form the new paths P′_{I} = P_{J}^{(1)}P_{I}^{(2)} and P′_{J} = P_{I}^{(1)}P_{J}^{(2)}. In other terms, the initial portions of P_{I} and P_{J} up to their last meeting point are interchanged, the terminal portions are preserved. Thus we obtain the new family Θ_{1}(P) = (P_{1}, …, P′_{I}, …, P′_{J}, …, P_{r}). Obviously, since the I-th and J-th starting point have been interchanged, the permutation associated to Θ_{1}(P) is σ ∘ (IJ) ((IJ) is the transposition that interchanges I and J), and the reflection indicator associated to Θ_{1}(P) is (η_{1}, …, η_{J}, …, η_{I}, …, η_{r}).

It is easy to see that in both cases, by application of Θ_{1} to Θ_{1}(P), one arrives at P again. Consequently Θ_{1} is an involution. Besides, by construction it is weightpreserving with respect to w and sign-reversing with respect to (−1)^{∥η∥} sgn σ. □

Proof of (1.2). Here we consider lattice paths in the plane integer lattice with steps from the set S_{2} = {(i, j) → (i, j + 1), (i, 2j − 1) → (i − 1, 2j − 1), (i, 2j) → (i + 1, 2j), where i, j run through the integers}. In words, the set of steps consists of vertical steps north, backward horizontal steps (west) at odd height, and forward horizontal steps (east) at even height. In the sequel, when we say ‘lattice path’ we always mean a lattice path with steps from the set S_{2}.

First we set up a one-to-one correspondence between down-up tableaux from β to α with at most r rows and families P = (P_{1}, P_{2}, …, P_{r}) of nonintersecting lattice paths where P_{i} runs from A_{i} = (β_{i} + i, 0) to E_{i} = (α_{i} + i, ∞) and never touches the y-axis, i = 1, 2, …, r. Let T = (τ_{0}, τ_{1}, …, τ_{2n}) be a down-up tableau from β to α with at most r rows. The bijection is defined in a way such that the i-th path encodes the growth and shrink of the (r − i + 1)-st row of T. To be more precise, starting with A_{i} = (β_{i} + i, 0) for j = 1, 2, …, n do the following procedure: If τ_{2j−1} has n cells less in the (r − i + 1)-st row than τ_{2j−2} then add a vertical step followed by n backward horizontal steps to P_{i}. If τ_{2j} has n cells more in the (r − i + 1)-st row than τ_{2j−1} then add a vertical step followed by n forward horizontal steps to P_{i}. Finally, an infinite number of vertical steps is added to each path to connect to the end points (α_{i} + i, ∞). Thus, given r = 4, the down-up tableau in Figure 2 corresponds to the set of nonintersecting lattice paths displayed in Figure 5. Note that in this example we have α_{1} = 1, α_{2} = 1, α_{3} = 2, α_{4} = 2, β_{1} = 0, β_{2} = 1, β_{3} = 1, β_{4} = 2.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • • • •_{A_{1}}  _{A_{2}} _{A_{3}}  _{A_{4}}^{E_{1}} ^{E_{2}}  ^{E_{3}} ^{E_{4}}^{↑} ^{↑}  ^{↑} ^{↑}^{P_{1}}  ^{P_{2}}  ^{P_{3}}  ^{P_{4}} Figure 5

Clearly this operation sets up the claimed bijection. It becomes weight-preserving if we define the weight w(v) of a vertical step v to be 1, the weight w(f) of a backward horizontal step f : (i, 2j − 1) → (i − 1, 2j − 1) as well as the weight w(b) of a forward horizontal step b : (i, 2j) → (i + 1, 2j) to be x_{j}. Recall that this weight function w on the step set S_{2} induces a weight w on families of lattice paths as was explained at the beginning of this section.

Next we give a combinatorial description of the determinant in (1.2). Because of

GF (P((a, 0) → (b, ∞); S_{2}); w) = ∑_{k} h_{b−a+k}(x)h_{k}(x)

we may write the determinant in (1.2) as

det (GF (P(A_{t} → E_{s}; S_{2}); w) − GF (P(ℜA_{t} → E_{s}; S_{2}); w)),  (1.5)

where ℜ is again the reflection in the y-axis. By expanding the determinant, (1.5) can be written in the form

∑_{σ∈𝔖_{r}} ; η∈{1,−1}^{r} sgn σ ∏_{i=1}^{r} η_{i} ∏_{i,η_{i}=1} GF (P(A_{σ(i)} → E_{i}; S_{2}); w)

∏_{i,η_{i}=−1} GF (P(ℜA_{σ(i)} → E_{i}; S_{2}); w),

or

∑_{σ∈𝔖_{r}, η∈{0,1}^{r}} ; P=(P_{1},...,P_{r}), P_{i}:ℜ^{η_{i}} A_{σ(i)}→E_{i}(−1)^{∥η∥} sgn σ w(P),  (1.6)

where again ∥η∥ = ∑_{i=1}^{r} η_{i}.

By (1.6) we have written also the determinant in (1.2) as a generating function for families P = (P_{1}, P_{2}, …, P_{r}) of lattice paths, P_{i} : ℜ^{η_{i}}A_{σ(i)} → E_{i}, for some σ ∈ 𝔖_{r} and η ∈ {0, 1}^{r}. The only difference to (1.4) is that the set of steps now is S_{2} instead of S_{1}. Again, let us call σ the permutation associated to P and η the reflection indicator associated to P. Also here, we shall construct a sign-reversing (with respect to (−1)^{∥η∥} sgn σ) and weight-preserving (with respect to w) involution on the set of all families P = (P_{1}, P_{2}, …, P_{r}) of lattice paths that were described above, which are either intersecting or contain a path that touches the y-axis. Once this is done, similar arguments as those in the proof of (1.1) show that (1.2) would be established.

Now we define the involution, which we denote by Θ_{2}. Let P = (P_{1}, P_{2}, …, P_{r}) be a family of lattice paths, P_{i} : ℜ^{η_{i}}A_{σ(i)} → E_{i}, for some σ ∈ 𝔖_{r} and η ∈ {0, 1}^{r}, which is either intersecting or contains a path that touches the y-axis. As before, first consider all meeting points of any path of P with the y-axis. Let M be the highest of these meeting points. Among the paths which go through M choose P_{I} with I being minimal. Again, note that the y-coordinate of M must be even. Now, to P_{I}’s initial portion up to M we apply the following modified reflection in the y-axis (see Figure 6). Beginning from the starting point of P_{I} up to M consider the portions of P_{I} which lie between the horizontal lines y = 2j − 2 and y = 2j, portions of P_{I} on the line y = 2j −2 excluded while portions on y = 2j included. If in this portion there is a vertical step followed by n backward horizontal steps and then a vertical step followed by m forward horizontal steps (note that the vertical steps are obligatory) replace it by a vertical step followed by m backward horizontal steps and a vertical step followed by n forward horizontal steps. What is obtained by this procedure is joined with the terminal portion of P_{I} beginning from M. In Figure 6 the circled points indicate where the paths are cut into portions according to the above description.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....} • • • ∘ ∘ ℜ^{η_{I}} A_{σ(I)} M  E_{I} P_{I}  ⟶  _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....} •  • • ∘ ∘ ℜ^{1−η_{I}} A_{σ(I)} M  E_{I} P′_{I} Figure 6

If none of the paths of P meet the y-axis consider all meeting points between any two paths of P. Choose the highest meeting points, and among those the left-most meeting point, and then apply the Gessel–Viennot interchanging procedure, as was described before in the proof of (1.1).

Again it is easy to see that in both cases, by application of Θ_{2} to Θ_{2}(P), one arrives at P again. Consequently Θ_{2} is a sign-reversing (with respect to (−1)^{∥η∥} sgn σ) and weight-reversing (with respect to w) involution. □

References

1. A. Berele, A Schensted-type correspondence for the symplectic group, J. Combin. Theory Ser. A 43 (1986), 320–328.

2. F. Brenti, Determinants of super-Schur functions, lattice paths, and dotted plane partitions, Adv. in Math. 98 (1993), 27–64.

3. F. Brenti, Combinatorics and total positivity, preprint.

4. D. M. Bressoud and S.-Y. Wei, Determinental formulae for complete symmetric functions, J. Combin. Theory Ser. A 60 (1992), 277–286.

5. 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.

6. L. Comtet, Advanced Combinatorics, D. Reidel, Dordrecht, Holland, 1974.

7. A. Conca, Gröbner bases of ideals of minors of a symmetric matrix, J. Algebra (to appear).

8. A. Conca, Ladder determinantal rings, preprint.

9. A. Conca and J. Herzog, On the Hilbert function of determinantal rings and their canonical module, Proc. Amer. Math. Soc. (to appear).

10. M. Desainte–Catherine and G. Viennot, Enumeration of certain Young tableaux with bounded height, Combinatoire énumérative (G. Labelle, P. Leroux, eds.), Springer–Verlag, Berlin, Heidelberg, New York, 1986, pp. 58—67.

11. W. F. Doran, A connection between alternating sign matrices and totally symmetric self-com-plementary plane partitions, J. Combin. Theory Ser. A 64, 265–288.

12. M. Fulmek and C. Krattenthaler, Lattice path proofs for determinant formulas for symplectic and orthogonal characters, preprint.

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

14. I. M. Gessel and C. Krattenthaler, Cylindric partitions, preprint.

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

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

17. C. Greene, Proof of a conjecture on immanents of the Jacobi–Trudi matrix, Linear Algebra Appl. 171 (1992), 65–79.

18. J. Herzog and N. V. Trung, Gröbner bases and multiplicity of determinantal and Pfaffian ideals, Adv. in Math. 96 (1992), 1–37.

19. C. Krattenthaler, Non-crossing two-rowed arrays and summations for Schur functions, Proc. of the 5th Conference on Formal Power Series and Algebraic Combinatorics, Florence, 1993 (A. Barlotti, M. Delest, R. Pinzani, eds.), D.S.I., Università di Firenze, 1993, pp. 301–314.

20. C. Krattenthaler, Non-crossing two-rowed arrays, in preparation.

21. C. Krattenthaler, The major counting of nonintersecting lattice paths and generating functions for tableaux, to appear in Mem. Amer. Math. Soc..

22. C. Krattenthaler and S. G. Mohanty, Counting tableaux with row and column bounds, Proceedings of the 4th Colloque de Series Formelles et Combinatoire Algebrique, Montreal 1992 (P. Leroux, C. Reutenauer, eds.), LaCIM, Université Québec à Montréal, 1992, pp. 271–282.

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

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

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

26. M. R. Modak, Combinatorial meaning of the coefficients of a Hilbert polynomial, Proc. Indian Acad. Sci. (Math. Sci.) 102 (1992), 93–123.

27. S. Okada, Partially strict shifted plane partitions, J. Combin. Theory Ser. A 53 (1990), 143–156.

28. S. Okada, A Robinson–Schensted-type algorithm for SO(2n, ℂ), J. Algebra 143 (1991), 334–372.

29. J. B. Remmel and R. Whitney, A bijective proof of the hook formula for the number of column-strict tableaux with bounded entries, Europ. J. Combin. 4 (1983), 45–63.

30. J. B. Remmel and R. Whitney, A bijective proof of the generating function for the number of reverse plane partitions via lattice paths, Linear and Multilinear Algebra 16 (1984), 75–91.

31. 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.

32. B. E. Sagan, The ubiquitous Young tableau, Invariant theory and tableaux (D. Stanton, ed.), The IMA Volumes in Math. And Its Appl., Vol. 19, Springer–Verlag, New York, Berlin, Heidelberg, 1989, pp. 262–298.

33. B. E. Sagan, Log concave sequences of symmetric functions and analogs of the Jacobi–Trudi determinants, Trans. Amer. Math. Soc. 329 (1992), 795–811.

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

35. J. R. Stembridge, The enumeration of totally symmetric plane partitions, preprint.

36. R. A. Sulanke, A determinant for q-counting lattice paths, Discrete Math. 81 (1990), 91–96.

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

38. K. Ueno, Lattice path proof of the ribbon determinant formula for Schur functions, Nagoya Math. J. 124 (1991), 55–59.

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.