BIJECTIONS FOR HOOK PAIR IDENTITIES

C. Krattenthaler^{†}

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

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

Submitted: March 4, 2000; Accepted: April 10, 2000.

Abstract. Short, bijective proofs of identities for multisets of ‘hook pairs’ (arm-leg pairs) of the cells of certain diagrams are given. These hook pair identities were originally found by Regev.

1. Introduction. In their work [7] on asymptotic analysis of degrees of sequences of symmetric group characters, Regev and Vershik obtained some hook formulas, which led them to conjecture surprising identities for multisets of hooks. These identities were shortly thereafter proved independently by Bessenrodt [1], Janson [2], and Regev and Zeilberger [8]. Another such identity was added by Postnikov and Regev [4]. Moving one step ahead, Regev [5] observed that in fact all these identities are not only true as identities for multisets of hooks, but even as identities for multisets of the corresponding arm-leg pairs. He called the latter (and we follow this convention) “hook pairs.” As is shown in [5], these identities imply several nice formulas for special evaluations of Schur and Jack polynomials. All the aforementioned identities feature hooks and arm-leg pairs of regions which are built out of (nonshifted) Ferrers diagrams. Finally, in [6], Regev provided similar identities for regions resulting from shifted diagrams.

Regev proves his multiset identities in [5, 6] by inductive arguments. (The proofs in [2, 4, 8] are also inductive, only Bessenrodt’s argument in [1] is combinatorial.) The purpose of this paper is to provide short, bijective proofs of all these identities. In fact, what I am going to demonstrate is that there is just one “master bijection” out of which all the identities result straightforwardly.

In the next section we provide all the relevant definitions and formulate, in Theorems 1–3, three key identities from [5, 6], which straightforwardly imply all other multiset identities in these two papers (and, thus, all the multiset identities in [1, 2, 4, 7, 8]). In the subsequent Section 3, we present our “master bijection,” which

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 05A15; Secondary 05A19 05E10.

Key words and phrases. hook pairs, hook-content formulas, arm, leg, multiset identities.

† Research partially supported by the Austrian Science Foundation FWF, grant P13190-MAT

immediately implies the first of these identities, Theorem 1. The resulting proofs of Theorems 2 and 3 are then given in Sections 4 and 5.

2. Identities for multisets of hook pairs. We recall some basic partition terminology (cf. [3, Ch. I, Sec. 1]). A partition is a sequence μ = (μ_{1}, μ_{2}, …, μ_{ℓ}) of positive integers, arranged in weakly decreasing order. We identify a partition μ with its Ferrers diagram, which is an array of cells with ℓ left-justified rows and μ_{i} cells in row i. To each cell, c say, we associate two numbers, the arm length and the leg length of c. The arm length a(c) of c is the number of cells which are (strictly) to the right of c and in the same row as c. Similarly, the leg length l(c) of c is the number of cells which are (strictly) below of c and in the same column as c. We call the arm-leg pair (a(c), l(c)) of a cell c the hook pair of c. For example, Figure 1 shows the Ferrers diagram (5, 3, 3, 1). The marked cell has arm length 3 and leg length 2, thus, the corresponding hook pair being (3, 2). We adopt the convention of writing a^{b} for a part a of a partition which occurs b times, so that the partition (5, 3, 3, 1) could also be written as (5, 3^{2}, 1).

×_{Figure 1}

Now let the partition μ = (μ_{1}, μ_{2}, …, μ_{ℓ}) be given, and choose k and n such that μ fits in the n × k rectangular partition (k^{n}), i.e., k ≥ μ_{1} and n ≥ ℓ. Let us denote the rectangle (k^{n}) by R_{n,k}. Under these assumptions, we form two skew diagrams, SR_{n,k}(μ) and SR_{n,k}(μ̃). The skew diagram SR_{n,k}(μ) is formed by starting with the k × n rectangle R_{n,k}, removing a copy of the partition μ from the top-left corner of R_{n,k}, and then gluing a copy of μ to the right of R_{n,k} so that the first row of this copy of μ is glued to the first row of R_{n,k}. See Figure 2.b for an example with k = 6, n = 4, μ = (5, 2, 1). The skew diagram SR_{n,k}(μ̃) is formed in a similar way. Again one starts with the k × n rectangle R_{n,k}. But now a copy of the partition μ which is rotated by 180^{∘} is removed from the bottom-right corner of R_{n,k}, and then a copy of μ which is rotated by 180^{∘} is glued to the left of R_{n,k} so that the last row of this rotated copy of μ is glued to the last row of R_{n,k}. See Figure 2.c for an example with k = 6, n = 4, μ = (5, 2, 1).

Now we are ready to state the first of Regev’s hook pair identities [5, Theorem 2].

Theorem 1. The multiset of hook pairs of the cells of SR_{n,k}(μ) is identical with the multiset of hook pairs of the cells of SR_{n,k}(μ̃).

Still given a partition μ = (μ_{1}, μ_{2}, …, μ_{ℓ}) and integers k and n such that k ≥ μ_{1} and n ≥ ℓ, we form another skew diagram, SQ(n, k, μ), by starting again with the

. . . . .^{.....} . . . . .^{.....}^{.....} . . . . .^{.....}^{.....}^{.....}^{.....}^{.....} . . . . .. . . . . . . . . . . . . . . . . . . .
a. The rectangle R_{4,6} b. The skew diagram SR_{4,6}((5, 2, 1))

.......................... . . . .. . . . .. . . . . . . . . . . . . . . . . . . .^{.....}^{.....} . . . . .. . . . .^{.....}
c. The skew diagram SR_{4,6}({ \atop (5, 2, 1)})

Figure 2

..................... . . . .. . . . .. . . . . . . . . . . . . . .^{.....}^{.....} . . . . .. . . . .^{.....}

The skew diagram SQ(4, 6, (4, 2, 1))

Figure 3

n × k rectangle R_{n,k}, removing a copy of μ which is rotated by 180^{∘} from the bottomright corner of R_{n,k}, gluing such a rotated copy of μ to the left of R_{n,k} in the same way as before when we formed SR_{n,k}(μ̃), and finally gluing a rotated (by 180^{∘}) copy of μ to the top of R_{n,k} so that the last column of this rotated copy of μ is glued to the last column of R_{n,k}. See Figure 3 for an example with k = 6, n = 4, μ = (4, 2, 1).

The second of Regev’s hook pair identities [5, Theorem 1.(a)] reads as follows.

Theorem 2. The multiset of hook pairs of the cells of SQ(n, k, μ) is equal to the union of the multiset of hook pairs of the cells of R_{n,k} and the multiset of hook pairs of the cells of μ.

p(μ)  μ q(R(a)) R(a)  . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . q(A)A_{2} SQ(a, μ)_{Figure 4}

Finally we concern ourselves with Regev’s refinement [6] of Theorem 2 for partitions μ of the form μ = (λ_{1}, …, λ_{s} | λ_{1} − 1, …, λ_{s} − 1) (in Frobenius notation; cf. [3, p. 3]), where λ_{1} > ⋯ > λ_{s} > 0. Given such a partition μ, we split it into two “halves” by cutting it along the diagonal as is illustrated in the top-left part of Figure 4 in an example where μ = (22^{3}, 16^{3}, 15^{6}, 12^{2}, 6, 3^{6}) = (21, 20, 19, 12, 11, 10, 8, 7, 6, 5, 4, 3 | 20, 19, 18, 11, 10, 9, 7, 6, 5, 4, 3, 2). Denote the lower-left region by p(μ). Given a ≥ μ_{1} − 1 = λ_{1}, let R(a) denote the a × (a + 1) rectangle R_{a,a+1} = ((a + 1)^{a}). Again, we split it into two halves, by cutting it along the diagonal as is illustrated in the bottom-left part of Figure 4 for a = 21. Denote the upper-right region by q(R(a)). Now consider SQ(a, μ) := SQ(a, a + 1, μ). Recall that this region consists of the a × (a + 1) rectangle R_{a,a+1}, of which a rotated copy of μ has been removed from its bottom-right corner, and on top of which and to the left of which was placed a rotated copy of μ each. Once again we split it into two halves along the diagonal of the rectangle R_{a,a+1}, as is illustrated in Figure 4. (There, we have chosen a = 21 and μ = (22^{3}, 16^{3}, 15^{6}, 12^{2}, 6, 3^{6}). Since it is of no relevance for us here, we have omitted to display the rotated copy of μ placed to the left of the rectangle R_{21,22}.) The part of SQ(a, μ) above the diagonal (in the example of Figure 4 this is the region inside the thick boundary) consists of two parts, the rotated copy of μ on top, which we denote by A_{2}, and the part which remained from R(a), which we denote by q(A).

If H is a subregion of G (an example being H = p(μ) and G = μ), let us write HP_{G}(H) for the multiset of hook pairs of the cells of H measured inside G, i.e., arm length and leg length are taken with respect to the boundaries of G (and not with respect to the boundaries of H). (See [6, Sec. 1] for an elaborate example. The definition is motivated by the definition of shifted hook length when p(μ) is regarded as a shifted partition, cf. [3, Ch. III, Sec. 8, Ex. 12].)

With this notation, the main result from [6, Theorem I, (I.1)] reads as follows.

Theorem 3. With the assumptions and notations as explained above, the following identity holds between multisets of hook pairs:

HP_{μ}(p(μ)) ∪ HP_{R(a)}(q(R(a))) = HP_{SQ(a,μ)}(q(A)) ∪ HP_{SQ(a,μ)}(A_{2}).

3. The “master bijection” — Proof of Theorem 1. It is obvious that for a proof of Theorem 1 it suffices to consider just those cells c of SR_{n,k}(μ) and SR_{n,k}(μ̃) for which the corresponding hook pairs (a(c), l(c)) have a fixed arm length, a(c) = d say, and to show that the multiset of leg lengths of these cells in SR_{n,k}(μ) agrees with the multiset of leg lengths of these cells in SR_{n,k}(μ̃). To illustrate what we mean, choose n = 10, k = 8, μ = (7, 7, 5, 4, 4, 3, 3, 1). The skew diagrams SR_{n,k}(μ) and SR_{n,k}(μ̃) with this choice of parameters are displayed in Figure 5. The Figure also shows the cells in SR_{n,k}(μ) and SR_{n,k}(μ̃) which have arm length d = 2. The numbers inside the cells are the corresponding leg lengths. We call the cells of a region R which have arm length d, the broken column of R in distance d. We have to show that, in general, for any d the multiset of leg lengths of cells in the broken column of SR_{n,k}(μ) in distance d is equal to the multiset of leg lengths of cells in the broken column of SR_{n,k}(μ̃) in distance d.

0 1 2 1 2 2 3 4 1 2 SR_{n,k}(μ) 0 1 2 1 2 3 4 2 1 2 SR_{n,k}(μ̃)_{Figure 5}

If we rotate SR_{n,k}(μ̃) by 180^{∘}, then SR_{n,k}(μ) and the rotated SR_{n,k}(μ̃) fit together side by side. Figure 6 shows the result in the case of our example of Figure 5. The numbers in the broken column which is to the left of the staircase that forms the border between the two regions are the vertical distances of the cells to the “bottom” of the diagram (consisting of the staircase and the base line to the left of the staircase), while the numbers in the broken column which is to the right of the staircase are the vertical distances of the cells to the “top” of the diagram (consisting of the staircase and the top line to the right of the staircase). Our task is to set up a bijection between these two multisets of numbers.

0 1 2  1 2 2 3 4  1 2 2 1 2  4 3 2 1 2  1 0_{Figure 6}

Lemma. Let S be a given staircase (see Figure 6). Let C_{l} be the broken column in distance d left of S, and let C_{r} be the broken column in distance d right of S. Then there is an explicit bijection (the “master bijection”) between the multiset {l(c) : c ∈ C_{l}} and the multiset {l′(c) : c ∈ C_{r}}. Here, l(c) denotes the distance of cell c to the bottom of the diagram, and l′(c) denotes the distance of cell c to the top of the diagram.

Proof. We claim that the following algorithm defines such a bijection:

(MB1) Read the numbers in the cells of C_{l} one after the other by considering the cells in the order bottom to top. While reading, out of each maximal increasing subsequence of numbers form a stack. Place the stacks in such a way that numbers of the same size are at the same height. (In our example in Figure 6, the numbers 0, 1, 2, 1, 2, 2, 3, 4, 1, 2 are read in. See the left part of Figure 7 for the result after dividing this sequence into stacks.)

(MB2) Move all the numbers of the first stack which are smaller than the numbers in the second stack to the second stack. Repeat this procedure with the second and third stack, etc. (Thus, in our example in the left part of Figure 7 we would move 0 from the first to the second stack, 0, 1 from the second to the third, and 0 from the third to the fourth stack. The result is displayed in the right part of Figure 7.)

(MB3) Read the numbers in the result in the order from the last stack to the first, and in each stack from bottom to top. (Thus, from the right part of Figure 7 we would read 0, 1, 2, 1, 2, 3, 4, 2, 1, 2.)

The claim is that the output of this algorithm is the numbers in the cells of C_{r} read by considering the cells in the order top to bottom (which for our running example can be verified in Figure 6). Clearly, this would immediately prove the Lemma because it is obvious how to invert the algorithm.

4 3 2  2  2  2 1  1  1 0  4 3 2  2  2  2 1  1  1 0_{Figure 7}

In order to prove the claim, we first introduce some notation. The staircase S consists of, alternately, vertical and horizontal pieces. Let the lengths of these pieces be v_{1}, h_{1}, v_{2}, h_{2}, …, v_{p−1}, h_{p−1}, v_{p}, where v_{i} stands for the length of the i-th vertical piece, if counted from bottom to top, and where h_{i} stands for the length of the i-th horizontal piece. In the example in Figure 6 we have v_{1} = 2, h_{1} = 1, v_{2} = 1, h_{2} = 2, v_{3} = 2, h_{3} = 1, v_{4} = 2, h_{4} = 1, v_{5} = 1, h_{5} = 2, v_{6} = 2.

Furthermore, let the maximal increasing subsequences when reading the numbers from C_{l} (from bottom to top) be 0, 1, …, M_{1}; m_{2}, m_{2} + 1, …, M_{2}; …; m_{q}, m_{q} + 1, …, M_{q}, so that the corresponding diagram in the style of Figure 7 looks like

M_{2}  M_{q}
⋮  M_{3}  ⋮
M_{1}  m_{2}  ⋮  …  m_{q}
⋮  m_{3}

0

Then there exist uniquely determined integers i_{1}, …, i_{q} and j_{1}, …, j_{q} with 1 ≤ i_{1} < ⋯ < i_{q} = p, 1 = j_{1} < ⋯ < j_{q} ≤ p, and j_{t} ≤ i_{t} for all t, such that

M_{1} = v_{j_{1}} + ⋯ + v_{i_{1}} − 1, h_{j_{1}} + ⋯ + h_{i_{1}−1} ≤ d and h_{j_{1}} + ⋯ + h_{i_{1}} > d,
m_{2} = v_{j_{2}} + ⋯ + v_{i_{1}},  h_{j_{2}−1} + ⋯ + h_{i_{1}} > d and h_{j_{2}} + ⋯ + h_{i_{1}} ≤ d,
M_{2} = v_{j_{2}} + ⋯ + v_{i_{2}} − 1, h_{j_{2}} + ⋯ + h_{i_{2}−1} ≤ d and h_{j_{2}} + ⋯ + h_{i_{2}} > d, (1)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
m_{q} = v_{j_{q}} + ⋯ + v_{i_{q−1}}, h_{j_{q}−1} + ⋯ + h_{i_{q−1}} > d and h_{j_{q}} + ⋯ + h_{i_{q−1}} ≤ d,
M_{q} = v_{j_{q}} + ⋯ + v_{i_{q}} − 1, h_{j_{q}} + ⋯ + h_{i_{q}−1} ≤ d.

Similarly, let the maximal increasing subsequences when reading the numbers from C_{r} (from top to bottom) be 0, 1, …, M̃_{q}; …; m̃_{2}, m̃_{2} +1, …, M̃_{2}; m̃_{1}, m̃_{1} +1, …, M̃_{1}, so that the corresponding diagram in the style of Figure 7 looks like

M̃_{2}  M̃_{q}
M̃_{1}  ⋮  M̃_{q−1}  ⋮
⋮  m̃_{2}  …  ⋮  ⋮
m̃_{1}  m̃_{q−1}  ⋮

0

Then there exist uniquely determined integers j̃_{1}, …, j̃_{q} and ĩ_{1}, …, ĩ_{q} with 1 ≤ j̃_{1} < ⋯ < j̃_{q} = p, 1 = ĩ_{1} < ⋯ < ĩ_{q} ≤ p, and j̃_{t} ≥ ĩ_{t} for all t, such that

M̃_{q} = vj̃_{q} + ⋯ + vĩ_{q} − 1,
h_{j̃_{q}−1} + ⋯ + hĩ_{q} ≤ d and  h_{j̃_{q}−1} + ⋯ + h_{ĩ_{q}−1} > d,
m̃_{q−1} = vj̃_{q−1} + ⋯ + vĩ_{q},
hj̃_{q−1} + ⋯ + h_{ĩ_{q}−1} > d and h_{j̃_{q−1}−1} + ⋯ + h_{ĩ_{q}−1} ≤ d,
M̃_{q−1} = vj̃_{q−1} + ⋯ + vĩ_{q−1} − 1,
h_{j̃_{q−1}−1} + ⋯ + hĩ_{q−1} ≤ d and h_{j̃_{q−1}−1} + ⋯ + h_{ĩ_{q−1}−1} > d, (2)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
m̃_{1} = vj̃_{1} + ⋯ + vĩ_{2},
hj̃_{1} + ⋯ + h_{ĩ_{2}−1} > d and  h_{j̃_{1}−1} + ⋯ + h_{ĩ_{2}−1} ≤ d,
M̃_{1} = vj̃_{1} + ⋯ + vĩ_{1} − 1, h_{j̃_{1}−1} + ⋯ + hĩ_{1} ≤ d.

The claim is equivalent to the assertion that M̃_{t} = M_{t} and m̃_{t} = m_{t+1} for all t. In view of (1) and (2), this would immediately follow once we show that j̃_{t} = i_{t} and ĩ_{t} = j_{t} for all t. In order to do that, it suffices to derive the inequalities in (2) from those of (1). Indeed, the general form of the inequalities in (1) is

h_{j_{t+1}−1} + ⋯ + h_{i_{t}} > d and h_{j_{t+1}} + ⋯ + h_{i_{t}} ≤ d,  (3)
h_{j_{t}} + ⋯ + h_{i_{t}−1} ≤ d and h_{j_{t}} + ⋯ + h_{i_{t}} > d.  (4)

In particular, the first inequality in (3) implies that

h_{j_{t+1}−1} + ⋯ + h_{i_{t+1}−1} > d,  (5)

since by assumption we have i_{t} ≤ i_{t+1} −1. Similarly, the first inequality in (4) implies that

h_{j_{t+1}−1} + ⋯ + h_{i_{t}−1} ≤ d,  (6)

since by assumption we have j_{t} ≤ j_{t+1} − 1. Altogether, the inequalities in (3)–(6) cover those of (2) with j̃_{t} = i_{t} and ĩ_{t} = j_{t}.

This concludes the proof of the Lemma.

4. Proof of Theorem 2. The preceding bijection allows us to construct a bijection for Theorem 2. We have to set up a bijection between the hook pairs in R_{n,k} ∪ μ and the hook pairs in SQ(n, k, μ).

To begin with, we identify the hook pairs in a subregion of R_{n,k} with the hook pairs in a subregion of SQ(n, k, μ). The subregion of R_{n,k}, S_{1} say, consists of the first k − μ_{1} columns of R_{n,k} together with a copy of μ, reflected upside down, on the bottom of R_{n,k} (see the left part of Figure 8 for an example with n = 18, k = 24, μ = (15^{3}, 6^{3}, 3^{6})). The subregion of SQ(n, k, μ), S_{2} say, consists of the (rotated) copy of μ on the left of SQ(n, k, μ), together with the next k − μ_{1} columns of SQ(n, k, μ) (see the right part of Figure 8).

. . . . .. . . . .. . . . .. . . . . S_{1}  T_{1} R_{n,k}  . . . . .. . . . .. . . . .. . . . . S_{2}  T_{2} SQ(n, k, μ)_{Figure 8}

It is completely obvious that, row-wise, the hook pairs in these subregions must be the same. I.e., reading hook pairs from left to right in the first row of S_{1} gives exactly the same as reading hook pairs from left to right in the first row of S_{2}, the same being true for the second rows, etc.

Therefore, what remains is to identify the hook pairs in the remaining regions. Let us denote the complement of S_{1} in R_{n,k} by T_{1}, and the complement of S_{2} in SQ(n, k, μ) by T_{2} (see Figure 8). Then we have to identify the hook pairs in T_{1} ∪ μ with the hook pairs in T_{2}.

Let us again consider broken columns in some given distance d from the right boundaries. This is indicated in Figure 9. (In this example, n = 18, k = 24, μ = (15^{3}, 6^{3}, 3^{6}), and d = 4.) The figure also shows “fake” parts of broken columns for μ and T_{2}, i.e., parts of broken columns which lie outside of the regions. They are shown with dotted surroundings and should be ignored for the moment. We have to identify the multiset of leg lengths in the broken columns of μ and T_{1} (excluding the “fake” part) with the multiset of leg lengths in the broken column of T_{2} (excluding the “fake” part). Let us denote the multiset of leg lengths in the broken column of μ

. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .  μ . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . T_{1}  . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .  T_{2} . . . . .. . . . .. . . . .. . . . . . . . . .. . . . .. . . . .. . . . ._{Figure 9}

by L(μ; d), and similarly for T_{1} and T_{2}.

In order to accomplish this identification, we observe that the Lemma from Section 3 provides a bijection between the multiset of leg lengths in the broken column of μ, the “fake” part included, and the part of the broken column of T_{2} which is to the left of the (rotated) copy of μ that has been removed from SQ(n, k, μ) (indicated by dotted lines in Figure 9), again the “fake” part included. (In Figure 9, this part of the broken column is the one below the dotted horizontal line running through T_{2}, the “fake” part included.) Let us denote the former multiset by L_{f}(μ; d), and the latter by L_{f}(T_{2}; d).

Furthermore, with the notation [[N]] := {0, 1, …, N − 1}, we have

L(μ; d) ∪ L(T_{1}; d) = (L_{f}(μ; d)\[[ℓ(μ) + 1 − min{k : μ_{k} ≤ d}]])

∪ ([[n]]\[[max{k : μ_{k} ≥ μ_{1} − d}]])

= (L_{f}(μ; d) ∪ [[n]])\([[ℓ(μ) + 1 − min{k : μ_{k} ≤ d}]] ∪ [[max{k : μ_{k} ≥ μ_{1} − d}]]), (7)

where ℓ(μ) denotes the number of parts of μ (equivalently, the number of rows of μ), and

L(T_{2}; d) = (L_{f}(T_{2}; d)\[[max{k : μ_{k} + d ≥ μ_{1}}]])

∪ ([[n]]\[[ℓ(μ) + 1 − min{k : μ_{k} ≤ d}]])

= (L_{f}(T_{2}; d) ∪ [[n]])\([[max{k : μ_{k} + d ≥ μ_{1}}]] ∪ [[ℓ(μ) + 1 − min{k : μ_{k} ≤ d}]]). (8)

In view of our previous observation that the multisets L_{f}(μ; d) and L_{f}(T_{2}; d) are in bijection, it is now completely evident that the multisets L(μ; d) ∪ L(T_{1}; d) and L(T_{2}; d) agree.

Remark. The argument thus far was not completely bijective. But it could easily be made bijective, for example, using the simplified version of the involution principle described in [9, bottom of p. 80ff]. There are other possibilities, but none of these seem to yield naturally defined mappings. In particular, these would not add any further insight. It is the “master bijection” from Section 3 and the computations in (7) and (8) which really explain why Theorem 2 is true.

5. Proof of Theorem 3. In a similar manner, Theorem 3 can be proved. We have to prove that the hook pairs in p(μ) and q(R(a)) (measured inside μ and R(a), respectively) are the same as the hook pairs in q(A) and A_{2} (measured inside SQ(a, μ)), see Figure 4.

Again, it suffices to consider a broken column in some distance d from the right boundaries in the corresponding figures, and to show that the leg lengths along the broken columns agree (see Figure 10, where d = 4; the “fake” part of the broken column in p(μ) should be ignored for the moment), i.e.,

L(p(μ); d) ∪ L(q(R(a)); d) = L(q(A); d) ∪ L(A_{2}; d),

using the same notation as before.

Again, the key is the Lemma from Section 3. What Figure 11 shows is obtained by the following construction: In Figure 10, in the part which shows p(μ), the extremal point, denoted by M, on the “diagonal” is circled. The corresponding point, denoted by M′, in the part which shows SQ(a, μ) is also circled. The top-most part of the broken column in p(μ) reaches a certain height, h say, above M. (The height h can be any nonnegative integer.) In Figure 10, we have h = 2. Now cut the Figure which represents SQ(a, μ) by the horizontal line which is h units below M′. In addition, cut off A_{2}. This gives Figure 11 (where h = 2), upon also adding a broken column in distance d to the right of the path which runs from bottom-left to top-right, and upon completing a broken column in distance d to the left of the path.

Let us denote the leg lengths (measured “to the bottom,” i.e., with respect to the path which runs from bottom-left to top-right) in the broken column to the left by L_{f}(q(A); d). These leg lengths contain all those which appear in L(q(A); d), plus the additional ones in the added part of the broken column. More precisely, it is not difficult to see that (at this point the special form of μ enters)

L_{f}(q(A); d) = L(q(A); d) ∪ [[d]].

Furthermore, the broken column to the right of the path is in perfect correspondence with the broken column of p(μ) (with the “fake” part included; compare Figure 10), which is seen by rotation by 180^{∘}. Let us denote the leg lengths (measured “to the top,” i.e., with respect to the path which runs from bottom-left to top-right) in the broken column to the right by L_{f}(p(μ); d). Obviously we have

L_{f}(p(μ); d) = L(p(μ); d) ∪ [[ℓ(μ) + 1 − min{k : μ_{k} ≤ d}]].

. . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}. . . . .  ^{p(μ)}  ∘^{M}^{q(R(a))}  . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .^{q(A)}^{A_{2}}^{SQ(a, μ)} ∘^{M′}_{Figure 10}

. . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}. . . . . . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} ∘_{Figure 11}

The point of the construction in Figure 11 is that the Lemma from Section 3 tells us that L_{f}(q(A); d) = L_{f}(p(μ); d). Now, if we combine everything then we are done: We have

L(p(μ); d) ∪ L(q(R(a)); d)
= (L_{f}(p(μ); d)\[[ℓ(μ) + 1 − min{k : μ_{k} ≤ d}]]) ∪ ([[a]]\[[d]])
= (L_{f}(p(μ); d) ∪ [[a]])\([[ℓ(μ) + 1 − min{k : μ_{k} ≤ d}]] ∪ [[d]])

and

L(q(A); d) ∪ L(A_{2}; d) = (L_{f}(q(A); d)\[[d]]) ∪ ([[a]]\[[ℓ(μ) + 1 − min{k : μ_{k} ≤ d}]])
= (L_{f}(q(A); d) ∪ [[a]])\([[d]] ∪ [[ℓ(μ) + 1 − min{k : μ_{k} ≤ d}]]).

Clearly, in view of L_{f}(q(A); d) = L_{f}(p(μ); d) these two expressions agree, as desired. Hence, the assertion of Theorem 3 is established.

Remark. Again, the above argument was not completely bijective. Statements analogous to those in the Remark at the end of Section 4 apply also here.

References

1. C. Bessenrodt, On hooks of Young diagrams, Ann. Combin. 2 (1998), 103–110.

2. S. Janson, Hook lengths in a skew Young diagram, Electron. J. Combin. 4 (1997), paper #R24.

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

4. A. Postnikov and A. Regev, Hook and content number identities, preprint.

5. A. Regev, Generalized hook and content numbers identities, Europ. J. Combin. (to appear).

6. A. Regev, Generalized hook and content numbers identities — the projective case, Europ. J. Combin. (to appear).

7. A. Regev and A. Vershik, Asymptotics of Young diagrams and hook numbers, Electron. J. Combin. 4 (1997), paper #R22.

8. A. Regev and D. Zeilberger, Proof of a conjecture on multisets of hook numbers, Ann. Combin. 1 (1997), 391–394.

9. R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, 1986, reprinted by Cambridge University Press, Cambridge, 1998.

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