Hook lengths in a skew Young diagram

Svante Janson

Department of Mathematics, Uppsala University PO Box 480, S-751 06 Uppsala, Sweden

                             svante.janson@math.uu.se

Submitted: October 15, 1997; Accepted: October 20, 1997

Abstract

Regev and Vershik (Electronic J. Combinatorics 4 (1997), #R22) have obtained some properties of the set of hook lengths for certain skew Young diagrams, using asymptotic calculations of character degrees. They also conjectured a stronger form of one of their results. We give a simple inductive proof of this conjecture. Very recently, Regev and Zeilberger (Annals of Combinatorics, to appear) have independently proved this conjecture.

1 Introduction

Regev and Vershik [1] have recently obtained some properties of the set of hook lengths for certain skew Young diagrams. They prove the results using asymptotic calculations of the degrees of certain sequences of characters of the symmetric group, and note that they do not know a direct “finite” proof of their results.

The purpose of the present note is to present such a proof for one of their results, viz. their Theorem 1.2.2. Moreover, Regev and Vershik’s Theorem 1.2.2 states that two different sets of hook lengths have the same product, and the authors conjecture that in fact these two sets are equal. (More precisely, the sets in question should be regarded as multisets, i.e. the elements may have multiplicities.) We prove this conjecture.

Very recently, Regev and Zeilberger [2] have independently proved this conjecture.

2 Notation

If n_{1} ≥ n_{2} ≥ ⋯ ≥ n_{m} ≥ 0 are integers, with m ≥ 1, let D = D(n_{1}, …, n_{m}) be the Young diagram with rows of lengths n_{1}, …, n_{m}. Following (and slightly extending) Regev and Vershik [1], we introduce the following definitions, see the examples in Figures 1 and 2.

R = R(m, n) is an m × n rectangle, i.e. a Young diagram with m rows of equal length n.

We assume that n ≥ n_{1} and that R and D are positioned such that their top left corners coincide. Then D ⊆ R. (Regev and Vershik consider only the case when R is the smallest rectangle containing D, i.e. when n = n_{1} and n_{m} ≥ 1. We find it convenient to treat a slightly more general situation.)

D^{∗} is obtained by rotating D a half turn about the center of R; thus D^{∗} ⊆ R and R\D^{∗} is a Young diagram with rows of lengths n − n_{m}, n − n_{m−1}, …, n − n_{1}.

SQ = SQ(n_{1}, …, n_{m}; n) is obtained from R \ D^{∗} by adding two copies of D^{∗}, one along the left edge and one along the top edge of R.

We will use a coordinate system with the x-axis directed upwards and the y-axis directed to the left. (Note that thus rows are numbered from the bottom to the top and columns from the right to the left.) We may then describe the skew diagrams as follows.

R(m, n) = {(i, j) : 1 ≤ i ≤ m, 1 ≤ j ≤ n}
D^{∗}(n_{1}, …, n_{m}) = {(i, j) : 1 ≤ i ≤ m, 1 ≤ j ≤ n_{i}}
SQ(n_{1}, …, n_{m}; n) = {(i, j) : 1 ≤ i ≤ m, n_{i} + 1 ≤ j ≤ n_{i} + n}
∪ {(i, j) : m + 1 ≤ i ≤ 2m, 1 ≤ j ≤ n_{i−m}}.

The hook length h_{A}(x) of an element x of a (skew) diagram A is, as usual, the number of elements of A directly below or to the right of x, including x itself. We define H(A) to be the multiset {h_{A}(x) : x ∈ A}.

×
× ×
× × × ×
× × × × 0
× × × × 0 0
× × × × 0 0 0 0

Figure 1: D^{∗}(4, 2, 1) marked with 0; SQ(4, 2, 1; 4) marked with ×

3 4 2 6 5 3 1 6 4 3 1 5 4 2 1 4 3 2 1  6 5 4 3 5 4 3 2 4 3 2 1  6 4 2 1 3 1 1

Figure 2: SQ(4, 2, 1; 4), R(3, 4) and D(4, 2, 1) with hook lengths

3 Result

Theorem. Let n ≥ n_{1} ≥ n_{2} ≥ ⋯ ≥ n_{m} ≥ 0 (m ≥ 1) be integers. We then have the equality of multisets of hook lengths

H(SQ(n_{1}, …, n_{m}; n)) = H(R(m, n)) ∪ H(D(n_{1}, …, n_{m})).  (1)

Proof. We say that (n, n_{1}, …, n_{m}) is good if (1) holds. The result follows by double induction, in m and n_{m}, from the following three claims.

(i) If n ≥ n_{1} ≥ 0, then (n, n_{1}) is good.

(ii) If (n, n_{1}, …, n_{m}) is good, then (n, n_{1}, …, n_{m}, 0) is good.

(iii) If (n, n_{1}, …, n_{m}) is good and n_{m−1} > n_{m}, then (n, n_{1}, …, n_{m−1}, n_{m} + 1) is good.

(i) is trivial: SQ(n_{1}; n) consists of two rows with n and n_{1} elements, positioned such that their hook lengths are 1, …, n and 1, …, n_{1}, respectively, corresponding to the hook lengths of R(1, n) and D(n_{1}).

For (ii), note that SQ′ = SQ(n_{1}, …, n_{m}, 0; n) is obtained from SQ = SQ(n_{1}, …, n_{m}; n) by inserting a new row (m + 1, 1), …, (m + 1, n), moving up all elements (i, j) with i ≥ m; equivalently, SQ′ is obtained from SQ by adding a new element on top of each column 1, …, n. Each of these new top elements has m elements beneath it, and thus their hook lengths are m + 1, …, m + n. Moreover, all elements in SQ keep the same hook length in SQ′; consequently H(SQ′) = H(SQ) ∪ {m + 1, …, m + n}, see Figure 3.

For the right hand side of (1), we observe that adding a new row of length 0 does not change D, while R = R(m, n) is changed to R′ = R(m + 1, n), which equals R with an additional top row having hook lengths m + 1, …, m + n. Thus H(R′) = H(R) ∪ {m + 1, …, m + n}. Consequently, if H(SQ) = H(R) ∪ H(D), then H(SQ′) = H(R′) ∪ H(D) too, which proves (ii).

For (iii) we let SQ′ = SQ(n_{1}, …, n_{m} + 1; n) and D′ = D(n_{1}, …, n_{m} + 1) (this time R = R(m, n) stays the same), and argue similarly. SQ′ differs from SQ in three places: the

4 5 3 7 6 4 2 6 5 3 1 6 4 3 1 5 4 2 1 4 3 2 1  7 6 5 4 6 5 4 3 5 4 3 2 4 3 2 1

Figure 3: Hook lengths in SQ(4, 2, 1, 0; 4) and R(4, 4)

\begin{aligned}& & & & & & /4 & 3 \\ & & & & & & 4/3 & 2 \\ & & & & 6 & 5 & 3/2 & 1 \\ & & /6 & 6/5 & 4/3 & 3/2 & 1/ \\ & & 5 & 4 & 2 & 1 \\ 4 & 3 & 2 & 1 \end{aligned}  \begin{matrix}6 & 4/5 & 2 & 1 \\ 3 & 1/2 \\ 1/2 & /1 \end{matrix}

Figure 4: Hook lengths in SQ(4, 2, 1; 4)/SQ(4, 2, 2; 4) and D(4, 2, 1)/D(4, 2, 2)

element (m, n_{m} + 1) is removed while two new elements (m, n_{m} + n + 1) and (2m, n_{m} + 1) are added. This affects only the hook lengths in row m and in column n_{m} + 1, see Figure 4.

The hook length h_{SQ}(m, j) of an element in row m in SQ is j − n_{m} + m − k if n_{k} < j ≤ n_{k−1} with 1 < k ≤ m, and j − n_{m} + m − 1 if n_{1} < j ≤ n + n_{m}; consequently the hook lengths in row m in SQ are the numbers 1, …, n + m − 1 except the m − 1 numbers n_{k} − n_{m} + m − k, k = 1, …, m − 1.

The hook lengths in row m in SQ′ are similarly (by substituting n_{m} + 1 for n_{m}) the numbers 1, …, n + m − 1 except n_{k} − n_{m} − 1 + m − k, k = 1, …, m − 1. The contributions from this row to the difference between H(SQ) and H(SQ′) is thus equivalent to adding the numbers n_{k} − n_{m} + m − k and removing the numbers n_{k} − n_{m} + m − k − 1, 1 ≤ k ≤ m − 1.

The hook lengths in column n_{m} + 1 in SQ, not counting (m, n_{m} + 1) which is already taken care of, are n_{m} + 2, …, n_{m} + m, while the hook lengths in the same column in SQ′ (which lies entirely above row m) are n_{m} + 1, …, n_{m} + m. The net effect of the changes in this column is thus an addition of the number n_{m} + 1. Consequently, combining the effects in the row and the column,

\begin{aligned}H(SQ′) = H(SQ) ∪ \{n_{m} + 1\} & ∪ \{n_{k} − n_{m} + m − k\}_{k=1}^{m−1} \\ & \ \{n_{k} − n_{m} + m − k − 1\}_{k=1}^{m−1}. \end{aligned}  (2)

For the right hand side of (1), we observe that D′ differs from D in that a new element is added to the last row. The hook lengths in this row in D are 1, …, n_{m}, while in D′ they are 1, …, n_{m} + 1, a net addition of n_{m} + 1.

The element above the new element in the kth row from top has hook length in D n_{k} − n_{m} + m − k − 1, while its hook length in D′ is increased by 1 to n_{k} − n_{m} + m − k.

No other hook lengths are affected, and consequently,

H(D′) = H(D) ∪ {n_{m} + 1} ∪ {n_{k} − n_{m} + m − k}_{k=1}^{m−1} \ {n_{k} − n_{m} + m − k − 1}_{k=1}^{m−1}.

Comparing this with (2), we see that if H(SQ) = H(R) ∪ H(D), then H(SQ′) = H(R) ∪ H(D′) too. This completes the proof of (iii), and thus of the theorem.

References

[1] A. Regev and A. Vershik, Asymptotics of Young diagrams and hook numbers. Electron. J. Combin. 4 (1997), #R22, 12pp.

[2] A. Regev and D. Zeilberger, Proof of a conjecture on multisets of hook numbers. Ann. Combin., to appear.