A BIJECTIVE PROOF OF THE HOOK-CONTENT

FORMULA FOR SUPER SCHUR FUNCTIONS

AND A MODIFIED JEU DE TAQUIN

C. Krattenthaler^{†}

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

Submitted: February 6, 1995; Accepted: July 25, 1995

Dedicated to Dominique Foata

Abstract. A bijective proof of the product formula for the principal specialization of super Schur functions (also called hook Schur functions) is given using the combinatorial description of super Schur functions in terms of certain tableaux due to Berele and Regev. Our bijective proof is based on the Hillman–Grassl algorithm and a modified version of Schützenberger’s jeu de taquin. We then explore the relationship between our modified jeu de taquin and a modified jeu de taquin by Goulden and Greene. We define a common extension and prove an invariance property for it, thus discovering that both modified jeu de taquins are, though different, equivalent.

1. Introduction. Let λ be a partition, i.e. λ = (λ_{1}, λ_{2}, …, λ_{r}) is a sequence of integers with λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{r} > 0. The super Schur function S_{λ}(x, y) (or hook Schur function), where x = (x_{1}, x_{2}, …) and y = (y_{1}, y_{2}, …) are two sequences of indeterminates, is defined by

S_{λ}(x, y) = det_{1≤i,j≤r}(S_{λ_{i}−i+j}(x, y)),  (1.1)

where the series S_{m}(x, y) are determined by their generating function

∑_{m≥0} S_{m}(x, y)z^{m} = ∏_{i≥1} \frac{1 + y_{i}z}{1 − x_{i}z} .  (1.2)

1991 Mathematics Subject Classification. Primary 05A15; Secondary 05A17, 05A30, 05E10, 05E15, 11P81.

Key words and phrases. Plane partitions, tableaux, hook-content formula, Hillman–Grassl algorithm, jeu de taquin, super Schur function. †Supported in part by EC’s Human Capital and Mobility Program, grant CHRX-CT93-0400 and the Austrian Science Foundation FWF, grant P10191-PHY

Super Schur functions appear naturally in the representation theory of Lie superalgebras (cf. [2, 3, 9, 10, 11, 17]), and were also discovered independently under the name of supersymmetric polynomials [14].

In order to be able to state the formula alluded to in the title, we have to recall some basic notions from partition theory. The Ferrers diagram of a partition λ = (λ_{1}, λ_{2}, …, λ_{r}) is an array of cells with r left-justified rows and λ_{i} cells in row i. Figure 1.a shows the Ferrers diagram corresponding to (4, 3, 3, 1). The conjugate of λ is the partition (λ′_{1}, …, λ′_{λ_{1}}) where λ′_{j} is the length of the j-th column in the Ferrers diagram of λ. We label the cell in the i-th row and j-th column of (the Ferrers diagram of) λ by the pair (i, j). Also, if we write ρ ∈ λ we mean ‘ρ is a cell of λ’. The hook length h_{ρ} of a cell ρ = (i, j) of λ is (λ_{i} − j) + (λ′_{j} − i) + 1, the number of cells in the hook of ρ, which is the set of cells that are either in the same row as ρ and to the right of ρ, or in the same column as ρ and below ρ, ρ included. The content c_{ρ} of a cell ρ = (i, j) of λ is j − i.

1 3 3 \overline{3} 2 \overline{1} \overline{3} 4 \overline{2} \overline{3} \overline{2}

a. Ferrers diagram b. super semistandard tableau

Figure 1

Now we are in the position to state the hook-content formula for the principal specialization of super Schur functions.

Theorem 1. Let λ = (λ_{1}, λ_{2}, …, λ_{r}) be a partition. For the specialization x_{i} = aq^{i}, y_{i} = bq^{i}, i = 1, 2, …, in the super Schur function S_{λ}(x, y) there holds

S_{λ}((aq, aq^{2}, aq^{3}, …), (bq, bq^{2}, bq^{3}, …)) = q^{∑_{i=1}^{r} iλ_{i}} ∏_{ρ∈λ} \frac{a + bq^{c_{ρ}}}{1 − q^{h_{ρ}}} .  (1.3)

Theorem 1 can be found, as everything about symmetric functions, in a slightly different, but equivalent form, in Macdonald’s book [13, p. 27, Ex. 5, p. 45, Ex. 3].

For our bijective proof of this hook-content formula we use the combinatorial description of super Schur functions in terms of what I call super semistandard tableaux (see section 2 for the definition), originally introduced by Berele and Regev [2] under the name of (k, l)- semistandard tableaux, a name however which does not make sense in our context. Our proof is based on the Hillman–Grassl algorithm [8] and on Schützenberger’s [18] jeu de taquin. It is inspired by our bijective proof [12] of Stanley’s hook-content formula for the generating function for column-strict reverse plane partitions of a given shape with bounded entries. Though there are quite a few similarities with [12], it turns out that the algorithms and arguments in [12] have to be adapted quite a bit in order to provide a bijective proof of (1.3).

We recall all the needed tableau and plane partition definitions in section 2. Then, in section 3, we present our bijective proof of the hook-content formula (1.3) for super Schur functions. In the appendix we carry out a complete example for our bijection. After a first version of this article was written, I discovered that a jeu de taquin procedure similar to ours already appeared in a paper by Goulden and Greene [7]. In fact, they are different algorithms, but it turns out that as mappings they are the same. We explore the relationship between the two algorithms in section 4. In order to prove the equivalence of the two algorithms, we define a joint extension of the algorithms, and establish an invariance property of the underlying modified jeu de taquin.

2. Super semistandard tableaux. Super semistandard tableaux are hybrids of column-strict reverse plane partitions and row-strict reverse plane partitions. We are going to define the latter first. Let λ = (λ_{1}, λ_{2}, …, λ_{r}) be a partition. A reverse plane partition of shape λ is a filling of the cells of (the Ferrers diagram of) λ with entries from an ordered alphabet such that the entries along rows and along columns are weakly increasing. A reverse plane partition is called column-strict if in addition columns are strictly increasing. Likewise, a reverse plane partition is called row-strict if rows are strictly increasing. We will also consider skew shapes for row-strict reverse plane partitions and column-strict reverse plane partitions. If λ and μ are two partitions with λ ≥ μ (i.e. the Ferrers diagram of μ is contained in the Ferrers diagram of λ), then the skew shape λ/μ consists of all cells that are contained in λ but not in μ. As expected, by a row-strict (respectively column-strict) reverse plane partition of shape λ/μ we mean a filling of the cells of λ/μ with entries from some ordered alphabet such that columns (respectively rows) are weakly increasing and rows (respectively columns) are strictly increasing.

Now, a super semistandard tableau of shape λ is a filling S of the cells of λ with entries from the ordered alphabet 1 < 2 < 3 < ⋯ < \overline{1} < \overline{2} < \overline{3} < ⋯ such that (SST1) the unbarred entries form a column-strict reverse plane partition of some shape ν,

where ν is a partition, (SST2) the barred entries form a row-strict reverse plane partition of shape λ/ν. Figure 1.b shows a super semistandard tableau of shape (4, 3, 3, 1). We call the part of a super semistandard tableau S that is occupied by the unbarred entries the inner part of S and denote it by S^{I}. Likewise, we call the part of S that is occupied by the barred entries the outer part of S and denote it by S^{O}.

The combinatorial interpretation of the super Schur function S_{λ}(x, y) is (here SST is short for ‘super semistandard tableau’)

S_{λ}(x, y) = _{∑_{S a SST} ; of shape λ} ∏_{i≥1} x_{i}^{#i’s in S}y_{i}^{#ī’s in S},  (2.1)

which can be proven combinatorially by the Gessel–Viennot method [5, 6] of nonintersecting lattice paths as shown by Remmel [15, sec. 5] (see also Brenti [4, Theorem 3.4]).

For convenience, we introduce the following two terms. Given any filling P (a super semistandard tableau, or a reverse plane partition, or …) of some (possibly skew) shape, we write P_{ρ}, respectively \overline{P_{ρ}}, for the entry in cell ρ of P, depending on whether we mean the unbarred or barred integer, respectively. Also, we call the sum of all the entries of P (forgetting about all the bars when taking the sum) the norm of P, and denote it by n(P). For example, the norm of the super semistandard tableau in Figure 1.b is 27.

3. Bijective proof of the hook-content formula for super Schur functions. In view of (2.1), our bijective proof of the hook-content formula (1.3) will consist of proving

∑_{S a SST} ; of shapeλa^{|S^{I}|}b^{|S^{O}|}q^{n(S)} = q^{∑_{i=1}^{r} iλ_{i}} ∏_{ρ∈λ} \frac{1}{1 − q^{h_{ρ}}} ∏_{ρ∈λ}(a + bq^{c_{ρ}})  (3.1)

bijectively, where, as expected, |S^{I}| and |S^{O}| denote the numbers of entries in the inner part and outer part of S, respectively.

While it is obvious what the combinatorial interpretation of the left-hand side of (3.1) is, we need to introduce yet a few more terms for being able to conveniently describe the right-hand side of (3.1) in combinatorial terms. We call an arbitrary filling of the cells of λ with nonnegative integers a tabloid of shape λ. We define the hook weight w_{h}(T) of a tabloid T of shape λ by ∑_{ρ∈λ} T_{ρ} · h_{ρ}. Furthermore, we call a filling of the cells of λ with only 0’s and 1’s a (0–1)-tabloid. We define the content weight w_{c}(T) of a (0–1)-tabloid T by ∑_{ρ∈λ} T_{ρ} · c_{ρ}. Then the right-hand side of (3.1) is the generating function

∑ q^{n(P_{0})}q^{w_{h}(T_{R})}q^{w_{c}(U_{R})}a^{#0’s in U_{R}}b^{#1’s in U_{R}},

where the sum is over all triples (P_{0}, T_{R}, U_{R}), with P_{0} being the “minimal” column-strict reverse plane partition of shape λ with entries from 1 < 2 < 3 < ⋯, i.e. the column-strict reverse plane partition with all entries in row i equal to i for all i, with T_{R} varying over all tabloids of shape λ, and with U_{R} varying over all (0–1)-tabloids of shape λ. So the task is to set up a bijection that maps a super semistandard tableau S_{L} of shape λ to such a triple (P_{0}, T_{R}, U_{R}), such that

n(S_{L}) = n(P_{0}) + w_{h}(T_{R}) + w_{c}(U_{R})  (3.2)

and

|(S_{L})^{I}| = number of 0’s in U_{R},  and  |(S_{L})^{O}| = number of 1’s in U_{R}.  (3.3)

One step in our bijection was already done much earlier. In their celebrated paper [8], Hillman and Grassl constructed an algorithmic bijection between tabloids T_{R} of shape λ and reverse plane partitions P̃_{R} of shape λ with entries from 0 < 1 < 2 < ⋯ such that n(P̃_{R}) = w_{h}(T_{R}). If we add such a reverse plane partition P̃_{R} to P_{0} cell-wise, then we obtain a column-strict reverse plane partition P_{R} of shape λ with entries from 1 < 2 < 3 < ⋯, and we have n(P_{R}) = n(P_{0})+n(P̃_{R}) = n(P_{0})+w_{h}(T_{R}). Therefore the new task is to set up a bijection that maps a super semistandard tableau S_{L} of shape λ to a pair (P_{R}, U_{R}), where P_{R} is a column-strict reverse plane partition of shape λ with entries from 1 < 2 < 3 ⋯, and where U_{R} is a (0–1)-tabloid of shape λ, such that

n(S_{L}) = n(P_{R}) + w_{c}(U_{R})  (3.4)

and (3.3) hold.

We claim that the following algorithm performs this task.

Algorithm S. The input for the algorithm is a super semistandard tableau S_{L} of shape λ.

(S0) Set (S, U) := (S_{L}, 0), where 0 denotes the (0–1)-tabloid of shape λ with 0 in each cell.

(S1) If S does not contain any barred entry then stop. The output of the algorithm is (S, U).

Otherwise, consider all inward corner cells of the outer part S^{O} of S (which are the cells in S^{O} with left and upper neighbour cells in S^{I}). Choose all such inward corner cells that contain the minimal barred entry of S, and among all these pick the top-most, cell ω say. (Note that the minimal barred entry of S must appear in an inward corner cell of S^{O} since S^{O} is a row-strict reverse plane partition.) Replace the entry \overline{S_{ω}} in cell ω by S_{ω} − c_{ω}. (Note that we “unbarred” the entry in this cell. Also note that S_{ω} − c_{ω} might be nonpositive, which does not bother us at this point.) Call this entry special. Continue with (S2).

(S2) If the special entry, s say, does not violate (SST1), i.e. if s does not violate weak increase along rows and strict increase along columns (in the unbarred entries, of course), then continue with (S3).

If it does, then we have the following situation,

\begin{aligned}& y \\ x & s \end{aligned} ,  (3.5)

where at least one of x > s and y ≥ s holds. (One of x or y is also allowed to be actually not there.) If x > y then do the move

\begin{aligned}& y \\ s + 1 & x \end{aligned} .  (3.6)

If x ≤ y then do the move

\begin{aligned}& s − 1 \\ x & y \end{aligned} .  (3.7)

The new special entry in (3.6) is s + 1, the new special entry in (3.7) is s − 1. Repeat (S2). (Note that always after either type of move the only possible violations of increase along rows or strict increase along columns involve the new special entry and the entry to the left or/and above.)

(S3) Let S be the super semistandard tableau just obtained. (The fact that indeed a super semistandard tableau is obtained will be proved right after Example S.) If we ended up with the special entry in cell ρ then add 1 to the entry in cell ρ of U. The tabloid thus obtained is the new U. (It will be proved in Lemma S below that U is in fact a (0–1)-tabloid.) Continue with (S1). □

Example S. A complete example for Algorithm S can be found in the appendix. There we map the super semistandard tableau of shape (4, 3, 3, 1) on the left of Figure 2 to the pair on the right of Figure 2, consisting of a column-strict reverse plane partition of shape (4, 3, 3, 1) with entries from 1 < 2 < 3 < ⋯ and a (0–1)-tabloid of shape (4, 3, 3, 1), such that the weight properties (3.3) and (3.4) hold. In fact, the norm of the semistandard tableau on the left of Figure 2 is 27, while the norm of the column-strict reverse plane partition on the right is 31 and the content weight of the (0–1)-tabloid is −4, which verifies (3.4) in this case. That (3.3) holds in our example is obvious.

1 3 3 \overline{3} 2 \overline{1} \overline{3} 4 \overline{2} \overline{3} \overline{2}  ⟷ ( \begin{matrix}1 & 1 & 1 & 3 \\ 2 & 3 & 3 \\ 4 & 4 & 4 \\ 5 \end{matrix} , \begin{matrix}1 & 0 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \\ 1 \end{matrix} )

n(.) = 27
|inner part| = 5
|outer part| = 6

\begin{aligned}n(.) = 31 , w_{c}(.) & = −4 \\ #0’s & = 5 \\ #1’s & = 6 \end{aligned}

Figure 2

The appendix has to be read in the following way. First of all, ignore all double circles, and all even rows in the right columns. What the left columns show is the pair (S, U) that is obtained after each loop (S1)-(S2)-(S3). Together with the pair (S, U) a filling of the shape (4, 3, 3, 1) is displayed that shows all values S_{ρ} + c_{ρ} for all cells ρ with U_{ρ} ≠ 0. This will be important for understanding Lemma S but can be ignored for the moment. At each stage, the entry that is chosen by (S1) is circled. Then each intermediate step during the loop (S1)-(S2)-(S3) is displayed in the odd rows of the right columns. The special entry is always underlined. When a super semistandard tableau is reached, the special entry is boxed. The entry in the corresponding cell of the (0–1)-tabloid is subsequently increased by 1 in step (S3). □

It should be noticed that, aside from adding/subtracting 1 to/from the special entry, what happens from (3.5) to (3.6), respectively (3.7), is a jeu de taquin forward move (cf. [18, sec. 2; 16, pp. 120/169]).

We have to justify the claim in (S3) that when we arrive at (S3) we obtained a super semistandard tableau. We do this by induction on the number of loops (S1)-(S2)-(S3). For the induction hypothesis assume that we enter (S1) with a pair (S, U), where S is a super semistandard tableau. (This is true for our initial pair (S_{L}, 0)). It is obvious that when we arrive at (S3) that S was transformed into a filling that satisfies (SST1) (otherwise the step (S2) was not finished) and (SST2) (because the only change in the outer part, the part containing the barred entries, was to remove an entry in an inward corner cell from it and make the entry into an unbarred entry). Therefore the only problem that could arise is when the special entry in the end is ≤ 0. However, when we arrive at (S3), a special entry ≤ 0 can only occur in cell (1, 1), because otherwise step (S2) was not finished. Each loop (S1)-(S2)-(S3) of the algorithm starts with some entry \overline{S_{ω}} ≥ \overline{1} in an inward corner cell ω of the outer part S^{O} of S. It is replaced by S_{ω} − c_{ω}. Then it is (possibly) moved according to (3.6) and (3.7). It is easy to check that at each stage during performing the steps (S2), the special entry, if located in cell ρ, will equal S_{ω} − c_{ρ}. This is a property so important that it has to be recorded for later use,

(special entry in ρ) = S_{ω} − c_{ρ}.  (3.8)

Suppose we reach cell (1, 1). When we arrive at (1, 1), by (3.8) and since c_{(1,1)} = 0, our special entry has become S_{ω}. But this is ≥ 1 since \overline{S_{ω}} ≥ \overline{1}.

So we have an algorithm that maps a super semistandard tableau S_{L} to a pair (P_{R}, U_{R}), where P_{R} is a super semistandard tableau without any barred entry, or in plain words, a column-strict reverse plane partition, and where U_{R}, thanks to Lemma S (cf. the Remark after Lemma S), is a (0–1)-tabloid. Stated in different terms, the algorithm maps left-hand side objects of (3.1) to right-hand side objects of (3.1). Besides, this mapping satisfies the weight properties (3.3) and (3.4). While (3.3) is trivially satisfied, (3.4) follows from (3.8).

What remains is to establish that our algorithm is actually a bijection between left-hand side and right-hand side objects. This will be accomplished by constructing an algorithm, Algorithm S* below, that will turn out to be the inverse of Algorithm S. To motivate the definition of Algorithm S*, we note the following lemma.

Lemma S. Let (S, U) be obtained after some loop (S1)-(S2)-(S3) during Algorithm S. Suppose that the loop terminated in cell γ when reaching (S3). Then γ cannot be reached by a special entry during succeeding loops (S1)-(S2)-(S3). Also, among all cells ρ with U_{ρ} ≠ 0, γ is a cell for which the value S_{ρ} + c_{ρ} attains its maximum, and if there are several cells ρ with U_{ρ} ≠ 0 where the maximum is attained, then γ is the left-most and bottom-most of those. Besides, there holds

\overline{S_{γ} + c_{γ}} ≤ min\{entries in S^{O}\}.  (3.9)

Remark. Note that the property that γ cannot be reached by “later” special entries inductively implies that after each loop (S1)-(S2)-(S3) the tabloid U is in fact a (0–1)- tabloid.

Proof of the Lemma. We prove the assertions by induction on the number of loops (S1)-(S2)-(S3).

For the start of the induction it will suffice to recall that we start Algorithm S with the pair (S_{L}, 0), where S_{L} is a super semistandard tableau.

As induction hypothesis we assume that (S, U) is either the initial pair (S_{L}, 0), or obtained after some loop (S1)-(S2)-(S3) in which case all the assertions of the Lemma are assumed to be true. Let ω be the cell where the next loop starts, i.e. the inward corner cell of S^{O} chosen by (S1), and let ζ be the cell where this next loop terminates at (S3). Let (S̃, Ũ) be the outcome after this loop. Note that by construction the cells ρ with Ũ_{ρ} ≠ 0 are ζ and the cells with U_{ρ} ≠ 0. In particular, U_{ρ} ≠ 0 implies Ũ_{ρ} ≠ 0.

First we prove (3.9) for S̃ and ζ. By (3.8), the entry of S̃ in cell ζ is

S̃_{ζ} = S_{ω} − c_{ζ}.  (3.10)

Since by definition of (S1) we have \overline{S_{ω}} = min\{entries in S^{O}\}, this immediately implies

\overline{S̃_{ζ} + c_{ζ}} = \overline{S_{ω}} = min\{entries in S^{O}\} ≤ min\{entries in S̃^{O}\}.  (3.11)

The last inequality is due to the fact that the multiset of entries in S̃^{O} comes out of the multiset of entries in S^{O} by removing \overline{S_{ω}}. Obviously, (3.11) proves (3.9) for S̃ and ζ, as desired.

Next we prove that the cell ζ cannot be reached during a “later” loop (S1)-(S2)-(S3). We distinguish between two cases. Namely, by definition of (S1), a “later” loop (S1)-(S2)- (S3) starts either at a cell, κ say, strictly to the right of ω or weakly to the left and strictly below of ω.

In the former case, by definition of (S1) and the fact that the outer part S^{O} of S is a row-strict reverse plane partition, we have

S̃_{κ} = S_{κ} > S_{ω}.  (3.12)

Then, when performing the loop (S1)-(S2)-(S3), first \overline{S̃_{κ}} is replaced by S̃_{κ} − c_{κ} and then (possibly) moved inwards according to (3.6) and (3.7). If we want to reach ζ, we have to reach the neighbour cell to the right or the neighbour cell below first. By (3.8) we would reach the neighbour cell to the right of ζ with the special entry being equal to S̃_{κ} − (c_{ζ} + 1). By (3.12) this is ≥ S_{ω} − c_{ζ} = S̃_{ζ}, the latter equality holding because of (3.10). Therefore, by definition of (S2), the loop either already stops here or continues with an upward move (3.7), and so does not reach ζ in any case. On the other hand, if we reach the neighbour cell below ζ, by (3.8) the special entry would equal S̃_{κ} − (c_{ζ} − 1). By (3.12) this is > S_{ω} − c_{ζ} = S̃_{ζ}. Again, by definition of (S2), this says that the loop either already stops here or continues with a left move (3.6), so it cannot reach ζ in any case.

The second case is that we start our “later” loop in a cell κ that is located weakly to the left and strictly below of ω. By definition of (S1) we have

S̃_{κ} = S_{κ} ≥ S_{ω}.  (3.13)

Again, if we want to reach ζ, we have to reach either the neighbour cell to the right or the neighbour cell below of ζ first. We claim that it cannot happen that the cell to the right is reached. This would follow immediately from the following easy-to-check property of our modified forward jeu de taquin (S2): If the second “jeu de taquin path” is below the first “jeu de taquin path” somewhere, then it has to stay below from thereon. To make this precise, suppose that during the first loop the special entry, s_{1} say, went to the left by (3.7), see the left half of Figure 3. (The arrows mark the direction of move of the special entry.)

y s_{1}_{z ∗}

⟶^{first loop}^{during}
{∗← \atop y}_{z ∗}

∗ y_{z s_{2}}

during

⟶^{second loop}

∗ y {∗← \atop z}

Figure 3

Since columns are strictly increasing in the inner part, we have y < z. Suppose that during the second loop we reach the cell neighbouring y and z with a special entry s_{2}, see the right half of Figure 3. Then by definition of the algorithm we have to stop here or, if not, we are forced to move left in the next step (S2). It is our assumption that the second “jeu de taquin path” starts below the first, therefore it has to stay below always.

Now we know that the only possibility to reach cell ζ is by reaching the neighbour cell below first. However, when we reach this neighbour cell below of ζ, by (3.8) the special entry equals S̃_{κ} − (c_{ζ} − 1). By (3.13) this is > S_{ω} − c_{ζ} = S̃_{ζ}. Once more, by definition of (S2), this says that the loop either already stops here or continues with a left move (3.6), so it cannot reach ζ in any case.

Next we show that S̃_{ρ} + c_{ρ}, evaluated at cells ρ with Ũ_{ρ} ≠ 0, attains its maximal value at ζ. This is evident if (S, U) is the initial pair (S_{L}, 0), i.e. if (S̃, Ũ) is the pair obtained by applying one loop (S1)-(S2)-(S3) to (S_{L}, 0), because then ζ is the only cell with Ũ_{ζ} ≠ 0. So, let us assume that (S, U) is obtained after some loop (S1)-(S2)-(S3). Let γ be the cell where the next-to-last loop, which gave rise to (S, U), terminated at (S3).

Let ρ be any cell with Ũ_{ρ} ≠ 0. Recall that this means ρ = ζ or U_{ρ} ≠ 0. We want to show

S̃_{ρ} + c_{ρ} ≤ S̃_{ζ} + c_{ζ}.  (3.14)

If ρ = ζ then there is nothing to show. So let ρ ≠ ζ. Then we have U_{ρ} ≠ 0. By induction hypothesis for γ, we have S_{γ} + c_{γ} ≥ S_{ρ} + c_{ρ} for all cells with U_{ρ} ≠ 0. Also by induction hypothesis, we know that ρ cannot be reached during a “later” loop (S1)-(S2)- (S3), therefore we have S̃_{ρ} = S_{ρ}. And, again by induction hypothesis, (3.9) holds for S and γ. Hence we have

\overline{S_{γ} + c_{γ}} ≤ min\{entries in S^{O}\} = \overline{S_{ω}} = \overline{S̃_{ζ} + c_{ζ}},

the equalities holding because of (3.11). Combining everything, we conclude

S̃_{ρ} + c_{ρ} = S_{ρ} + c_{ρ} ≤ S_{γ} + c_{γ} ≤ S̃_{ζ} + c_{ζ},  (3.15)

which verifies (3.14).

Finally we show that ζ is the left-most and bottom-most among all cells ρ with Ũ_{ρ} ≠ 0 where S̃_{ρ} + c_{ρ} attains its maximal value. Again, this is trivially satisfied if (S, U) is the initial pair (S_{L}, 0) since then ζ is the only cell with Ũ_{ζ} ≠ 0. So, let us assume that (S, U) is obtained after some loop (S1)-(S2)-(S3). Also here, let γ be the cell where the next-to-last loop, which gave rise to (S, U), terminated at (S3). Let ρ be a cell with Ũ_{ρ} ≠ 0 where S̃_{ρ} + c_{ρ} attains its maximal value. In particular, we have

S̃_{ρ} + c_{ρ} = S̃_{ζ} + c_{ζ}.  (3.16)

Of course, nothing is to show for ρ = ζ, so we may assume ρ ≠ ζ. This implies U_{ρ} ≠ 0. We already observed that then the relations (3.15) hold. Combining (3.15) and (3.16) we are forced to conclude

S_{ρ} + c_{ρ} = S_{γ} + c_{γ} = S̃_{ζ} + c_{ζ}.  (3.17)

We shall show that ζ has to lie in the region (weakly) to the left and (weakly) below of γ. Since γ was the left-most and bottom-most of all the cells ρ with U_{ρ} ≠ 0 where the maximal value of S_{ρ} + c_{ρ} is attained, and since S_{ρ} + c_{ρ} = S̃_{ρ} + c_{ρ} for all cells with U_{ρ} ≠ 0, this would establish that ζ is the left-most and bottom-most of all the cells ρ with Ũ_{ρ} ≠ 0 where the maximal value of S̃_{ρ} + c_{ρ} is attained, as desired.

We prove the claim of the previous paragraph by excluding the other three quarter regions that are determined by the horizontal line and the vertical line running through γ.

First, suppose that ζ lies in the region strictly to the right and weakly below of γ. For these cells there holds the following basic computation. For convenience, let γ = (i_{1}, j_{1}) and ζ = (i_{2}, j_{2}), where ζ is located in this region strictly to the right and weakly below of γ, i.e. i_{1} ≤ i_{2} and j_{1} < j_{2}. Then, since the inner part S̃^{I} of S̃ is a column-strict reverse plane partition, we have

S̃_{ζ} + c_{ζ} = S̃_{ζ} + (j_{2} − i_{2})
≥ (S̃_{γ} + i_{2} − i_{1}) + (j_{2} − i_{2}) = S̃_{γ} + j_{2} − i_{1}
> S̃_{γ} + j_{1} − i_{1} = S̃_{γ} + c_{γ}.  (3.18)

This contradicts (3.17) because of S_{γ} = S̃_{γ}, which again follows from the induction hypothesis that γ cannot be reached during “later” loops (S1)-(S2)-(S3). Thus, this region is excluded.

Next we show that ζ cannot lie in the region (weakly) to the right and (weakly) above γ, γ excluded. This would follow immediately from the claim that if two successive loops (S1)-(S2)-(S3) start with the same size of entry in the inward corner cells chosen by (S1) (which applies in our case since the loop that lead to S started with an entry \overline{S_{γ} + c_{γ}} in some inward corner cell, and the loop that lead from S to S̃ started with \overline{S̃_{ζ} + c_{ζ}}, both quantities being the same by (3.17)) then the second path of moves has to stay below the first path of moves.

To check this claim, once again note that both loops started with the same size of entries in the cells chosen by (S1). By the rules in (S1), and because the outer part S^{O} of S is a row-strict reverse plane partition, this means that the second loop started strictly to the left and strictly below of the first. We already proved that our modified forward jeu de taquin (S2) has the property that if the second “jeu de taquin path” is below of the first “jeu de taquin path” somewhere, then it has to stay below from thereon. So the region (weakly) to the right and (weakly) above γ can never be reached.

Finally, we examine if ζ could be located in the region strictly to the left and weakly above of γ. Since S_{γ} = S̃_{γ}, once more the computation (3.18), with γ and ζ interchanged applies, implying S̃_{γ} +c_{γ} > S̃_{ζ} +c_{ζ}, which contradicts (3.17) because of S_{γ} = S̃_{γ}. Therefore we cannot reach the region under consideration.

This completes the proof of the Lemma. □

¿From Lemma S it is pretty obvious what the inverse algorithm of Algorithm S could be.

Algorithm S*. The input for the algorithm is a pair (P_{R}, U_{R}), where P_{R} is a columnstrict reverse plane partition of shape λ with entries from 1 < 2 < 3 < ⋯, and where U_{R} is a (0–1)-tabloid of shape λ.

(S*0) Set (S, U) := (P_{R}, U_{R}).

(S*1) If U = 0 then stop. The output of the algorithm is S.

Otherwise, consider all cells ρ with U_{ρ} ≠ 0. Among these choose the cells for which S_{ρ} + c_{ρ} is maximal, and among all these pick the left-most and bottom-most, cell ζ say. (Observe that among two different cells attaining the same value of S_{ρ} + c_{ρ} one is always weakly to the left and strictly below of the other, again because of the computation (3.18), with S̃ replaced by S. So the left-most and bottom-most of these does exist.) Replace the entry S_{ζ} in cell ζ by \overline{S_{ζ} + c_{ζ}}. (Note that we “barred” the entry.) Call this entry special. Continue with (S*2).

(S*2) If the special entry, s say, does not have a right or bottom neighbour entry that is unbarred, then continue with (S*3).

If the special entry does have a right or bottom neighbour entry that is unbarred, then we have the following situation,

\begin{matrix}s & x \\ y \end{matrix} ,  (3.19)

where at least one of x or y is an unbarred entry. (One of x or y is also allowed to be actually not there.) If x < y (in particular, this is the case if y is a barred entry) then do the move

\begin{matrix}x & s \\ y \end{matrix} .  (3.20)

If x ≥ y (in particular, this is the case if x is a barred entry) then do the move

\begin{matrix}y & x \\ s \end{matrix} .  (3.21)

The new special entry in either case is s. Repeat (S*2).

(S*3) Let S be the super semistandard tableau just obtained. (The fact that indeed a super semistandard tableau is obtained will be proved in the subsequent Lemma S*.) Replace the entry 1 in cell ζ of U by 0. The (0–1)-tabloid thus obtained is the new U. Continue with (S*1). □

Example S*. A complete example for Algorithm S* can be found in the appendix. There we map the pair on the right of Figure 2, consisting of a column-strict reverse plane partition of shape (4, 3, 3, 1) with entries from 1 < 2 < 3 < ⋯ and a (0–1)-tabloid of shape (4, 3, 3, 1), to the super semistandard tableau of shape (4, 3, 3, 1) on the left of Figure 2, such that the weight properties (3.3) and (3.4) hold. It is simply the inverse of the example for Algorithm S given in Example S. Therefore, here the appendix has to be read in the reverse direction, and in the following way. First of all, ignore all single circles, and all odd rows in the right columns. What the left columns show is the pair (S, U) that is obtained after each loop (S*1)-(S*2)-(S*3) together with a filling of the shape (4, 3, 3, 1) that shows all values S_{ρ} + c_{ρ} for all cells ρ with U_{ρ} ≠ 0. At each stage, the entry that is chosen by (S*1) is doubly circled. Then each intermediate step during the loop (S*1)-(S*2)-(S*3) is displayed in the even rows of the right columns. The special entry is always doubly underlined. When a super semistandard tableau is reached, the special entry is doubly boxed. The entry in the corresponding cell of the (0–1)-tabloid is subsequently decreased by 1 in step (S*3). □

Again, it should be noticed that (3.20) and (3.21) are exactly jeu de taquin backward moves (cf. [18, sec. 2; 16, pp. 120/169]), which reverse the forward moves (3.6) and (3.7), respectively, except for the subtraction/addition of 1 in (3.6) and (3.7).

In order to show that Algorithm S* is always well-defined, we have to confirm that when arriving at (S*3) we always obtained a super semistandard tableau. This is established in the following lemma. Besides, this lemma contains the facts about Algorithm S* that are needed to prove that the Algorithms S and S* are inverses of each other.

Lemma S*. Let (S, U) be obtained after some loop (S*1)-(S*2)-(S*3) during Algorithm S*. Then for all cells ρ with U_{ρ} ≠ 0 there holds

\overline{S_{ρ} + c_{ρ}} ≤ min\{entries in S^{O}\}.  (3.22)

Also, S is a super semistandard tableau. Besides, if ω is the inward corner cell of S^{O} that contained the special entry at the end of the loop (S*1)-(S*2)-(S*3) that lead to S, then ω is the top-most inward corner cell of S^{O} that contains the minimal entry of S^{O}.

Proof. We prove the assertions by induction on the number of loops (S*1)-(S*2)- (S*3). To be precise, we prove the following (slightly stronger) statement inductively: All the assertions of the Lemma hold. Besides, during the loop (S*1)-(S*2)-(S*3) that leads to (S, U) the special entry never occupies a cell ρ with U_{ρ} ≠ 0.

To begin with, we know that when we start with Algorithm S* we have a pair (S, U), where S is a super semistandard tableau (since S = P_{R} is a column-strict reverse plane partition in 1 < 2 < 3 < ⋯). Also, (3.22) is vacuously satisfied (there is no barred entry in S = P_{R}). This will suffice for the start of the induction.

As induction hypothesis let us assume that the assertions of the Lemma and the assertion that the special entry never occupies a cell ρ with U_{ρ} ≠ 0 are true for (S, U) and all preceding pairs occuring in step (S*3) during the process of the algorithm, except of course that the assertion about the inward corner cell ω and the assertion about the special entry do not hold for the initial pair (because they do not make sense for the initial pair).

Let ζ be the cell where the loop (S*1)-(S*2)-(S*3) starts from (S, U), i.e. the cell that is chosen by applying (S*1) to (S, U), and let κ be the cell where the loop stops at (S*3). Furthermore, let (S̃, Ũ) be the outcome after this loop. Then, by definition of the algorithm we have

\overline{S̃_{κ}} = \overline{S_{ζ} + c_{ζ}}.  (3.23)

Note that, also by definition of the algorithm, the cells ρ with Ũ_{ρ} ≠ 0 are those with U_{ρ} ≠ 0, excluding ζ. In particular, Ũ_{ρ} ≠ 0 implies U_{ρ} ≠ 0.

First we prove that during the loop (S*1)-(S*2)-(S*3) leading from (S, U) to (S̃, Ũ) the special entry never occupies a cell ρ with Ũ_{ρ} ≠ 0. Recall that, by definition of (S*1), the cell ζ, the cell where the loop starts, is the left-most and bottom-most cell among the cells with U_{ζ} ≠ 0 where the value S_{ζ} + c_{ζ} is maximal. Let the special entry be located in some cell ρ with Ũ_{ρ} ≠ 0, at some stage during the performance of the loop. Clearly, ρ is located (weakly) to the right and (weakly) below of ζ. Since, by definition of (S*3), we have Ũ_{ζ} = 0, cell ρ is different from ζ. If ρ were located strictly to the right of ζ, then the computation (3.18), with S̃ replaced by S, ζ replaced by ρ, and γ replaced by ζ, would imply that S_{ρ} + c_{ρ} > S_{ζ} + c_{ζ}. But this contradicts the definition of ζ. So the only other possibility is that ρ is located in the same column as ζ and strictly below ζ. Then a computation similar to (3.18) would show that S_{ρ} + c_{ρ} = S_{ζ} + c_{ζ}, which again contradicts the definition of ζ. Therefore the special entry can only meet cells ρ with Ũ_{ρ} = 0. In particular, this implies that the entries in cells ρ with Ũ_{ρ} ≠ 0 do not change during the loop. Therefore we have

S̃_{ρ} = S_{ρ}  (3.24)

for all cells ρ with Ũ_{ρ} ≠ 0.

Now we prove (3.22) for S̃. Let ρ be any cell with Ũ_{ρ} ≠ 0. This implies U_{ρ} ≠ 0. Therefore, by (3.24) and by construction of ζ in (S*1), we have

S̃_{ρ} + c_{ρ} = S_{ρ} + c_{ρ} ≤ S_{ζ} + c_{ζ}.  (3.25)

Also by construction of ζ, we have U_{ζ} ≠ 0, and hence by induction hypothesis (3.22) that \overline{S_{ζ} + c_{ζ}} ≤ min\{entries in S^{O}\}. This implies that \overline{S_{ζ} + c_{ζ}} = min\{entries in S̃^{O}\}, since the multiset of entries of S̃^{O} equals the multiset of entries in S^{O}, with the special entry \overline{S_{ζ} + c_{ζ}}, created in (S*1) and finally located in cell κ in S̃, added. Hence, (3.25) proves (3.22) with S replaced by S̃, as desired.

Now we prove that S̃ is a super semistandard tableau. By construction of Algorithm S*, the inner part S̃^{I} of S̃ automatically is a column-strict reverse plane partition. Therefore, it is only to prove that the outer part S̃^{O} of S̃ is a row-strict reverse plane partition. If \overline{S_{ζ} + c_{ζ}} < min\{entries in S^{O}\} then this assertion certainly holds, since \overline{S̃_{κ}} = \overline{S_{ζ} + c_{ζ}} is the only new entry in S̃, and it is located in an inward corner cell of S̃^{O}. Note in particular, that we are in this case at the very beginning.

By induction hypothesis, (3.22) holds for ζ, so the only other case is

\overline{S_{ζ} + c_{ζ}} = min\{entries in S^{O}\}.  (3.26)

Observe that the only difficulty arises when we reach the cell κ at the end of a loop (S*1)- (S*2)-(S*3), and the neighbour cell to the right of κ contains the entry \overline{S_{ζ} + c_{ζ}}. In this case row-strictness of the outer part S̃^{O} of S̃ would be violated. We have to show that this case cannot occur.

Let (S′, U′) be the pair preceding (S, U), i.e. (S, U) is obtained by applying one loop (S*1)-(S*2)-(S*3) to (S′, U′). As we just noted, (S′, U′) exists, since if (S, U) were the initial pair we would not be in this case. Furthermore, let γ be the cell where this loop starts, and let ω be the corner cell where it stops. By definition of the algorithm we have

\overline{S_{ω}} = \overline{S′_{γ} + c_{γ}}.  (3.27)

Now, by induction hypothesis and the definition of the algorithm, there holds

\overline{S′_{γ} + c_{γ}} = min\{entries in S^{O}\}.  (3.28)

Furthermore, there holds S′_{ζ} = S_{ζ}, since by induction hypothesis the cell ζ (which is a cell with U_{ζ} ≠ 0) was not met by the special entry during the loop (S*1)-(S*2)-(S*3) that lead from (S′, U′) to (S, U). Hence, by definition of (S*1), S′_{γ} + c_{γ} ≥ S′_{ζ} + c_{ζ} = S_{ζ} + c_{ζ}. Combining this with (3.26) and (3.28), we are forced to conclude

S′_{γ} + c_{γ} = S′_{ζ} + c_{ζ} (= S_{ζ} + c_{ζ}).  (3.29)

Therefore, again by definition of (S*1), ζ lies weakly to the right and strictly above γ.

It is an easy-to-check property of backward jeu de taquin (S*2) that if the second “jeu de taquin path” is above the first “jeu de taquin path” somewhere, then it has to stay above from thereon. To be precise, suppose that during the first loop (S*1)-(S*2)-(S*3) the special entry, s_{1} say, went to the right by (3.20), see the left half of Figure 4. (Again, the arrows mark the direction of move of the special entry.)

∗ y_{s_{1} z}

⟶^{first loop}^{during}
∗ y {z→ \atop ∗}

s_{2} y_{z ∗}

during

⟶^{second loop}

{y→ \atop ∗}_{z ∗}

Figure 4

Since columns are strictly increasing in the inner part, we have y < z. Suppose that during the second loop we reach the cell neighbouring y and z with a special entry s_{2}, see the right half of Figure 4. Then by definition of the algorithm we have to stop here or, if not, we are forced to move right in the next step (S*2).

We know that the second “jeu de taquin path” starts at ζ, which is weakly to the right and strictly above of γ, the starting cell of the first “jeu de taquin path”. Therefore the second path has to stay above the first path always. Hence κ, the cell where the second path terminates, cannot be the left neighbour cell of ω. Therefore, κ is in a row above ω. By induction hypothesis, ω is the top-most inward corner cell of S^{O} that contains the minimal entry of S^{O}. This implies that the cell to the right of κ contains and entry that is > \overline{S_{ω}} = \overline{S̃_{κ}}, the equality following from a combination of (3.27), (3.29), and (3.23). As noted above, this guarantees that S̃ is a super semistandard tableau.

Finally, we prove that κ is the top-most inward corner cell in S̃^{O} that contains the minimal entry in S̃^{O}. This is trivially true if \overline{S_{ζ} + c_{ζ}} < min\{entries in S^{O}\}, again by remembering (3.23). Note that this inequality is in particular true at the very beginning of Algorithm S*. Because of the induction hypothesis (3.22), the only other case is \overline{S_{ζ} + c_{ζ}} = min{entries in S^{O}}. Since we are not at the very beginning, we are allowed to assume that this last assertion of Lemma S* holds for S and ω. However, we already considered the case \overline{S_{ζ} + c_{ζ}} = min\{entries in S^{O}\} before (see (3.26)) and showed that the “jeu de taquin path” leading from ζ to κ has to stay above of the “jeu de taquin path” leading from γ to ω. Hence κ is strictly above ω. By induction hypothesis, ω was the top-most corner cell containing the minimal entry of S^{O}. So κ, which by (3.23) contains \overline{S_{ζ} + c_{ζ}} = min\{entries in S^{O}\} in S̃, is the top-most corner cell of S̃ containing min{entries in S̃^{O}} (= min{entries in S^{O}}), as desired.

This completes the proof of the Lemma. □

¿From Lemmas 1 and 2 it is abundantly clear that the Algorithms S and S* are inverses of each other. This finishes the bijective proof of (3.1).

4. More on modified jeu de taquin. In this section we explore the relations between our modified jeu de taquin in Algorithm S and a modified jeu de taquin in a paper of Goulden and Greene [7, sec. 3]. The main result of this section is an invariance property (Theorem SG) of modified jeu de taquin, which somehow is the analogue of the invariance of standard jeu de taquin (see [18; 16, Theorem 3.9.7]).

Super Schur functions are also defined for skew shapes λ/μ. For the purposes of this section, we assume that x and y are doubly infinite sequences of variables, x = (…, x_{−1}, x_{0}, x_{1}, …) and y = (…, y_{−1}, y_{0}, y_{1}, …). Then, the skew super Schur function S_{λ/μ}(x, y) is defined by

S_{λ/μ}(x, y) = det_{1≤i,j≤r}(S_{λ_{i}−i−μ_{j}+j}(x, y)),  (4.1)

where the series S_{m}(x, y) are determined by their generating function

∑_{m≥0} S_{m}(x, y)z^{m} = ∏_{i=−∞}^{∞} \frac{1 + y_{i}z}{1 − x_{i}z} ,

(note the difference to (1.2) in the range of the product). The combinatorial description (2.1) extends to skew super Schur functions. Namely, if we extend the definition of super semistandard tableau by saying that it is a filling of some skew shape with entries from the ordered alphabet ⋯ < −1 < 0 < 1 < ⋯ < \overline{−1} < \overline{0} < \overline{1} < ⋯ satisfying (SST1) (but the shape ν replaced by ν/μ) and (SST2), then (again SST is short for ‘super semistandard tableau’)

S_{λ/μ}(x, y) = _{∑_{S a SST} of shape λ/μ} ∏_{i=−∞}^{∞} x_{i}^{#i’s in S}y_{i}^{#ī’s in S}.  (4.2)

As in the nonskew case (4.2) can be proven combinatorially by the Gessel–Viennot method of nonintersecting lattice paths, see [15, sec. 5; 4, Theorem 3.4].

Algorithm S was defined for super semistandard tableaux of a nonskew shape λ. However, everything can be defined and works fine also for a skew shape λ/μ. To be precise, it is readily checked that Algorithm S for a skew shape λ/μ proves the following alternative combinatorial desription for (skew) super Schur functions due to Goulden and Greene [7, Theorem 1.1] (here CRPP is short for column-strict reverse plane partition with integer entries)

S_{λ/μ}(x, y) = _{∑_{P a CRPP} of shape λ/μ} ∏_{ρ∈λ/μ}(x_{P_{ρ}} + y_{P_{ρ}+c_{ρ}}).  (4.3)

(In fact, we needed the restriction of a nonskew shape only at one place, namely, in the second paragraph after Example S, when showing that all the entries are at least 1 when arriving at (S3). But now we are considering alphabets that are unbounded above and below, so this step is superfluous in this context.) Goulden and Greene also construct a bijection for proving that the representations (4.2) and (4.3) for S_{λ/μ}(x, y) agree. This bijection is based on a generalization of Bender and Knuth’s involution [1, pp. 46/47; 16, pp. 152/153] that proves the symmetry of Schur functions combinatorially. In passing, they provide (without proof) an alternative description of this bijection, in terms of a jeu de taquin-like procedure. Though similar, this procedure is different from ours. To understand the relationship between the two procedures, we introduce a nondeterministic jeu de taquin procedure which contains both Algorithm S and Goulden and Greene’s algorithm as special cases.

The following (nondeterministic) algorithm maps a super semistandard tableau S of shape λ/μ to an array A of shape λ/μ containing unbarred and barred positive integers such that (A1) the multiset of entries in S and A agree, (A2) if in A each barred entry, ȳ say, contained in cell ρ, is replaced by y − c_{ρ}, then A

becomes a column-strict reverse plane partition. It should be observed that such an array A is exactly equivalent to a pair (P, U) of a column-strict reverse plane partition P and a (0–1)-tabloid U, the latter pairs occuring as output of Algorithm S. Given such an array A the corresponding pair (P, U) is obtained by defining P to be the column-strict reverse plane partition constructed in (A2) above, and by defining U to be the (0–1)-tabloid with 1 in each cell that contains a barred entry in A and with 0 in each cell that contains an unbarred entry in A. Clearly, this correspondence is a bijection.

Algorithm SG. The input for the algorithm is a super semistandard tableau S of shape λ/μ.

(SG0) Set A := S.

(SG1) Consider all pairs (x_{1}, ȳ_{1}), where x_{1} is an unbarred entry and ȳ_{1} is a barred entry located in cell ρ_{1}, x_{1} being the left neighbour of ȳ_{1}, and all pairs (x_{2}, ȳ_{2}), where x_{2} is an unbarred entry and ȳ_{2} is a barred entry located in cell ρ_{2}, x_{2} being the top neighbour of ȳ_{2}. If for all such pairs there holds

x_{1} ≤ y_{1} − c_{ρ_{1}}  (4.4)

and

x_{2} < y_{2} − c_{ρ_{2}},  (4.5)

then stop. The output of the algorithm is A. (Observe that (4.4) and (4.5) are required for A to satisfy property (A2) above.)

Otherwise, do one of the following two steps B or U.

B. Consider all violations of (4.4) or (4.5). Let ȳ be the top-most among the minimal barred entries involved. (From Lemma 1, (2), it will follow that ȳ is unique.) Let ȳ be located in cell ρ. Then we have the following situation,

\begin{aligned}& x_{t} \\ x_{l} & ȳ \end{aligned} ,  (4.6)

where at least one of x_{l} > y − c_{ρ} and x_{t} ≥ y − c_{ρ} holds. (One of x_{l} or x_{t} is also allowed to be actually not there, or, in abuse of notation, to be a barred entry. In the latter case, by convention the corresponding inequality does not hold.) If x_{l} > x_{t} (or if x_{t} is a barred entry) then do the move

\begin{aligned}& x_{t} \\ ȳ & x_{l} \end{aligned} .  (4.7)

If x_{l} ≤ x_{t} (or if x_{l} is a barred entry) then do the move

ȳ ; x_{l} x_{t} .  (4.8)

U. Consider all violations of (4.4) or (4.5). Let x be the right-most among the maximal unbarred entries involved. (From Lemma 1, (1), it will follow that x is unique.) Let the cell to the right of x be ρ_{r} and the cell below of x be ρ_{b}. Then we have the following situation,

x ȳ_{r} ; ȳ_{b} ,  (4.9)

where at least one of x > y_{r} − c_{ρ_{r}} and x ≥ y_{b} − c_{ρ_{b}} holds. (One of ȳ_{r} or ȳ_{b} is also allowed to be actually not there, or, in abuse of notation, to be an unbarred entry. In the latter case, by convention the corresponding inequality does not hold.) If ȳ_{r} ≤ ȳ_{b} (or if ȳ_{b} is an unbarred entry) then do the move

ȳ_{r} x ; ȳ_{b} .  (4.10)

If ȳ_{r} > ȳ_{b} (or if ȳ_{r} is an unbarred entry) then do the move

\begin{matrix}ȳ_{b} & ȳ_{r} \\ x \end{matrix} .  (4.11)

Let the new A be the array of shape λ/μ just obtained. Repeat (SG1). □

The output of the algorithm trivially satisfies condition (A1) above. It will follow from Lemma 1 that the output also satisfies (A2), see the Remark after Lemma 1.

It is an easy observation that when always choosing step B in Algorithm SG we basically do the same as in Algorithm S. The only difference is that in Algorithm SG we do not subtract the content from the barred entries and keep the barred entries as such, unlike in Algorithm S. The translation of an output of Algorithm SG into the corresponding output of Algorithm S was described in the paragraph preceding the description of Algorithm SG. Similarly, when always choosing step U in Algorithm SG we (basically) do the same as in Goulden and Greene’s algorithm. So, roughly speaking, what we do in Algorithm S is to move the barred entries, one after the other, “into” the unbarred entries, while Goulden and Greene move the unbarred entries, one after the other, “into” the barred entries. Nevertheless, both procedures turn out to be equivalent, i.e. the final result is the same in both cases. In fact, the main result of this section (Theorem SG below) is that, regardless which choices we take in step (SG1), the final result will be the same. Therefore, though Goulden and Greene write that, unlike the standard jeu de taquin, their algorithm is deterministic and different sequences of moves may give different results, there is some freedom in choosing the order of moves. But there is not as much freedom as in standard jeu de taquin where there is complete freedom.

Theorem SG. The output of Algorithm SG applied to some given super semistandard tableau S is independent of the choices between B and U that are taken in step (SG1).

The proof of Theorem SG is based on the following two Lemmas.

Lemma 1. After each application of (SG1) during Algorithm SG, the obtained array A has the following properties.

(1) Let x be an unbarred entry located (weakly) to the left and (weakly) above the unbarred entry y. Then x ≤ y. Also, each column is strictly increasing in the unbarred entries.

(2) Let x̄ be a barred entry located (weakly) to the left and (weakly) above the barred entry ȳ. Then x̄ ≤ ȳ. Also, each row is strictly increasing in the barred entries.

(3) For all pairs (x̄_{1}, y_{1}), where x̄_{1} is a barred entry located in cell ρ_{1} and y_{1} is an unbarred entry, x̄_{1} being the left neighbour of y_{1}, there holds

x_{1} − c_{ρ_{1}} ≤ y_{1}.  (4.12)

For all pairs (x̄_{2}, y_{2}), where x̄_{2} is a barred entry located in cell ρ_{2} and y_{2} is an unbarred entry, x̄_{2} being the top neighbour of y_{2}, there holds

x_{2} − c_{ρ_{2}} < y_{2}.  (4.13)

Remark. Clearly, this implies that the output of Algorithm SG satisfies (A2). For, in addition to the properties (1)–(3) of the Lemma, the output satisfies also (4.4) and (4.5) since otherwise the step (SG1) was not finished.

Proof. We prove the Lemma by induction on the number of applications of (SG1). The claim of the Lemma is certainly true at the very beginning since we start with a super semistandard tableau.

For the induction step a careful case-by-case analysis has to be performed. We consider just one case out of four (two cases each for steps B and U, depending on whether moving horizontally or vertically), the others are similar.

Suppose that by performing step U, (4.11), an unbarred entry, x say, is moved down one row. Figure 5 displays the generic situation before and after the move. Here, m, n, s, t can be any nonnegative integers.

cell ρ /_{cell ω} \ \begin{matrix}… b̄ x_{−m} … x_{−2} x_{−1} & x & x_{1} x_{2} … x_{s} z̄… \\ … a ȳ_{−n} … ȳ_{−2} ȳ_{−1} & ȳ & ȳ_{1} ȳ_{2} … ȳ_{t} u … \end{matrix}  ^{cell ρ} /_{cell ω} \ \begin{matrix}… b̄ x_{−m} … x_{−2} x_{−1} & ȳ & x_{1} x_{2} … x_{s} z̄… \\ … a ȳ_{−n} … ȳ_{−2} ȳ_{−1} & x & ȳ_{1} ȳ_{2} … ȳ_{t} u … \end{matrix}

a. before the move b. after the move

Figure 5

The pictures have to be taken symbolically in the sense that all combinations of n > m or n ≤ m, and s > t or s ≤ t are possible.

By definition of step U, x is the right-most among the maximal unbarred entries that violate (4.4) or (4.5) in Figure 5.a. Moreover, since we moved down by (4.11), we have (for the definition of ω see Figure 5)

x ≥ y − c_{ω}.  (4.14)

Of course, by induction hypothesis, nothing has to be shown for entries that did not move. In fact, it suffices to prove

ad (1): a ≤ x ≤ u  (4.15)
ad (2): b̄ < ȳ < z̄  (4.16)
ad (3): y − c_{ρ} < x, y − c_{ρ} ≤ x_{1} and y_{−1} − c_{ω_{−1}} ≤ x,  (4.17)

where we assume that ȳ_{i} is located in cell ω_{i}, i = −n, …, −1, 1, …, t.

In order to prove a ≤ x, we distinguish between two cases. First suppose a > y_{−n}−c_{ω_{−n}}. This is a violation of (4.4). Since x is the right-most among the maximal unbarred entries that violate (4.4) or (4.5) in Figure 5.a, we must have x ≥ a. On the other hand, suppose a ≤ y_{−n} − c_{ω_{−n}}. Then, by induction hypothesis (2) (applied to Figure 5.a of course), and by (4.14), we have

a ≤ y_{−n} − c_{ω_{−n}} ≤ y_{−n+1} − c_{ω_{−n+1}} ≤ ⋯ ≤ y_{−1} − c_{ω_{−1}} ≤ y − c_{ω} ≤ x.

The inequality x ≤ u follows from the induction hypothesis (1).

For proving b̄ < ȳ, we first note that by induction hypothesis (2) we have b̄ ≤ ȳ. So, we only have to show that b̄ ≠ ȳ. By way of contradiction, let us assume b̄ = ȳ. Then, by induction hypothesis (2), it is impossible that there are any barred entries to the left of ȳ in Figure 5.a. This means that n = 0, and that a is the left neighbour of ȳ in Figure 5.a. At the very beginning the entry b̄ was strictly above and weakly to the right of the entry ȳ, because otherwise b̄ and ȳ would have been in the same row at some stage, contradicting induction hypothesis (2). For similar reasons it is impossible that a rectangle determined by b̄ as its top-left corner and ȳ as its bottom-right corner contained another barred entry at any time. Finally, because of the argument visualized in Figure 3, the path of entry ȳ always stays below the path of entry b̄. Therefore b̄ must have passed all the way through from cell ρ to the cell that it is now occupying in Figure 5. Moreover, x_{−m}, …, x_{−1}, x and a did not move after b̄ passed through. But then, at some point, we must have considered the situation

\begin{matrix}x & b̄ \\ a \end{matrix}

before. By induction hypothesis (1), this implies x < a. This contradicts x ≥ a which was already established.

Next we show ȳ < z̄. Let z̄ be located in cell ζ. If s = 0, i.e. if z̄ is the right neighbour of x in Figure 5.a, then ȳ < z̄ holds by definition of step U, (4.11). If s > 0, then we must have x_{s} ≤ z − c_{ζ}. For, otherwise (4.4) would be violated. Besides, by induction hypothesis (1) we have x ≤ x_{s}, and so x would not be the right-most among the maximal unbarred entries that violate (4.4) or (4.5) in Figure 5.a. Combining this with (4.14), we conclude y − c_{ω} ≤ x ≤ x_{s} ≤ z − c_{ζ} and hence y ≤ z − s − 2 < z.

All three inequalities in (4.17) follow directly from (4.14), x ≤ x_{1}, and ȳ_{−1} < ȳ, the latter two being due to the induction hypothesis (1), (2). □

Lemma 2. Suppose that A is an array satisfying (1)–(3) in Lemma 1. Furthermore suppose that the right-most among the maximal unbarred entries that violate (4.4) or (4.5) is not the left or top neighbour of the top-most among the minimal barred entries that violate (4.4) or (4.5). Then the steps U and B commute,

U(B(A)) = B(U(A)).

Proof. This is established by a straight-forward case-by-case analysis, utilizing Lemma 1. □

Finally we are in the position to prove Theorem SG.

Proof of Theorem SG. Suppose that during Algorithm SG we applied the sequence W (U, B) of steps U and B to the initial semistandard tableau S. One should think of W (U, B) as a word in U’s and B’s. Let the length of W (U, B) be L. We shall show that

W (U, B)(S) = B^{L}(S),  (4.18)

i.e. that the result is the same when we apply step B all the time (which is basically the same as Algorithm S, as we already noted). Clearly this would suffice to prove the Theorem.

We establish (4.18) by successively changing U’s in W (U, B) into B’s and by applying the commutation rule in Lemma 2. First we claim that there is a word W_{1}(U, B) such that

W (U, B)(S) = B W_{1}(U, B)(S).  (4.19)

This is trivially true if W (U, B) already has the form B W_{1}(U, B). So let us assume that W (U, B) has the form U W_{1}(U, B). Consider the array W_{1}(U, B)(S), the array obtained before the final step. Since W (U, B)(S) = U W_{1}(U, B)(S) satisfies (4.4) and (4.5), it is obvious that the right-most among the maximal unbarred entries that violate (4.4) or (4.5) in W_{1}(U, B)(S) is the left or top neighbour of the top-most among the minimal barred entries that violate (4.4) or (4.5) in W_{1}(U, B)(S). Hence, it does not make any difference whether we apply U or B to W_{1}(U, B)(S). This settles (4.19) also in this case.

Now we use the commutation rule in Lemma 2 to move the left B in the right-hand side of (4.19) inside the word W_{1}(U, B). The only problem arises, when we arrive at W_{2}(U, B) B U W_{3}(U, B)(S), where W_{3}(U, B)(S) is an array in which the right-most among the maximal unbarred entries that violate (4.4) or (4.5) is the left or top neighbour of the top-most among the minimal barred entries that violate (4.4) or (4.5). In this case Lemma 2 does not apply. But then we have U W_{3}(U, B)(S) = B W_{3}(U, B)(S), and therefore

W (U, B)(S) = W_{2}(U, B) B B W_{3}(U, B).  (4.20)

We continue by moving this “new” B inside the word W_{3}(U, B), until we arrive at

W (U, B)(S) = (W_{4}(U, B) B)(S),  (4.21)

for some word W_{4}(U, B). By iterating the process (4.19)-(4.20)-(4.21) we finally obtain (4.18). □

Acknowledgement. This work was carried out while the author visited the University of California at San Diego. He thanks the University of California and in particular Adriano Garsia for making this visit possible. Besides, he is indebted to Adriano Garsia for drawing his attention to the problem of finding “nice” combinatorial proofs of hook formulas.

Appendix. The appendix contains a complete example for Algorithms S and S* for λ = (4, 3, 3, 1), setting up a mapping between the two sides of Figure 2. See the specific descriptions given in Examples 1 and 2 of how to read the following tables.

1 3 3 \overline{3} 2 \overline{1} \overline{3} 4 \overline{2} \overline{3} \overline{2} 0 0 0 0 0 0 0 0 0 0 0  \underrightarrow{(S1)} 1 3 3 \overline{3} 2 \underline{1} \overline{3} 4 \overline{2} \overline{3} \overline{2} \underrightarrow{(3.7)} 1 \underline{0} 3 \overline{3} 2 3 \overline{3} 4 \overline{2} \overline{3} \overline{2} \underrightarrow{(3.6)} 1 1 3 \overline{3} 2 3 \overline{3} 4 \overline{2} \overline{3} \overline{2} \underrightarrow{(S3)}

\begin{matrix}− & − & − & − \\ − & − & − \\ − & − & − \\ − \end{matrix} \underleftarrow{(S*3)} 1 3 3 \overline{3} 2 \overline{1} \overline{3} 4 \overline{2} \overline{3} \overline{2} \underleftarrow{(3.21)} 1 \underline{\underline{\overline{1}}} 3 \overline{3} 2 3 \overline{3} 4 \overline{2} \overline{3} \overline{2} \underleftarrow{(3.20)} \underline{\underline{\overline{1}}} 1 3 \overline{3} 2 3 \overline{3} 4 \overline{2} \overline{3} \overline{2} \underleftarrow{(S*1)}

1 [figure] 1 3 \overline{3} 2 3 \overline{3} 4 \overline{2} \overline{3} \overline{2} 1 0 0 0 0 0 0 0 0 0 0 \underrightarrow{(S1)} 1 1 3 \overline{3} 2 3 \overline{3} 4 \underline{3} \overline{3} \overline{2} \underrightarrow{(3.6)} 1 1 3 \overline{3} 2 3 \overline{3} 4 4 \overline{3} \overline{2} \underrightarrow{(S3)}

\begin{matrix}1 & − & − & − \\ − & − & − \\ − & − & − \\ − \end{matrix} \underleftarrow{(S*3)} 1 1 3 \overline{3} 2 3 \overline{3} 4 \overline{2} \overline{3} \overline{2} \underleftarrow{(3.20)} 1 1 3 \overline{3} 2 3 \overline{3} \underline{\underline{\overline{2}}} 4 \overline{3} \overline{2} \underleftarrow{(S*1)}

1 1 3 \overline{3} 2 3 \overline{3} 4 [figure] 4 \overline{3} \overline{2} 1 0 0 0 0 0 0 1 0 0 0  \underrightarrow{(S1)} 1 1 3 \overline{3} 2 3 \overline{3} 4 4 \overline{3} 5 \underrightarrow{(S3)}

\begin{matrix}1 & − & − & − \\ − & − & − \\ 2 & − & − \\ − \end{matrix} \underleftarrow{(S*3)} 1 1 3 \overline{3} 2 3 \overline{3} 4 4 \overline{3} \overline{2} \underleftarrow{(S*1)}

1 1 3 \overline{3} 2 3 \overline{3} 4 4 \overline{3} 5 [figure] 1 0 0 0 0 0 0 1 0 0 1 \underrightarrow{(S1)} 1 1 3 \underline{0} 2 3 \overline{3} 4 4 \overline{3} 5 \underrightarrow{(3.6)} 1 1 1 3 2 3 \overline{3} 4 4 \overline{3} 5 \underrightarrow{(S3)}

\begin{matrix}1 & − & − & − \\ − & − & − \\ 2 & − & − \\ 2 \end{matrix} \underleftarrow{(S*3)} 1 1 3 \overline{3} 2 3 \overline{3} 4 4 \overline{3} 5 \underleftarrow{(3.20)} 1 1 \underline{\underline{\overline{3}}} 3 2 3 \overline{3} 4 4 \overline{3} 5 \underleftarrow{(S*1)}

1 1 1 [figure] 3 2 3 \overline{3} 4 4 \overline{3} 5 1 0 1 0 0 0 0 1 0 0 1  \underrightarrow{(S1)} 1 1 1 3 2 3 \underline{2} 4 4 \overline{3} 5 \underrightarrow{(3.6)} 1 1 1 3 2 3 3 4 4 \overline{3} 5 \underrightarrow{(S3)}

\begin{matrix}1 & − & 3 & − \\ − & − & − \\ 2 & − & − \\ 2 \end{matrix} \underleftarrow{(S*3)} 1 1 1 3 2 3 \overline{3} 4 4 \overline{3} 5 \underleftarrow{(3.20)} 1 1 1 3 2 \underline{\underline{\overline{3}}} 3 4 4 \overline{3} 5 \underleftarrow{(S*1)}

1 1 1 3 2 3 [figure] 3 4 4 \overline{3} 5 1 0 1 0 0 1 0 1 0 0 1 \underrightarrow{(S1)} 1 1 1 3 2 3 3 4 4 \underline{3} 5 \underrightarrow{(3.6)} 1 1 1 3 2 3 3 4 4 4 5 \underrightarrow{(S3)}

\begin{matrix}1 & − & 3 & − \\ − & 3 & − \\ 2 & − & − \\ 2 \end{matrix} \underleftarrow{(S*3)} 1 1 1 3 2 3 3 4 4 \overline{3} 5 \underleftarrow{(3.20)} 1 1 1 3 2 3 3 4 \underline{\underline{\overline{3}}} 4 5 \underleftarrow{(S*1)}

1 1 1 3 2 3 3 4 4 [figure] 4 5 1 0 1 0 0 1 0 1 1 0 1 ; \begin{matrix}1 & − & 3 & − \\ − & 3 & − \\ 2 & 3 & − \\ 2 \end{matrix}

References

1. E. A. Bender and D. E. Knuth, Enumeration of plane partitions, J. Combin. Theory A 13 (1972), 40—54.

2. A. Berele and A. Regev, Hook Young diagrams with applications to combinatorics and representations of Lie superalgebras, Adv. in Math. 44 (1987), 118–175.

3. A. Berele and J. B. Remmel, Hook flag characters and their combinatorics, J. Pure Appl. Algebra 35 (1985), 225–245.

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

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

6. I. M. Gessel and X. Viennot, Determinants, paths, and plane partitions, preprint (1989).

7. I. Goulden and C. Greene, A new tableau representation for supersymmetric Schur functions, J. Algebra 170 (1994), 687–703.

8. A. P. Hillman and R. M. Grassl, Reverse plane partitions and tableau hook numbers, J. Combin. Theory Ser. A 21 (1976), 216–221.

9. V. G. Kac, Lie superalgebras, Adv. in Math. 26 (1977), 8–96.

10. V. G. Kac, Characters of typical representations of classical Lie superalgebras, Comm. Algebra 5 (1977), 889–897.

11. V. G. Kac, Representations of classical Lie superalgebras, Differential geometrical methods in mathematical physics II, Lecture Notes in Math., vol. 676, Springer–Verlag, Berlin, 1978, pp. 597–626.

12. C. Krattenthaler, An involution principle-free bijective proof of Stanley’s hook-content formula, preprint.

13. I. G. Macdonald, Symmetric Functions and Hall Polynomials, second edition, Oxford University Press, New York/London, 1995.

14. N. Metropolis, G. Nicoletti and G.-C. Rota, A new class of symmetric functions, Math. Anal. Appl. Part B, Adv. in Math. Suppl. Stud. 7 (1981), 563–575.

15. J. B. Remmel, The combinatorics of (k, l)-hook Schur functions, Combinatorics and algebra (C. Greene, ed.), Contemporary Math., vol. 34, Amer. Math. Soc., Providence, R.I., 1984, pp. 253–287.

16. B. E. Sagan, The symmetric group, Wadsworth & Brooks/Cole, Pacific Grove, California, 1991.

17. M. Scheunert, The theory of Lie superalgebras, Lecture Notes in Math., vol. 716, Springer–Verlag, Berlin, 1979.

18. M.-P. Schützenberger, La correspondance de Robinson, Combinatoire et Représentation du Groupe Symétrique, Lecture Notes in Math., vol. 579, Springer–Verlag, Berlin–Heidelberg–New York, 1977, pp. 59–113.

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