An involution principle-free bijective proof of Stanley’s hook-content formula

C. Krattenthaler^{†}

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

             WWW: http://radon.mat.univie.ac.at/People/kratt

Abstract. A bijective proof for Stanley’s hook-content formula for the generating function for column-strict reverse plane partitions of a given shape is given that does not involve the involution principle of Garsia and Milne. It is based on the Hillman–Grassl algorithm and Schützenberger’s jeu de taquin.

1. Introduction. The purpose of this article is to give a bijective proof for Stanley’s hook-content formula [15, Theorem 15.3] for a certain plane partition generating function. In order to be able to state the formula we have to recall some basic notions from partition theory. A partition is a sequence λ = (λ_{1}, λ_{2}, …, λ_{r}) with λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{r} > 0, for some r. The Ferrers diagram of λ 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.

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, involution principle.

†Supported in part by EC’s Human Capital and Mobility Program, grant CHRX-CT93-0400 and the Austrian Science Foundation FWF, grant P10191-PHY

1 3 4 4 5 5 7 5 6 7 8  1 3 4 4 4 6 7 5 7 8 8

a. Ferrers diagram  b. reverse plane  c. column-strict reverse

partition plane partition

Figure 1

Given a partition λ = (λ_{1}, λ_{2}, …, λ_{r}), a reverse plane partition of shape λ is a filling P of the cells of λ with integers such that the entries along rows and along columns are weakly increasing. Figure 1.b displays a reverse plane partition of shape (4, 3, 3, 1). A reverse plane partition is called column-strict if in addition columns are strictly increasing. Figure 1.c displays a column-strict reverse plane partition of shape (4, 3, 3, 1). We write P_{ρ} for the entry in cell ρ of P. We call the sum of all the entries of a reverse plane partition P the norm of P, and denote it by n(P).

Now we are in the position to state Stanley’s hook-content formula [15, Theorem 15.3].

Theorem 1 (Stanley). Let λ = (λ_{1}, λ_{2}, …, λ_{r}) be a partition and a be an integer ≥ r. The generating function ∑ q^{n(P)}, where the sum is over all column-strict reverse plane partitions P of shape λ with entries between 1 and a, is given by

q^{∑_{i=1}^{r} iλ_{i}} ∏_{ρ∈λ} \frac{1 − q^{a+c_{ρ}}}{1 − q^{h_{ρ}}} .  (1.1)

Stanley proved this theorem by showing that the generating function in question equals a determinant, and then evaluated the determinant. However, such a proof does not explain why the generating function equals such a nice product. In particular, it does not give any clue why in (1.1) the hook lengths and contents appear. The desire to have an explanation for these phenomenons provides the motivation for the search for a bijective proof of this result. A bijective proof for Stanley’s Theorem 1 was given earlier by Remmel and Whitney [10]. Though being a significant advance, one cannot claim that this proof is really enlightening or explains formula (1.1) in a satisfying way. Aside from making use of the involution principle of Garsia and Milne [2] (which creates bijections in an indirect way), it was based on bijections that mimicked recurrence relations, which is certainly not the most direct route to attack the problem. Our proof of Theorem 1 explains the appearance of hook lengths and contents in a straight-forward way. It is based on the Hillman–Grassl algorithm [3] and on Schützenberger’s [14] jeu de taquin. It does not need the involution principle. However, the careful reader will notice that we set up a bijection between two sets of objects that are different from those for which Remmel and Whitney set up their bijection. In order to find a bijection between the sets that Remmel and Whitney consider, also we have to use the involution principle. However, the resulting bijection is considerably simpler than Remmel and Whitney’s.

We remark that a bijective proof of Theorem 1 for one-rowed shapes (i.e. the case of (ordinary) partitions with ≤ λ_{1} parts, each part ≤ a) can be found in Sagan’s paper [11, proof of Theorem 8]. However, this proof is different from our proof when restricted to one-rowed shapes. Besides, this proof does not seem to generalize to arbitrary shapes. In the same paper, which has bijective proofs of hook formulas as its theme, also the problem of finding a bijective proof of MacMahon’s product formula [7, sec. 429, proof in sec. 494] for the generating function of plane partitions of rectangular shapes with bounded entries is posed. Since MacMahon’s formula is actually contained in Theorem 1 (which is seen by an easy transformation of plane partitions into column-strict reverse plane partitions), our bijection also provides a solution to this problem. See also section 4.

Our paper is organized as follows. In section 2 our bijective proof of Theorem 1 is described. (A complete example for our bijection is carried out in the appendix of this paper). Then, in section 3, we discuss some related bijections. In particular, it is there where we explain how our bijection described in section 2 can be used to provide a much simpler (involution principle-based) bijection between the sets that Remmel and Whitney use in their bijective proof [10] of Theorem 1. Finally, in section 4, we list some more plane partition formulas that also desire to receive bijective proofs.

In conclusion of the Introduction, a few comments on the relation of the present work to the recent beautiful bijective proof [8] of the Frame–Robinson–Thrall hook formula for the number of standard Young tableaux of a given shape by Novelli, Pak and Stoyanovskii (announced in [9]) are in order. Clearly, the Novelli–Pak–Stoyanovskii algorithm as well as our algorithm described in Section 2 are based on jeu de taquin (a modified jeu de taquin in our case). Still, I am not able to name an immediate, direct relation. However, I discovered that it is possible to merge the Novelli–Pak–Stoyanovskii idea of how to keep track of the hooks with the modified jeu de taquin idea of this paper to obtain a new bijective proof of the hook-content formula (1.1), which also avoids the involution principle. (In fact, it sets up a bijection between the sets Remmel and Whitney consider in their paper [10].) This will be the subject of a forthcoming publication [5].

2. Bijective proof of Stanley’s hook-content formula. First, we rewrite (1.1) in the form (here CRPP is short for ‘column-strict reverse plane partition’)

(_{∑_{P a CRPP of shape λ} with 1≤entries≤a}q^{n(P)}) · ∏_{ρ∈λ} \frac{1}{1 − q^{a+c_{ρ}}} = q^{∑_{i=1}^{r} iλ_{i}} ∏_{ρ∈λ} \frac{1}{1 − q^{h_{ρ}}} .  (2.1)

Let us call an arbitrary filling of the cells of λ with nonnegative integers a tabloid of shape λ. Furthermore, let us define the hook weight w_{h}(T) of a tabloid T of shape λ by ∑_{ρ∈λ} T_{ρ} · h_{ρ}, and the content weight w_{c}(T) of a tabloid T by ∑_{ρ∈λ} T_{ρ} · (a + c_{ρ}). Then the right-hand side of (2.1) is the generating function ∑ q^{n(P_{0})}q^{w_{h}(T_{R})}, where the sum is over all pairs (P_{0}, T_{R}), with P_{0} being the “minimal” column-strict reverse plane partition of shape λ with entries ≥ 1, i.e. the column-strict reverse plane partition with all entries in row i equal to i for all i, and with T_{R} varying over all tabloids of shape λ. Similarly, the left-hand side of (2.1) is the generating function ∑ q^{n(P_{L})}q^{w_{c}(T_{L})}, where the sum is over all pairs (P_{L}, T_{L}), with P_{L} varying over all column-strict reverse plane partitions of shape λ with entries between 1 and a and T_{L} varying over all tabloids of shape λ. So the task is to set up a bijection that maps a right-hand side pair (P_{0}, T_{R}) to a left-hand side pair (P_{L}, T_{L}), such that n(P_{0}) + w_{h}(T_{R}) = n(P_{L}) + w_{c}(T_{L}).

One step in our bijection was already done much earlier. In their celebrated paper [3], Hillman and Grassl constructed an algorithmic bijection between tabloids T_{R} of shape λ and reverse plane partitions P̄_{R} of shape λ with nonnegative entries 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 ≥ 1, 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 column-strict reverse plane partition of shape λ with entries ≥ 1 to a pair (P_{L}, T_{L}), where P_{L} is a column-strict reverse plane partition of shape λ with entries between 1 and a, and where T_{L} is a tabloid of shape λ, such that

n(P_{R}) = n(P_{L}) + w_{c}(T_{L}).  (2.2)

We claim that the following algorithm performs this task.

Algorithm C. The input for the algorithm is a column-strict reverse plane partition P_{R} of shape λ with entries ≥ 1.

(C0) Set (P, T) := (P_{R}, 0), where 0 denotes the tabloid of shape λ with 0 in each cell. (C1) If P does not contain any entry > a then stop. The output of the algorithm is

(P, T).

Otherwise, consider all corner cells of λ (which are the cells with no right and bottom neighbour cells). Choose all corner cells that contain the maximal entry of P, and among all these pick the left-most, cell ω say. (Note that the maximal entry of P must appear in a corner cell of P since P is a column-strict reverse plane partition. Hence, in our situation it must be > a.) Replace the entry P_{ω} in cell ω by P_{ω} − (a + c_{ω}). Call this entry special. Continue with (C2).

(C2) If a column-strict reverse plane partition is obtained then continue with (C3). If not, i.e. if the special entry, s say, violates increase along rows or strict increase along

columns, then we have the following situation,

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

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} .  (2.4)

If x ≤ y then do the move

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

4 The new special entry in (2.4) is s + 1, the new special entry in (2.5) is s − 1. Repeat (C2). (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.)

(C3) Let P be the column-strict reverse plane partition just obtained. If we ended up with the special entry in cell ρ then add 1 to the entry in cell ρ of T. The tabloid thus obtained is the new T. Continue with (C1). □

Example C. A complete example for Algorithm C can be found in the appendix. There we choose a = 4 and map the column-strict reverse plane partition 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 ≤ 4 and a tabloid of shape (4, 3, 3, 1), such that the weight property (2.2) holds. In fact, the norm of the column-strict reverse plane partition on the left of Figure 2 is 49, while the norm of the column-strict reverse plane partition on the right is 26 and the content weight of the tabloid is 23.

\begin{matrix}1 1 3 8 2 3 4 5 7 8 7 & ⟷ & ( \begin{matrix}1 & 1 & 1 & 3 \\ 2 & 2 & 2 \\ 3 & 3 & 4 \\ 4 \end{matrix} , \begin{matrix}1 & 0 & 1 & 0 \\ 1 & 0 & 0 \\ 3 & 1 & 0 \\ 1 \end{matrix} ) \\ n(.) = 49 & & n(.) = 26 , w_{c}(.) = 23 \end{matrix} 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 (P, T) that is obtained after each loop (C1)-(C2)-(C3). Together with the pair (P, T) a filling of the shape (4, 3, 3, 1) is displayed that shows all values P_{ρ} + 4 + c_{ρ} for all cells ρ with T_{ρ} ≠ 0. This will be important for understanding Lemma C but can be ignored for the moment. At each stage, the entry that is chosen by (C1) is circled. Then each intermediate step during the loop (C1)-(C2)-(C3) is displayed in the odd rows of the right columns. The special entry is always underlined. When a column-strict reverse plane partition is reached, the special entry is boxed. The entry in the corresponding cell of the tabloid is subsequently increased by 1 in step (C3). □

It should be noticed that, aside from adding/subtracting 1 to/from the special entry, what happens from (2.3) to (2.4), respectively (2.5), is a jeu de taquin forward move (cf. [14, sec. 2; 13, pp. 120/169]).

It is obvious that this algorithm maps P_{R} to a pair (P_{L}, T_{L}), where T_{L} is a tabloid of shape λ and P_{L} is a column-strict reverse plane partition of shape λ with entries ≤ a. In fact, the entries of P_{L} have to be ≥ 1. This is seen as follows. The only problem could arise with our special entry. However, when we arrive at (C3), a special entry ≤ 0 can only occur in cell (1, 1), because otherwise step (C2) was not finished. Each loop (C1)- (C2)-(C3) of the algorithm starts with some entry P_{ω} > a in a corner cell ω. It is replaced by P_{ω} − (a + c_{ω}). Then it is (possibly) moved according to (2.4) and (2.5). It is easy to check that at each stage during performing the steps (C2), the special entry, if located in cell ρ, will equal P_{ω} − (a + c_{ρ}). This is a property so important that it has to be recorded for later use,

(special entry in ρ) = P_{ω} − (a + c_{ρ}).  (2.6)

Suppose we reach cell (1, 1). When we arrive at (1, 1), by (2.6) and since c_{(1,1)} = 0, our special entry has become P_{ω} − a. But this is ≥ 1 since P_{ω} > a.

So we have an algorithm that maps right-hand side objects P_{R} of (2.1) to left-hand side objects (P_{L}, T_{L}) of (2.1). Besides, this mapping satisfies the weight property (2.2). This is immediate from (2.6).

What remains is to establish that our algorithm is actually a bijection between righthand side and left-hand side objects. This will be accomplished by constructing an algorithm, Algorithm C* below, that will turn out to be the inverse of Algorithm C. We could exhibit Algorithm C* immediately. However, we prefer to provide motivation for the definition of Algorithm C* first, in form of the following lemma. On the other hand, readers who are not interested in the details can safely skip the lemma and jump to the description of Algorithm C* at this point.

Lemma C. Let (P, T) be obtained after some loop (C1)-(C2)-(C3) during Algorithm C. Suppose that the loop terminated in cell γ when reaching (C3). Then among all cells ρ with T_{ρ} ≠ 0, γ is a cell for which the value P_{ρ} + a + c_{ρ} attains its minimum, and if there are several cells ρ with T_{ρ} ≠ 0 where the minimum is attained, then γ is the right-most and top-most of those. Besides, there holds

P_{γ} + a + c_{γ} ≥ max{entries in P }.  (2.7)

Proof. We prove the assertions by induction on the number of loops (C1)-(C2)-(C3). The assertions are certainly true for the pair (P̄, T̄) obtained after the very first loop

(C1)-(C2)-(C3) from (P_{R}, 0). This is because there is only one cell ζ in T̄ with T̄_{ζ} ≠ 0, and, what regards (2.7), because

P̄_{ζ} + a + c_{ζ} = max{entries in P_{R}} ≥ max{entries in P̄},  (2.8)

the equality holding because of (2.6), the inequality holding because of the following facts. In the transition from P_{R} to P̄ the multiset of entries remains the same, except for one entry, (P_{R})_{ω}, where ω is the corner cell that is chosen when applying (C1) to P_{R}. At the beginning of the loop (C1)-(C2)-(C3) leading from P_{R} to P̄, (P_{R})_{ω} is replaced by (P_{R})_{ω} − (a + c_{ω}), which is less than (P_{R})_{ω} because of a ≥ r > max{−c_{ρ} : ρ ∈ λ} (recall that a ≥ r is one of the assumptions in Theorem 1.) Then the special entry (P_{R})_{ω} −(a+c_{ω}) is (possibly) moved inwards according to (2.4) and (2.5). At the end of the loop (C1)-(C2)- (C3) a column-strict reverse plane partition is obtained, therefore the special entry in the end has to be ≤ max{entries in P_{R}} in any case.

. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . . . . . .. . . . .. . . . .. . . . . . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . γ  ω ζ

The cells γ, ζ, ω, the jeu de taquin path from ω to ζ, and the four regions determined by γ.

Figure 3

So, let us assume that the assertions are true for (P, T), obtained after some loop (C1)- (C2)-(C3). Let γ be the cell where the last loop, which gave rise to (P, T), terminated at (C3). Let ω be the cell where the next loop starts, i.e. the corner cell of P chosen by (C1), and let ζ be the cell where this next loop terminates at (C3). See Figure 3. Let (P̄, T̄) be the outcome after this loop. Note that by construction the cells ρ with T̄_{ρ} ≠ 0 are ζ and the cells with T_{ρ} ≠ 0. In particular, T_{ρ} ≠ 0 implies T̄_{ρ} ≠ 0.

First we prove (2.7) for P̄ and ζ. By (2.6), the entry of P̄ in cell ζ is

P̄_{ζ} = P_{ω} − (a + c_{ζ}).  (2.9)

This immediately implies

P̄_{ζ} + a + c_{ζ} = P_{ω} = max{entries in P } ≥ max{entries in P̄}.  (2.10)

The last inequality follows from the arguments that proved (2.8), just replace P_{R} by P in the paragraph after (2.8). Obviously, (2.10) proves (2.7) for P̄ and ζ, as desired.

Next we show that P̄_{ρ} + a + c_{ρ}, evaluated at cells ρ with T̄_{ρ} ≠ 0, attains its minimal value at ζ. By induction hypothesis, (2.7) holds for P and γ. Hence we have

P_{γ} + a + c_{γ} ≥ max{entries in P } = P_{ω} = P̄_{ζ} + a + c_{ζ}.  (2.11)

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

P̄_{ρ} + a + c_{ρ} ≥ P̄_{ζ} + a + c_{ζ}.  (2.12)

If ρ = ζ then there is nothing to show. So let ρ ≠ ζ. Then we have T_{ρ} ≠ 0. By induction hypothesis for γ, we have P_{γ} + a + c_{γ} ≤ P_{ρ} + a + c_{ρ} for all cells with T_{ρ} ≠ 0. So, if we suppose P_{ρ} = P̄_{ρ}, then we conclude, using (2.11),

P̄_{ρ} + a + c_{ρ} = P_{ρ} + a + c_{ρ} ≥ P_{γ} + a + c_{γ} ≥ P̄_{ζ} + a + c_{ζ},

which verifies (2.12) in this case. However, the only entries that are changed during the performance of the loop (C1)-(C2)-(C3) are located in cells (weakly) to the right and (weakly) below of cell ζ, see Figure 3. For these cells there holds the following basic computation. For convenience, let ζ = (i_{1}, j_{1}), and let ρ = (i_{2}, j_{2}) be in this region to the right and below of ζ, i.e. i_{1} ≤ i_{2} and j_{1} ≤ j_{2}. Then, since P̄ is a column-strict reverse plane partition, we have

P̄_{ρ} + a + c_{ρ} = P̄_{ρ} + a + (j_{2} − i_{2})
≥ (P̄_{ζ} + i_{2} − i_{1}) + a + (j_{2} − i_{2}) = P̄_{ζ} + a + j_{2} − i_{1}
≥ P̄_{ζ} + a + j_{1} − i_{1} = P̄_{ζ} + a + c_{ζ}.  (2.13)

Therefore the value P̄_{ρ} + a + c_{ρ} for any cell ρ in the region to the right and below of ζ is at least P̄_{ζ} + a + c_{ζ}, so also for the cells with T̄_{ρ} ≠ 0, which verifies (2.12) in this case, too. For later reference we remark that the computation (2.13) also shows that the only cells in this region for which we could have equality are in the same column as ζ.

Finally we show that ζ is the right-most and top-most among all cells ρ with T̄_{ρ} ≠ 0 where P̄_{ρ} + a + c_{ρ} attains its minimal value. Let ρ be a cell with T̄_{ρ} ≠ 0 where P̄_{ρ} + a + c_{ρ} attains its minimal value. In particular, we have

P̄_{ρ} + a + c_{ρ} = P̄_{ζ} + a + c_{ζ}.  (2.14)

First, suppose that ρ is a cell with P̄_{ρ} ≠ P_{ρ}. Then ρ has to be located in the region (weakly) to the right and (weakly) below of ζ. As we noted after the computation (2.13), the only cells ρ in this region for which we could have equality in (2.13) lie in the same column as ζ. ζ is the top-most and right-most of these, in agreement with our claim.

The more delicate case is when ρ is a cell with T̄_{ρ} ≠ 0 and P̄_{ρ} = P_{ρ}. Of course, nothing is to show for ρ = ζ, so we may assume ρ ≠ ζ. This implies T_{ρ} ≠ 0, and so P̄_{ρ} + a + c_{ρ} = P_{ρ} + a + c_{ρ} ≥ P_{γ} + a + c_{γ}, the inequality holding by induction hypothesis for γ. Combining this with (2.11) and (2.14) we are forced to conclude

P_{ρ} + a + c_{ρ} = P_{γ} + a + c_{γ} = P̄_{ζ} + a + c_{ζ}.  (2.15)

We shall show that ζ has to lie in the region (weakly) to the right and (weakly) above of γ (as is indicated in Figure 3). Since γ was the right-most and top-most of all the cells ρ with T_{ρ} ≠ 0 where the minimal value of P_{ρ} + a + c_{ρ} is attained, this would establish that ζ is the right-most and top-most of all the cells ρ with T̄_{ρ} ≠ 0 where the minimal value of P̄_{ρ} + a + 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 γ, see Figure 3.

First, suppose that ζ lies in the region strictly to the right and (weakly) below of γ. Then P_{γ} = P̄_{γ}, since γ was not met during the loop (C1)-(C2)-(C3) leading from P to P̄. However, then the basic computation (2.13) applies with ζ replaced by γ, and ρ replaced by ζ. Since we assumed that ζ is strictly to the right of γ, the remark below (2.13) tells that actually strict inequality in (2.13), with the above replacements, holds, i.e. P̄_{ζ} + a + c_{ζ} > P̄_{γ} + a + c_{γ}. This contradicts (2.15) because of P_{γ} = P̄_{γ}. Thus, this region is excluded.

Next we show that ζ cannot lie in the region (weakly) to the left and (weakly) below of γ, γ excluded. This would follow immediately from the claim that if two successive loops (C1)-(C2)-(C3) start with the same size of entry in the corner cells chosen by (C1) (which applies in our case since the loop that lead to P started with an entry P_{γ} + a + c_{γ} in some corner cell, and the loop that lead from P to P̄ started with P̄_{ζ} + a + c_{ζ}, both quantities being the same by (2.15)) then the second path of moves has to stay to the right of 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 (C1). By the rules in (C1), this means that either the second loop started strictly to the right of the first, or we started in the same cell, where in this case the first loop started with a left move (2.4). (Note that if we start with an upward move (2.5) then, by column-strictness, a smaller entry is moved into the corner cell than has been there before.) Now, it is an easy-to-check property of our modified forward jeu de taquin (C2) that if the second “jeu de taquin path” is to the right of the first “jeu de taquin path” somewhere, then it has to stay to the right from thereon. To make this precise, suppose that during the first loop the special entry, s_{1} say, went up by (2.5), see the left half of Figure 4. (The arrows mark the direction of move of the special entry.)

y z_{s_{1} ∗}

⟶^{first loop}^{during}
∗ z_{↑ y ∗}

∗ z_{y s_{2}}

during

⟶^{second loop}

∗ ∗_{y ↑ z}

Figure 4

Since rows are weakly increasing, 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 the definition of the algorithm forces us to stop here or to move up in the next step (C2). We already checked that the second “jeu de taquin path” starts to the right of the first, therefore it has to stay to the right always. So also this region is excluded.

Finally, we examine if ζ could be located in the region strictly to the left and (weakly) above of γ. Once more the computation (2.13), with ρ replaced by γ, applies and, together with the remark below (2.13) (note that we assumed γ to be strictly to the right of ζ), implies P̄_{γ} + a + c_{γ} > P̄_{ζ} + a + c_{ζ}, which contradicts (2.15) because of the simple fact P_{γ} ≥ P̄_{γ}.

This completes the proof of the Lemma. □

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

Algorithm C*. The input for the algorithm is a pair (P_{L}, T_{L}), where P_{L} is a columnstrict reverse plane partition of shape λ with entries between 1 and a, and where T_{L} is a tabloid of shape λ.

(C*0) Set (P, T) := (P_{L}, T_{L}).

(C*1) If T = 0 then stop. The output of the algorithm is P.

Otherwise, consider all cells ρ with T_{ρ} ≠ 0. Among these choose the cells for which P_{ρ} + a + c_{ρ} is minimal, and among all these pick the right-most and top-most, cell ζ say.

(Observe that among two cells attaining the same value of P_{ρ}+a+c_{ρ} one is always (weakly) to the right and (weakly) above of the other, again because of the computation (2.13), with P̄ replaced by P, and the remark below (2.13). So the right-most and top-most of these does exist.) Replace the entry P_{ζ} in cell ζ by P_{ζ} + a + c_{ζ}. Call this entry special. Continue with (C*2).

(C*2) If the special entry, s say, is located in a corner cell of λ then continue with (C*3). If not, then we have the following situation,

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

(One of x or y is also allowed to be actually not there.) If x < y then do the move

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

If x ≥ y then do the move

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

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

(C*3) Let P be the column-strict reverse plane partition just obtained. (The fact that indeed a column-strict reverse plane partition is obtained will be proved in the subsequent Lemma C*.) Subtract 1 from the entry in cell ζ of T. The tabloid thus obtained is the new T. Continue with (C*1). □

Example C*. A complete example for Algorithm C* can be found in the appendix. There we choose a = 4 and map the pair on the right of Figure 2, consisting of a columnstrict reverse plane partition of shape (4, 3, 3, 1) with entries ≤ 4 and a tabloid of shape (4, 3, 3, 1), to the column-strict reverse plane partition of shape (4, 3, 3, 1) on the left of Figure 2, such that the weight property (2.2) holds. It is simply the inverse of the example for Algorithm C given in Example C. 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 (P, T) that is obtained after each loop (C*1)-(C*2)-(C*3) together with a filling of the shape (4, 3, 3, 1) that shows all values P_{ρ} + 4 + c_{ρ} for all cells ρ with T_{ρ} ≠ 0. At each stage, the entry that is chosen by (C*1) is doubly circled. Then each intermediate step during the loop (C*1)-(C*2)-(C*3) is displayed in the even rows of the right columns. The special entry is always doubly underlined. When a column-strict reverse plane partition is reached, the special entry is doubly boxed. The entry in the corresponding cell of the tabloid is subsequently decreased by 1 in step (C*3). □

Again, it should be noticed that (2.17) and (2.18) are exactly jeu de taquin backward moves (cf. [14, sec. 2; 13, pp. 120/169]), which reverse the forward moves (2.4) and (2.5), respectively, except for the subtraction/addition of 1 in (2.4) and (2.5).

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

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

P_{ρ} + a + c_{ρ} ≥ max{entries in P }.  (2.19)

Also, P is a column-strict reverse plane partition. Besides, if ω is the corner cell that contained the special entry at the end of the loop (C*1)-(C*2)-(C*3) that lead to P, then ω is the left-most corner cell in P that contains the maximal entry of P.

Proof. We prove the assertions by induction on the number of loops (C*1)-(C*2)- (C*3).

To begin with, we know that when we start with Algorithm C* we have a pair (P, T), where P is a column-strict reverse plane partition with entries between 1 and a. So for any cell ρ = (i, j) we have

P_{ρ} + a + c_{ρ} = P_{(i,j)} + a + c_{(i,j)}
≥ i + a + (j − i)
> a
> max{entries in P }.  (2.20)

So the assertion (2.19) and the assertion that P is a column-strict reverse plane partition hold at the very beginning. This will suffice for the start of the induction.

As induction hypothesis let us assume that the assertions of the Lemma are true for (P, T) and all preceding pairs occuring in step (C*3) during the process of the algorithm, except of course that the assertion about the corner cell ω does not hold for the initial pair (because it does not make sense for the initial pair).

Let ζ be the cell where the loop (C*1)-(C*2)-(C*3) starts from (P, T), i.e. the cell that is chosen by applying (C*1) to (P, T), and let κ be the corner cell where the loop stops at (C*3). See Figure 5. Furthermore, let (P̄, T̄) be the outcome after this loop. Then, by definition of the algorithm we have

P̄_{κ} = P_{ζ} + a + c_{ζ}.  (2.21)

Note that, also by definition of the algorithm, the cells ρ with T̄_{ρ} ≠ 0 are those with T_{ρ} ≠ 0, except possibly for ζ. In particular, T̄_{ρ} ≠ 0 implies T_{ρ} ≠ 0.

ζ  ω γ κ

The cells γ, ω, ζ, κ, the jeu de taquin paths from γ to ω and from ζ to κ.

Figure 5

First we prove (2.19) for P̄. Let ρ be any cell different from κ with T̄_{ρ} ≠ 0. By definition of (C*2) we have P̄_{ρ} ≥ P_{ρ}. Besides, we already saw that T̄_{ρ} ≠ 0 implies T_{ρ} ≠ 0. Therefore, by construction of ζ in (C*1), we have

P̄_{ρ} + a + c_{ρ} ≥ P_{ρ} + a + c_{ρ} ≥ P_{ζ} + a + c_{ζ}.  (2.22)

Note that (2.22) also holds for ρ = κ since by (2.21) we have P̄_{κ} + a + c_{κ} = (P_{ζ} + a + c_{ζ}) + a + c_{κ} ≥ P_{ζ} + a + c_{ζ}, the inequality being true because of a ≥ r > max{−c_{ρ} : ρ ∈ λ} (recall that a ≥ r is one of the assumptions in Theorem 1.) Also by construction of ζ, we have T_{ζ} ≠ 0, and hence by induction hypothesis (2.19) that P_{ζ} + a + c_{ζ} ≥ max{entries in P }. This implies that P_{ζ} + a + c_{ζ} = max{entries in P̄} since the set of entries of P̄ is the same as the set of entries in P except for the special entry P_{ζ} + a + c_{ζ} created in (C*1) and finally located in cell κ in P̄. Hence, (2.22) proves (2.19) with P replaced by P̄, as desired.

Now we prove that P̄ is a column-strict reverse plane partition. If P_{ζ} + a + c_{ζ} > max{entries in P } then this assertion certainly holds, since P̄_{κ} = P_{ζ} + a + c_{ζ} is the only new entry in P̄. Note in particular, that by (2.20) we are in this case at the very beginning.

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

P_{ζ} + a + c_{ζ} = max{entries in P }.  (2.23)

Observe that the only difficulty arises when we reach corner cell κ at the end of a loop (C*1)-(C*2)-(C*3) from above, and when in addition P_{κ} = P̄_{κ} holds. In this case columnstrictness of P̄ would be violated. We have to show that this case cannot occur.

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

P_{ω} = P′_{γ} + a + c_{γ}.  (2.24)

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

P′_{γ} + a + c_{γ} = max{entries in P }.  (2.25)

Furthermore, there holds P′_{ζ} ≤ P_{ζ}, by the definition of (C*1) if ζ ≠ ω, but also if ζ = ω because of (2.24) and the induction hypothesis (2.19) for P′ and ρ = γ. Hence, again by definition of (C*1), P′_{γ} + a + c_{γ} ≤ P′_{ζ} + a + c_{ζ} ≤ P_{ζ} + a + c_{ζ}. Combining this with (2.23) and (2.25), we are forced to conclude

P′_{γ} + a + c_{γ} = P′_{ζ} + a + c_{ζ} (= P_{ζ} + a + c_{ζ}).  (2.26)

Therefore, again by definition of (C*1), ζ lies (weakly) to the left and (weakly) below of γ, as is indicated in Figure 5.

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

∗ s_{1}_{z y}

⟶^{first loop}^{during}
∗ y_{z ↓ ∗}

s_{2} y_{z ∗}

during

⟶^{second loop}

z y_{↓ ∗ ∗}

Figure 6

Since rows are weakly increasing, we have z ≤ y. 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 6. Then the definition of the algorithm forces us to stop here or to move down in the next step (C*2).

We already saw that the second “jeu de taquin path” starts at ζ, which is (weakly) to the left and (weakly) below of γ, the starting cell of the first “jeu de taquin path”. Therefore, if we suppose that the first path does not meet ζ, we are to the left of the first path when we start the second path. Then, if at the end of the second path we reach the same corner cell as the first path did, we have to reach it from the left. As noted above, this guarantees that P̄ is a column-strict reverse plane partition. If we do not reach the same corner cell, then we reach a corner cell κ to the left. In this case our induction hypothesis for ω, the corner cell that was reached at the end of the first path, says that P_{κ} is strictly less than P_{ω} = max{entries in P }. Therefore, by using (2.21) and (2.23) we have P_{κ} < max{entries in P } = P̄_{κ}. Hence, P̄ will be a column-strict reverse plane partition, regardless from which direction we reached cell κ.

Now we have to consider the only remaining case that the first path, starting at γ, meets ζ. In this case, ζ would have to lie in the same column as γ (and below). First suppose that ζ is left by the first path by a downward move. In this case, by (2.18), we would have P_{ζ} > P′_{ζ}, which contradicts (2.26). So the first path has to leave ζ by a right move. Hence, we are to the left of the first path at the beginning of the second path. Thus, the above considerations apply again.

Finally, we prove that κ is the left-most corner cell in P̄ that contains the maximal entry in P̄. This is trivially true if P_{ζ} +a+c_{ζ} > max{entries in P }, again by remembering (2.21). Note that this inequality is in particular true at the very beginning of Algorithm C*, because in this case (2.20) holds even for all cells ρ, so also for ζ. Because of the induction hypothesis (2.19), the only other case is P_{ζ} + a + c_{ζ} = max{entries in P }. Since we are not at the very beginning, we are allowed to assume that this last assertion of Lemma C* holds for P and ω. However, we already considered the case P_{ζ} + a + c_{ζ} = max{entries in P } before (see (2.23)) and showed that the “jeu de taquin path” leading from ζ to κ has to stay to the left of the “jeu de taquin path” leading from γ to ω. Hence κ is (weakly) to the left of ω. By induction hypothesis, ω was the left-most corner cell containing the maximal entry of P. So κ, which by (2.21) contains P_{ζ} + a + c_{ζ} = max{entries in P } in P̄, is the left-most corner cell of P̄ containing max{entries in P̄} (= max{entries in P }), as desired.

This completes the proof of the Lemma. □

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

3. Related bijections. In this section we discuss bijections related to the bijection in section 2. It is mainly intended to serve the true purist among combinatorialists.

It is two items that we want to address in this section. First, one might argue that we did not prove Theorem 1 directly, but the variant (2.1). Well, as we show in the first part of this section, it is not difficult to construct a bijective proof of Theorem 1 directly, i.e. of

(_{∑_{P a CRPP of shape λ} with 1≤entries≤a}q^{n(P)}) = q^{∑_{i=1}^{r} iλ_{i}} ∏_{ρ∈λ} \frac{1}{1 − q^{h_{ρ}}} · ∏_{ρ∈λ}(1 − q^{a+c_{ρ}}),  (3.1)

by using our Algorithms C and C*. Secondly, Remmel and Whitney [10], in the first bijective proof of Stanley’s hook-content formula Theorem 1, gave an involution principlebased bijective proof for even another variant of Theorem 1, namely

(_{∑_{P a CRPP of shape λ} with 1≤entries≤a}q^{n(P)}) · ∏_{ρ∈λ}[h_{ρ}] = q^{∑_{i=1}^{r} iλ_{i}} ∏_{ρ∈λ}[a + c_{ρ}],  (3.2)

where [n] := 1 + q + q^{2} + ⋯ + q^{n−1}. While we do not know how to construct a direct bijection (in the sense of avoiding the involution principle) for (3.2), we are able to find a much simpler involution principle-based bijective proof of (3.2) by using our Algorithms C and C*. This is subject of the second part of this section.

Before we start, we introduce some special tabloids to be used in the course of the following bijections. Let f be some function from the set of all cells of a Ferrers diagram λ into the integers, that maps the cell ρ to the value f_{ρ}, say. Then we call a tabloid T of shape λ a (< f)-tabloid if T_{ρ} < f_{ρ} for all cells ρ ∈ λ, and we call T a (0–f)-tabloid if T_{ρ} equals 0 or f_{ρ}, for all cells ρ ∈ λ. The sign sgn(T) of a (0–f)-tabloid is always defined to be (−1)^{number of nonzero entries in T}.

Bijective proof of (3.1). As was already used in section 2, the Hillman–Grassl correspondence [3] bijectively shows that q^{∑_{i=1}^{r} iλ_{i}}/ ∏_{ρ∈λ}(1 − q^{h_{ρ}}) is the generating function ∑ q^{n(P_{R})}, where the sum is over all column-strict reverse plane partitions of shape λ with entries ≥ 1. Thus the right-hand side of (3.1) is the generating function ∑ sgn(T_{R})q^{n(P_{R})}q^{n(T_{R})}, where the sum is over all pairs (P_{R}, T_{R}), with P_{R} being a columnstrict reverse plane partition of shape λ with entries ≥ 1 and with T_{R} being a (0–(a + c))- tabloid of shape λ (viewing (a+c) as a function that maps a cell ρ ∈ λ to a+c_{ρ}). There is a straight-forward embedding of the set of column-strict reverse plane partitions P of shape λ with entries between 1 and a (the “left-hand side objects” in (3.1)) into the above pairs, namely by mapping P to (P, 0). Therefore, in order to prove (3.1) bijectively, we have to find a sign-reversing (with respect to sgn(T_{R})) and weight-preserving (with respect to q^{n(P_{R})+n(T_{R})}) involution on the set of all pairs (P_{R}, T_{R}) as above, where either P_{R} contains some entry > a or where T_{R} contains some nonzero entry.

Such an involution is simply described. Fix some total ordering of the cells of λ. Consider such a pair (P_{R}, T_{R}). Apply Algorithm C to P_{R} to obtain (P̄_{R}, T̄_{R}), where P̄_{R} is a column-strict reverse plane partition of shape λ with entries between 1 and a and where T̄_{R} is some tabloid of shape λ. Pick the least cell ρ (in the chosen fixed total order) such that T̄_{R} or T_{R} contain a nonzero entry in this cell. (Note that by assumption there must be at least one such cell.) If the entry is nonzero in T_{R} then replace it by 0, thus obtaining T′_{R}, and add 1 to the entry in cell ρ of T̄_{R}, thus obtaining T̄′_{R}. Otherwise, replace the 0 in cell ρ of T_{R} by a + c_{ρ}, thus otaining T′_{R}, and subtract 1 from the entry in cell ρ of T̄_{R}, thus obtaining T̄_{R}. Apply Algorithm C* to the pair (P̄_{R}, T̄′_{R}), thus obtaining P′_{R}. The image of (P_{R}, T_{R}) under our involution is defined to be (P′_{R}, T′_{R}). The reader should not have any difficulty to verify that this mapping is indeed an involution and is sign-reversing and weight-preserving in the above sense. □

Bijective proof of (3.2). First we have to recall the involution principle of Garsia and Milne [2] (see also [17, sec. 4.6]). Let X be a finite set with a signed weight function w defined on it. Furthermore, let X_{L} and X_{R} be subsets of X, both of which containing elements with positive sign only. Suppose that there is a sign-reversing and weight-preserving involution i_{L} on X that fixes X_{L} and a sign-reversing and weight-preserving involution i_{R} on X that fixes X_{R}. Then there must be a weight-preserving bijection between X_{L} and X_{R}. And such a bijection can be constructed explicitly by mapping x ∈ X_{L} to (i_{L}∘i_{R})^{n}(x) where n is the least integer such that (i_{L} ∘ i_{R})^{n}(x) is in X_{R}.

Now we turn to our promised bijective proof of (3.2). The right-hand side of (3.2) can be seen as the generating function ∑ q^{n(P_{0})}q^{n(T_{R})}, where the sum is over all pairs (P_{0}, T_{R}), with P_{0} being the “minimal” column-strict plane partition with entries ≥ 1 as explained in section 2, and with T_{R} being a (< a + c)-tabloid of shape λ. Call this set of pairs O_{R}. Similarly, the left-hand side of (3.2) can be seen as the generating function ∑ q^{n(P_{L})}q^{n(T_{L})}, where the sum is over all pairs (P_{L}, T_{L}), with P_{L} being a column-strict reverse plane partition of shape λ with entries between 1 and a, and with T_{L} being a (< h)-tabloid. Call this set of pairs O_{L}.

We need to set up a bijection between these two sets of objects. We want to use the involution principle. Therefore we have to say which choices we take for the set X, the signed weight w, the subsets X_{L} and X_{R}, and the involutions i_{L} and i_{R}. Of course, O_{L} and O_{R} should correspond to X_{L} and X_{R}, respectively, the latter being subsets of the bigger set X, that has to be described next.

We define X to be the set of all triples (P, T^{1}, T^{2}) where P is a column-strict reverse plane partition os shape λ with entries ≥ 1, T^{1} is a (0– min{h, a + c})-tabloid of shape λ, and T^{2} is a (< max{h, a + c})-tabloid of shape λ. The signed weight w on X is defined by

w((P, T^{1}, T^{2})) = sgn(T^{1}) q^{n(P)+n(T^{1})+n(T^{2})}.  (3.3)

We define the set X_{L} to be the subset of all triples (P, T^{1}, T^{2}), where P is a columnstrict reverse plane partition of shape λ with entries between 1 and a, where T^{1} = 0, and where T^{2} is a (< h)-tabloid. Note in particular that the sign of w((P, T^{1}, T^{2})) for all these triples is sgn(0) = 1 which is positive. Obviously, X_{L} is in bijection with O_{L}. Besides, there holds w((P, 0, T^{2})) = q^{n(P)+n(T^{2})}, which is exactly what we need.

We define the set X_{R} to be the subset of X consisting of all triples (P_{0}, T^{1}, T^{2}), where T^{1} = 0 and where T^{2} is a (< a + c)-tabloid. Again, the sign of w((P_{0}, T^{1}, T^{2})) for all these triples is positive. Obviously, X_{R} is in bijection with O_{R}, and w((P_{0}, 0, T^{2})) = q^{n(P_{0})+n(T^{2})}, which is exactly what we need.

For defining the involutions i_{L} and i_{R} we fix a total ordering of the cells of λ, as we did before in the bijective proof of (3.1).

First we define the involution i_{L} that fixes X_{L}. Let (P, T^{1}, T^{2}) be a triple in X that is not in X_{L}, i.e. P contains an entry > a or T^{1} contains a nonzero entry. We distinguish between two cases. For the first case we assume that there is a cell ρ in λ with

h_{ρ} ≤ T_{ρ}^{1} + T_{ρ}^{2} < a + c_{ρ}.  (3.4)

Without loss of generality, let ρ be the least such cell in our fixed total order. Note in particular, that (3.4) implies h_{ρ} < a+c_{ρ}, and therefore by definition of T^{1} and T^{2} we have T_{ρ}^{1} = 0 or h_{ρ}, and 0 ≤ T_{ρ}^{2} < a + c_{ρ}. If T_{ρ}^{1} = 0 then we replace T_{ρ}^{1} by h_{ρ}, thus obtaining T̄^{1}, and we replace T_{ρ}^{2} by T_{ρ}^{2} − h_{ρ}, thus obtaining T̄^{2}. If T_{ρ}^{1} = h_{ρ} then we replace T_{ρ}^{1} by 0, thus obtaining T̄^{1}, and we replace T_{ρ}^{2} by T_{ρ}^{2} + h_{ρ}, thus obtaining T̄^{2}. It is easy to check that because of (3.4) in both cases T̄_{1} will be a (0– min{h, a + c})-tabloid and T̄^{2} will be a (< max{h, a + c})-tabloid. We define i_{L}((P, T^{1}, T^{2})) to be (P, T̄^{1}, T̄^{2}). Obviously, there holds w((P, T^{1}, T^{2})) = −w((P, T̄^{1}, T̄^{2})), as required.

In the second case, i.e. if we have a triple (P, T^{1}, T^{2}) where (3.4) is false for any cell ρ, then in the first step we transform (P, T^{1}, T^{2}) into a quadruple (P′, S^{0}, S^{1}, S^{2}), where P′ is a column-strict reverse plane partition of shape λ with entries between 1 and a, S^{0} is a tabloid of shape λ, S^{1} is a (< h)-tabloid of shape λ, and S^{2} is a (0–(a + c))-tabloid of shape λ, such that

w((P, T^{1}, T^{2})) = sgn(S^{2}) q^{n(P′)+w_{c}(S^{0})+n(S^{1})+n(S^{2})}.  (3.5)

The pair (P′, S^{0}) is obtained by applying Algorithm C to P. S^{1} and S^{2} are obtained by doing the following operation on T^{1} and T^{2} for each cell ρ in λ. If h_{ρ} ≥ a + c_{ρ} then interchange T_{ρ}^{1} and T_{ρ}^{2}. If h_{ρ} < a + c_{ρ} and if T_{ρ}^{1} + T_{ρ}^{2} < h_{ρ} (which implies T_{ρ}^{1} = 0) then again interchange T_{ρ}^{1} and T_{ρ}^{2}. If h_{ρ} < a + c_{ρ} and if T_{ρ}^{1} + T_{ρ}^{2} ≥ a + c_{ρ} (which implies T_{ρ}^{1} = h_{ρ}) then replace T_{ρ}^{1} by T_{ρ}^{1} + T_{ρ}^{2} − (a + c_{ρ}) and T_{ρ}^{2} by a + c_{ρ}. By a simple case-by-case analysis the following facts can be checked: The new tabloid S^{1} is a (< h)-tabloid and the new tabloid S^{2} is a (0–(a + c))-tabloid, in all cases. The relation (3.5) is satisfied. Also, this transformation can be reversed. Finally, T^{1} ≠ 0 if and only if S^{2} ≠ 0 under this transformation.

In the second step, we choose the least cell ρ in our fixed total order such that S_{ρ}^{0} or S_{ρ}^{2} is nonzero. If S_{ρ}^{2} is nonzero then replace S_{ρ}^{2} by 0, thus obtaining S̄^{2}, and add 1 to S_{ρ}^{0}, thus obtaining S̄^{0}. If S_{ρ}^{2} is 0 then replace S_{ρ}^{2} by a + c_{ρ}, thus obtaining S̄^{2}, and subtract 1 from S_{ρ}^{0}, thus obtaining S̄^{0}. Finally, in the third step we apply the inverse of the above transformation to (P′, S̄^{0}, S^{1}, S̄^{2}), thus obtaining (P̄, T̄^{1}, T̄^{2}). We define i_{L}((P, T^{1}, T^{2})) to be (P̄, T̄^{1}, T̄^{2}). By construction we have w((P, T^{1}, T^{2})) = −w(P̄, T̄^{1}, T̄^{2}), as required.

We leave it to the reader to verify that i_{L} is a sign-reversing and weight-preserving (with respect to the signed weight (3.3)) involution on X \ X_{L}.

The definition of i_{R} proceeds in a similar spirit. Let (P, T^{1}, T^{2}) be a triple in X with either P being different from P_{0} or T^{1} containing a nonzero entry.

Again, we distinguish between two cases. For the first case we assume that there is a cell ρ in λ with

a + c_{ρ} ≤ T_{ρ}^{1} + T_{ρ}^{2} < h_{ρ}.  (3.6)

Without loss of generality, let ρ be the least such cell in our fixed total order. Note in particular, that (3.6) implies a+c_{ρ} < h_{ρ}, and therefore by definition of T^{1} and T^{2} we have T_{ρ}^{1} = 0 or a + c_{ρ}, and 0 ≤ T_{ρ}^{2} < h_{ρ}. If T_{ρ}^{1} = 0 then we replace T_{ρ}^{1} by a + c_{ρ}, thus obtaining T̄^{1}, and we replace T_{ρ}^{2} by T_{ρ}^{2} − (a + c_{ρ}), thus obtaining T̄^{2}. If T_{ρ}^{1} = a + c_{ρ} then we replace T_{ρ}^{1} by 0, thus obtaining T̄^{1}, and we replace T_{ρ}^{2} by T_{ρ}^{2} + a + c_{ρ}, thus obtaining T̄^{2}. It is easy to check that because of (3.6) in both cases T̄_{1} will be a (0– min{h, a + c})-tabloid and T̄^{2} will be a (< max{h, a + c})-tabloid. We define i_{L}((P, T^{1}, T^{2})) to be (P, T̄^{1}, T̄^{2}). Obviously, there holds w((P, T^{1}, T^{2})) = −w((P, T̄^{1}, T̄^{2})), as required.

In the second case, i.e. if we have a triple (P, T^{1}, T^{2}) where (3.6) is false for any cell ρ, then in the first step we transform (P, T^{1}, T^{2}) into a quadruple (P_{0}, S^{0}, S^{1}, S^{2}), where S^{0} is a tabloid of shape λ, S^{1} is a (< (a + c))-tabloid of shape λ, and S^{2} is a (0–h)-tabloid of shape λ, such that

w((P, T^{1}, T^{2})) = sgn(S^{2}) q^{n(P_{0})+w_{h}(S^{0})+n(S^{1})+n(S^{2})}.  (3.7)

The pair (P_{0}, S^{0}) is obtained from P by using the Hillman–Grassl algorithm as described in section 2. S^{1} and S^{2} are obtained by doing the following operation on T^{1} and T^{2} for each cell ρ in λ. If a + c_{ρ} ≥ h_{ρ} then interchange T_{ρ}^{1} and T_{ρ}^{2}. If a + c_{ρ} < h_{ρ} and if T_{ρ}^{1} + T_{ρ}^{2} < a + c_{ρ} (which implies T_{ρ}^{1} = 0) then again interchange T_{ρ}^{1} and T_{ρ}^{2}. If a + c_{ρ} < h_{ρ} and if T_{ρ}^{1} + T_{ρ}^{2} ≥ h_{ρ} (which implies T_{ρ}^{1} = a + c_{ρ}) then replace T_{ρ}^{1} by T_{ρ}^{1} + T_{ρ}^{2} − h_{ρ} and T_{ρ}^{2} by h_{ρ}. Similarly as above, by a simple case-by-case analysis the following facts can be checked: The new tabloids S^{1} is a (< (a + c))-tabloid and the new tabloid S^{2} is a (0–h)- tabloid, in all cases. The relation (3.7) is satisfied. This transformation can be reversed. And, T^{1} ≠ 0 if and only if S^{2} ≠ 0 under this transformation.

In the second step, we choose the least cell ρ in our fixed total order such that S_{ρ}^{0} or S_{ρ}^{2} is nonzero. If S_{ρ}^{2} is nonzero then replace S_{ρ}^{2} by 0, thus obtaining S̄^{2}, and add 1 to S_{ρ}^{0}, thus obtaining S̄^{0}. If S_{ρ}^{2} is 0 then replace S_{ρ}^{2} by h_{ρ}, thus obtaining S̄^{2}, and subtract 1 from S_{ρ}^{0}, thus obtaining S̄^{0}. Finally, in the third step we apply the inverse of the above transformation to (P′, S̄^{0}, S^{1}, S̄^{2}), thus obtaining (P̄, T̄^{1}, T̄^{2}). We define i_{R}((P, T^{1}, T^{2})) to be (P̄, T̄^{1}, T̄^{2}). By construction we have w((P, T^{1}, T^{2})) = −w(P̄, T̄^{1}, T̄^{2}), as required.

Also here, we leave it to the reader to verify that i_{R} is a sign-reversing and weightpreserving (with respect to the signed weight (3.5)) involution on X \ X_{R}. □

4. Conclusion. There are many other product formulas for plane partition generating functions, and only for a few of them combinatorial proofs are known. However, many of the formulas for which no combinatorial proof is known allow nice combinatorial formulations. Therefore there should also be nice combinatorial proofs that explain these forms of the formulas. Below we list a few candidates that desire to be proved combinatorially.

(1) In [4] it is proven that the number of plane partitions of a given staircase shape with bounded entries is a product involving the hook-lengths and some generalized contents of the staircase shape. Is it possible to extend the ideas of section 2 to this case? Of course, it cannot be that easy since there does not exist a weighted version of this result.

(2) Counting plane partitions subject to various symmetries acquired a lot of attention during the past 25 years. There are 10 symmetry classes (see the survey in Stanley’s paper [16]), for each of which there is a nice product formula. Now all the formulas are proven (except for the q-analogue of Case 4; the formulas that were only conjectured at the time of [16] are proved in [1, 6, 18]). Case 1, MacMahon’s generating function [7, sec. 429, proof in sec. 494] for plane partitions of rectangular shape with bounded entries, is easily seen to be contained in Theorem 1. Therefore this paper provides a bijective proof for Case 1. In all other cases the existing proofs are to the more or lesser extent noncombinatorial. Case 2, the generating function for symmetric plane partitions of square shape with bounded entries, looks like a promising candidate to be proved combinatorially. This is because symmetric plane partitions can be seen as shifted plane partitions, by forgetting about one half of the symmetric plane partition, where the entries of the shifted plane partition off the diagonal contribute twice their size to the norm. There exists a shifted version of the Hillman–Grassl correspondence, due to Sagan [11, sec. 3,4], that would provide the analogue for the first step in our bijection in section 2. So it remains to find the shifted analogues of Algorithms C and C*. Though there is also a shifted version of jeu de taquin (cf. [12]), it does not seem to help here. And the fact that there is a nice product formula for the generating function for symmetric plane partitions of square shape only (and not for an arbitrary fixed symmetric shape) adds to the evidence that a new idea is needed in this case.

On the other hand, in all the Cases 1–4 the formulas can be written in a form such that the product is indexed by the boxes of the region in which the plane partitions under consideration are contained, which is a highly combinatorial description. So there must be bijective proofs explaining these forms of the formulas.

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 C and C* for λ = (4, 3, 3, 1) and a = 4, setting up a mapping between the two sides of Figure 2. See the specific descriptions given in Examples C and C* of how to read the following tables.

1 1 3 8 2 3 4 5 7 8 7 0 0 0 0 0 0 0 0 0 0 0  \underrightarrow{(C1)} 1 1 3 8 2 3 4 5 7 \underline{4} 7 \underrightarrow{(2.4)} 1 1 3 8 2 3 4 5 5 7 7 \underrightarrow{(C3)}

\begin{matrix}− & − & − & − \\ − & − & − \\ − & − & − \\ − \end{matrix} \underleftarrow{(C*3)} 1 1 3 8 2 3 4 5 7 8 7 \underleftarrow{(2.17)} 1 1 3 8 2 3 4 5 \underline{\underline{8}} 7 7 \underleftarrow{(C*1)}

1 1 3 8 2 3 4 5 5 [figure] 7 7 0 0 0 0 0 0 0 0 1 0 0 \underrightarrow{(C1)} 1 1 3 \underline{1} 2 3 4 5 5 7 7 \underrightarrow{(2.4)} 1 1 2 3 2 3 4 5 5 7 7 \underrightarrow{(C3)}

\begin{matrix}− & − & − & − \\ − & − & − \\ − & 8 & − \\ − \end{matrix} \underleftarrow{(C*3)} 1 1 3 8 2 3 4 5 5 7 7 \underleftarrow{(2.17)} 1 1 \underline{\underline{8}} 3 2 3 4 5 5 7 7 \underleftarrow{(C*1)}

1 1 2 [figure] 3 2 3 4 5 5 7 7 0 0 1 0 0 0 0 0 1 0 0 \underrightarrow{(C1)} 1 1 2 3 2 3 4 5 5 7 6 \underrightarrow{(C3)}

\begin{matrix}− & − & 8 & − \\ − & − & − \\ − & 8 & − \\ − \end{matrix} \underleftarrow{(C*3)} 1 1 2 3 2 3 4 5 5 7 7 \underleftarrow{(C*1)}

1 1 2 3 2 3 4 5 5 7 6 [figure] 0 0 1 0 0 0 0 0 1 0 1 \underrightarrow{(C1)} 1 1 2 3 2 3 4 5 5 \underline{3} 6 \underrightarrow{(2.4)} 1 1 2 3 2 3 4 5 \underline{4} 5 6 \underrightarrow{(2.4)} 1 1 2 3 2 3 4 5 5 5 6 \underrightarrow{(C3)}

\begin{matrix}− & − & 8 & − \\ − & − & − \\ − & 8 & − \\ 7 \end{matrix} \underleftarrow{(C*3)} 1 1 2 3 2 3 4 5 5 7 6 \underleftarrow{(2.17)} 1 1 2 3 2 3 4 5 \underline{\underline{7}} 5 6 \underleftarrow{(2.17)} 1 1 2 3 2 3 4 \underline{\underline{7}} 5 5 6 \underleftarrow{(C*1)}

1 1 2 3 2 3 4 5 [figure] 5 5 6 0 0 1 0 0 0 0 1 1 0 1  \underrightarrow{(C1)} 1 1 2 3 2 3 4 5 5 5 \underline{5} \underrightarrow{(2.5)} 1 1 2 3 2 3 4 4 5 5 5 \underrightarrow{(C3)}

\begin{matrix}− & − & 8 & − \\ − & − & − \\ 7 & 8 & − \\ 7 \end{matrix} \underleftarrow{(C*3)} 1 1 2 3 2 3 4 5 5 5 6 \underleftarrow{(2.18)} 1 1 2 3 2 3 4 \underline{\underline{6}} 5 5 5 \underleftarrow{(C*1)}

1 1 2 3 2 3 4 4 [figure] 5 5 5 0 0 1 0 0 0 0 2 1 0 1  \underrightarrow{(C1)} 1 1 2 3 2 3 4 4 5 5 \underline{4} \underrightarrow{(2.5)} 1 1 2 3 2 3 4 3 5 5 4 \underrightarrow{(C3)}

\begin{matrix}− & − & 8 & − \\ − & − & − \\ 6 & 8 & − \\ 6 \end{matrix} \underleftarrow{(C*3)} 1 1 2 3 2 3 4 4 5 5 5 \underleftarrow{(2.18)} 1 1 2 3 2 3 4 \underline{\underline{5}} 5 5 4 \underleftarrow{(C*1)}

1 1 2 3 2 3 4 3 [figure] 5 5 4 0 0 1 0 0 0 0 3 1 0 1 \underrightarrow{(C1)} 1 1 2 3 2 3 4 3 5 \underline{1} 4 \underrightarrow{(2.4)} 1 1 2 3 2 3 4 3 \underline{2} 5 4 \underrightarrow{(2.5)} 1 1 2 3 2 \underline{1} 4 3 3 5 4 \underrightarrow{(2.4)}

\begin{matrix}− & − & 8 & − \\ − & − & − \\ 5 & 8 & − \\ 5 \end{matrix} \underleftarrow{(C*3)} 1 1 2 3 2 3 4 3 5 5 4 \underleftarrow{(2.17)} 1 1 2 3 2 3 4 3 \underline{\underline{5}} 5 4 \underleftarrow{(2.18)} 1 1 2 3 2 \underline{\underline{5}} 4 3 3 5 4 \underleftarrow{(2.17)}

\underrightarrow{(2.4)} 1 1 2 3 2 2 4 3 3 5 4 \underrightarrow{(C3)}

\underleftarrow{(2.17)} 1 1 2 3 \underline{\underline{5}} 2 4 3 3 5 4 \underleftarrow{(C*1)}

1 1 2 3 2 [figure] 2 4 3 3 5 4 0 0 1 0 1 0 0 3 1 0 1 \underrightarrow{(C1)} 1 1 2 3 2 2 4 3 3 \underline{1} 4 \underrightarrow{(2.5)} 1 1 2 3 2 2 \underline{0} 3 3 4 4 \underrightarrow{(2.5)} \begin{matrix}1 & 1 & \underline{−1} & 3 \\ 2 & 2 & 2 \\ 3 & 3 & 4 \\ 4 \end{matrix} \underrightarrow{(2.4)}

\begin{matrix}− & − & 8 & − \\ 5 & − & − \\ 5 & 6 & − \\ 5 \end{matrix} \underleftarrow{(C*3)} 1 1 2 3 2 2 4 3 3 5 4 \underleftarrow{(2.18)} 1 1 2 3 2 2 \underline{\underline{5}} 3 3 4 4 \underleftarrow{(2.18)} 1 1 \underline{\underline{5}} 3 2 2 2 3 3 4 4 \underleftarrow{(2.17)}

\underrightarrow{(2.4)} 1 \underline{0} 1 3 2 2 2 3 3 4 4 \underrightarrow{(2.4)} 1 1 1 3 2 2 2 3 3 4 4 \underrightarrow{(C3)}

\underleftarrow{(2.17)} 1 \underline{\underline{5}} 1 3 2 2 2 3 3 4 4 \underleftarrow{(2.17)} \underline{\underline{5}} 1 1 3 2 2 2 3 3 4 4 \underleftarrow{(C*1)}

1 [figure] 1 1 3 2 2 2 3 3 4 4 1 0 1 0 1 0 0 3 1 0 1

\begin{matrix}5 & − & 7 & − \\ 5 & − & − \\ 5 & 6 & − \\ 5 \end{matrix}

References

1. G. E. Andrews, Plane partitions V: The t.s.s.c.p.p. conjecture, J. Combin. Theory Ser. A 66 (1994), 28–39.

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

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

4. C. Krattenthaler, A determinant evaluation and some enumeration results for plane partitions, Number-Theoretic Analysis (E. Hlawka, R. F. Tichy, eds.), Lect. Notes in Math. 1452, Springer-Verlag, Berlin, New York, 1990, pp. 121–131.

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

6. G. Kuperberg, Symmetries of plane partitions and the permanent-determinant method, J. Combin. Theory Ser. A 68 (1994), 115–151.

7. P. A. MacMahon, Combinatory Analysis, Cambridge University Press, 1916; reprinted by Chelsea, New York, 1960.

8. J. C. Novelli, I. M. Pak and A. V. Stoyanovsii, A new bijective proof of the hook-length formula, preprint.

9. I. M. Pak and A. V. Stoyanovskii, A bijective proof of the hook-length formula and its analogues, Funkt. Anal. Priloz. 26, No. 3 (1992), 80–82, English translation in Funct. Anal. Appl. 26 (1992), 216–218.

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

11. B. E. Sagan, Enumeration of partitions with hooklengths, Europ. J. Combin. 3 (1982), 85–94.

12. B. E. Sagan, Shifted tableaux, Schur Q-functions, and a conjecture of R. Stanley, J. Combin. Theory Ser. A 45 (1987), 62–103.

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

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

15. R. P. Stanley, Theory and applications of plane partitions: Part 2, Stud. Appl. Math 50 (1971), 259–279.

16. R. P. Stanley, Symmetries of plane partitions, J. Combin. Theory A 43 (1986), 103–113; Erratum 44 (1987), 310.

17. D. Stanton and D. White, Constructive Combinatorics, Undergraduate Texts in Math., Springer–Verlag, New York, Berlin Heidelberg, Tokyo, 1986.

18. J. R. Stembridge, The enumeration of totally symmetric plane partitions, Adv. in Math. 111 (1995), 227–245.

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