Séminaire Lotharingien de Combinatoire 46 (2001), Article B46f

HOOK LENGTH FORMULA AND

GEOMETRIC COMBINATORICS

Igor Pak

Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139 USA E-mail: pak@math.mit.edu

Abstract. We present here a transparent proof of the hook length formula. The formula is reduced to an equality between the number of integer point in certain polytopes. The latter is established by an explicit continuous volume-preserving piecewise linear map.

Introduction

About one hundred years ago, Alfred Young realized that the dimension of the irreducible representation of the symmetric group is given by the number of what we now call standard Young tableaux. About fifty years ago, Frame, Robinson and Thrall discovered a remarkable and somewhat mysterious hook length formula for this dimension. Ever since, a quest for a simple combinatorial proof has been under way. Although several beautiful proofs have been found, it is our personal view that the real meaning of the formula is yet to be understood. Thus the current paper as another meager attempt.

Roughly, our proof consists of three steps, which can be outlined as follows. In the first step we reduce the hook length formula to Stanley’s hook content formula for the number of reverse plane partitions. Since we do not need the full power of Stanley’s theorem, we use a simple geometric argument to prove the claim. Then we extend the result, by switching from the cone of reverse plane partitions to certain finite polytopes. Finally, we prove that the integer volumes of these polytopes are identical by using an explicit continuous volume-preserving map between them. We enclose three “bonus” sections which describe special properties of the map defined above. We conclude with brief remarks and pointers to the literature, which are completely absent in the main body of the paper.

The goal of this paper is not to invent a completely new approach or a new bijection, but rather to create a simple and transparent proof with virtually no technical details. In the process, we utilize some well known ideas and simplify the existing bijections. After certain reservations about the merit of such an exercise, we decided that it has both scientific and educational value. We defer the final judgement to the reader.

Typeset by AMS-TEX

Key words and phrases. Hook length formula, RSK, convex polytope, Ehrhart polynomial.

A few words about notation. Throughout the paper we use [λ] to denote the set of squares of a Young diagram λ (see below). We write [n] = {1, 2, …, n}, ℤ_{+} = {0, 1, 2, … }. Furthermore, we write f ∼ g for functions f, g : ℝ_{+} → ℝ_{+}, when f(z)/g(z) → 1 as z → ∞. Also, for any array d = (d_{1}, …, d_{k}), we write |d| = d_{1} + ⋯ + d_{k}. We will abbreviate the hook length formula as HLF, the hook content formula as HCF, etc. A small warning: the proof of Lemma 1 should not be skipped even if the result is well known to the reader. The proof contains definitions and notation we use thereafter.

1. The hook length formula

Let λ = (λ_{1}, λ_{2}, …, λ_{ℓ}) be a partition of n (denotes λ ⊢ n), if λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{ℓ}, |λ| = ∑_{i} λ_{i} = n. From now on, let ℓ denotes the number of parts; let m = λ_{1} denote the length of the largest part. Define the conjugate partition λ′ = (λ′_{1}, …, λ′_{m}) by λ′_{j} = |{i : λ_{i} ≥ j}|.

A Young diagram [λ] corresponding to λ, is a collection of squares (i, j) ∈ ℤ^{2}, such that 1 ≤ j ≤ λ_{i}. Define the hook length h(r) = λ_{i} + λ′_{j} − i − j + 1, where r = (i, j) ∈ [λ].

We say that (i_{1}, j_{1}) ≺ (i_{2}, j_{2}) if i_{1} ≤ i_{2}, j_{1} ≤ j_{2}. A standard Young tableau A of shape λ is a bijective map f : [λ] → [n] = {1, …, n}, such that f(i_{1}, j_{1}) < f(i_{2}, j_{2}) for all (i_{1}, j_{1}) ≺ (i_{2}, j_{2}). We denote the set of standard Young tableaux of shape λ by SYT(λ).

Figure 1. Young diagram [λ], where λ = (6, 6, 5, 3, 2). A hook at r = (2, 3), h(r) = 6. A standard Young tableau of shape (3, 2, 2).

Theorem 1. (Hook Length Formula) :

|SYT(λ)| = \frac{n!}{∏_{r∈[λ]} h(r)} .

2. Reverse plane partitions

A reverse plane partition A of shape λ is a function f : [λ] → ℤ_{+} = {0, 1, 2, … }, such that f(i_{1}, j_{1}) ≤ f(i_{2}, j_{2}) for all (i_{1}, j_{1}) ≺ (i_{2}, j_{2}). We denote the set of reverse

Figure 2. A reverse plane partition A of shape λ = (4, 3, 2); |A| = 37.

plane partitions of shape λ by RPP(λ). Let |A| = ∑_{r∈[λ]} f(r) denote the size of A. One can think of A as of a two-dimensional array (x_{i,j}) of shape [λ].

Theorem 2. (Hook Content Formula) :

∑_{A∈RPP(λ)} t^{|A|} = ∏_{r∈[λ]} \frac{1}{1 − t^{h(r)}} .

Lemma 1. The Hook Content Formula implies the Hook Length Formula.

Proof. Let V ≃ ℝ^{n} be the vector space of all real functions f : [λ] → ℝ, and let f(i, j) = x_{i,j}. Consider the cone C(λ) ⊂ V of all real functions f : [λ] → ℝ_{+}, such that f(i_{1}, j_{1}) ≤ f(i_{1}, j_{2}) for all (i_{1}, j_{1}) ≺ (i_{2}, j_{2}). In other words, C(λ) is defined by the inequalities x_{i,j} ≥ 0, x_{i_{1},j_{1}} ≤ x_{i_{2},j_{2}}, for all i_{1} ≤ i_{2}, j_{1} ≤ j_{2}. Let φ : C(λ) → ℝ_{+} be a linear function φ = ∑_{(i,j)∈[λ]} x_{i,j}.

Similarly, let W ≃ ℝ^{n} be the set of functions g : [λ] → ℝ, g(i, j) = y_{i,j}, and let D(λ) = ℝ_{+}^{n} be the cone of nonnegative functions: y_{i,j} ≥ 0. Denote by ψ : D(λ) → ℝ_{+} the linear function ψ = ∑_{r∈[λ]} h(r) y_{r}.

Now we can restate the HCF as follows:

e(C(λ) ∩ {φ = N}) = e(D(λ) ∩ {ψ = N}), for all N ∈ ℤ_{+},

where e(P) denotes the number of integer points in the polytope P. Let us rewrite this as follows:

e(C(λ) ∩ {φ ≤ N}) = e(D(λ) ∩ {ψ ≤ N}), for all N ∈ ℤ_{+}.

This implies that

(⋆) vol(C(λ) ∩ {φ ≤ z}) ∼ vol(D(λ) ∩ {ψ ≤ z}), as z → ∞.

Now, for every bijection σ : [λ] → [n] we can define the cone C(σ) ⊂ V to be the cone of functions f : [λ] → ℝ_{+} such that f(σ^{−1}(i)) ≤ f(σ^{−1}(j)) for all i < j. Clearly,

C(λ) = ∪_{σ∈SYT(λ)} C(σ), ∪_{σ} C(σ) = ℝ_{+}^{n} ⊂ V,
vol(C(σ) ∩ {φ ≤ z}) = vol(C(σ′) ∩ {φ ≤ z}),
vol(C(σ) ∩ C(σ′) ∩ {φ ≤ z}) = 0, for every σ ≠ σ′.

Therefore

vol(C(λ) ∩ {φ ≤ z}) = ∑_{σ∈SYT(λ)} vol(C(σ) ∩ {φ ≤ z})

= \frac{|SYT(λ)|}{n!} vol(D(λ) ∩ \{φ ≤ z\}) = \frac{|SYT(λ)|}{n!} z^{n} vol(D(λ) ∩ \{φ ≤ 1\}).

On the other hand, the change of coordinates y′_{i,j} = \frac{h(i,j)}{z} y_{i,j} gives:

vol(D(λ) ∩ \{ψ ≤ z\}) = ( ∏_{r∈[λ]} \frac{z}{h(r)}) vol(D(λ) ∩ \{φ ≤ 1\}).

We conclude

vol(C(λ) ∩ \{φ ≤ z\}) = \frac{n!}{|SYT(λ)| ∏_{r∈[λ]} h(r)} vol(D(λ) ∩ \{ψ ≤ z\}).

Substituting this into (⋆) and letting z → ∞, implies the result. □

3. Two polytopes

Denote by r_{c} = (i_{c}, j_{c}) the maximal element in [λ] along diagonal i − j = c :

r_{c} = max_{≺} {(i, j) ∈ [λ] : i − j = c}.

Now, let α_{c}, 1 − m ≤ c ≤ ℓ − 1, be the diagonal sums :

α_{c} = ∑_{(i,j)∈[λ]: i−j=c} x_{i,j}.

We think of α_{c} as of linear functions on V. Clearly, ∑_{c} α_{c} = φ.

Similarly, consider rectangular sums :

β_{c} = ∑_{r=(i,j)≺r_{c}} y_{i,j}.

Again, we think of β_{c} as of linear functions on W. Later we prove that ∑_{c} β_{c} = ψ.

Figure 3. The area of the diagonal sum α_{−2} and the rectangular sum β_{−2}. The corner square r_{2} = (4, 2).

Now, for every integer array d = (d_{1−m}, …, d_{ℓ−1}), consider the two polytopes:

\begin{aligned}P_{λ}(d) & = C(λ) ∩ \{α_{1−m} = d_{1−m}, …, α_{0} = d_{0}, …, α_{ℓ−1} = d_{ℓ−1}\} ⊂ V, \\ Q_{λ}(d) & = D(λ) ∩ \{β_{1−m} = d_{1−m}, …, β_{0} = d_{0}, …, β_{ℓ−1} = d_{ℓ−1}\} ⊂ W. \end{aligned}

Theorem 3. (Two Polytopes Theorem) For any integer array d = (d_{1−m}, …, d_{ℓ−1}), we have e(P_{λ}(d)) = e(Q_{λ}(d)).

Lemma 2. The Two Polytopes Theorem implies the Hook Content Formula.

Proof. Consider the linear function ϱ = ∑_{c=1−m}^{ℓ−1} β_{c}. Let us first prove that ϱ = ψ. Indeed,

ϱ = ∑_{c=1−m}^{ℓ−1} β_{c} = ∑_{c=1−m}^{ℓ−1} ∑_{(i,j)≺r_{c}} y_{i,j} = ∑_{(i,j)∈[λ]} ∑_{c=i−λ_{i}}^{j−λ_{j}} y_{i,j} = ∑_{(i,j)∈[λ]} h(i, j) y_{i,j} = ψ.

Therefore, Theorem 3 implies that

e(C(λ) ∩ {φ = z}) = ∑_{d: φ=z} e(P_{λ}(d)) = ∑_{d: ϱ=z} e(Q_{λ}(d))

= ∑_{d: ψ=z} e(Q_{λ}(d)) = e(D(λ) ∩ {ψ = z}).

From the proof of Lemma 1, this implies HCF. □

Proof of the HLF. From above, Theorem 3 and Lemma 2 imply the HCF. Now the HLF follows from the HCF by Lemma 1. □

Corollary 1. For all λ, d, the polytopes P_{λ}(d) and Q_{λ}(d) have the same Ehrhart polynomial.

Proof. For any polytope P, let N ·P = {N x : x ∈ P }. The Ehrhart polynomial is defined as E(P, t) = e(t · P). We use N · a to denote (Na_{1}, Na_{2}, …).

By definition of polytopes P_{λ} and Q_{λ}, we have:

E(P_{λ}(d), N) = e(N · P_{λ}(d)) = e(P_{λ}(N · d))
= e(Q_{λ}(N · d)) = e(N · Q_{λ}(d)) = E(Q_{λ}(d), N),

for every N ≥ 1. This implies the result. □

4. Proof of the Two Polytopes Theorem

In this section we prove TPT by induction on n = |λ|. When n = 1, we have λ = (1), P_{λ} = Q_{λ}, and the result is trivial. We define an identity map ξ_{λ} : P_{λ} → Q_{λ} in this case.

Now, let r_{c} be the maximal element on diagonal i − j = c in λ. We say that r_{c} = (i_{c}, j_{c}) is a corner in [λ], if r_{c−1}, r_{c+1} ≺ r_{c}. We have r_{c−1} = (i_{c} − 1, j_{c}), r_{c+1} = (i_{c}, j_{c}−1) in this case. Observe that if r_{c} is a corner in [λ], then [μ] = [λ]−r_{c} is a Young diagram of a partition μ = (λ_{1}, …, λ_{i_{c}−1}, λ_{i_{c}} −1, λ_{i_{c}+1}, …) ⊢ n−1. The step of induction we present below is a reduction of TPT from [λ] to [μ] = [λ]−r_{c}.

Let d = (d_{1−m}, …, d_{ℓ−1}) be as above. We shall construct an explicit map ξ_{λ} : P_{λ}(d) → Q_{λ}(d), which gives a bijection between integer points in P_{λ}(d) and in Q_{λ}(d). Indeed, let A = (x_{i,j}) ∈ P_{λ}(d). Define

x′_{i,j} = \{ \begin{matrix}x_{i,j}, if i − j ≠ c \\ x_{i,j} − max\{x_{i−1,j} , x_{i,j−1}\}, if (i, j) = (i_{c}, j_{c}) \\ max\{x_{i−1,j} , x_{i,j−1}\} + min\{x_{i+1,j} , x_{i,j+1}\} − x_{i,j}, \\ if i − j = c, (i, j) ≠ (i_{c}, j_{c}). \end{matrix}

Here we use the convention x_{i,0} = x_{0,j} = 0. Let A′ = (x′_{i,j}), ζ = ζ_{λ,c} : (x_{i,j}) → (x′_{i,j}).

Notice that by construction, ζ is a continuous piecewise linear map, with the inverse ζ^{−1} : (x′_{i,j}) → (x_{i,j}) given by

x_{i,j} = \{ \begin{matrix}x′_{i,j}, if i − j ≠ c \\ x′_{i,j} + max\{x′_{i−1,j} , x′_{i,j−1}\}, if (i, j) = (i_{c}, j_{c}) \\ max\{x′_{i−1,j} , x′_{i,j−1}\} + min\{x′_{i+1,j} , x′_{i,j+1}\} − x′_{i,j}, \\ if i − j = c, (i, j) ≠ (i_{c}, j_{c}). \end{matrix}

Now let ξ_{λ} : A → B, where B = (y_{i,j}) ∈ Q_{λ}(d) is defined as follows:

(y_{i,j})_{{(i,j)∈[μ]}} = ξ_{μ}(x′_{i,j})_{{(i,j)∈[μ]}}, and y_{i_{c},j_{c}} = x′_{i_{c},j_{c}}.

One can think of ξ_{λ} as of a composition ξ_{λ} = ξ_{μ} ∘ ζ : A →^{ζ} A′ →^{ξ_{μ}} B.

Note that one can define ξ_{λ} as a map ξ_{λ} : V → W, with an obvious inverse ξ_{λ}^{−1} = ζ^{−1} ∘ ξ_{μ}^{−1}. Now the inductive assumption implies that ξ_{λ} is one-to-one.

We need to show that ξ_{λ} : P_{λ}(d) → Q_{λ}(d) is a bijection. First, observe that ξ_{λ}(A) ∈ D(λ) ⊂ W for all A ∈ C(λ). Similarly, ξ^{−1}(B) ∈ C(λ) ⊂ V for all B ∈ D(λ). We use here the inductive assumption and construction of ζ. Now it remains to show that α_{r}(A) = β_{r}(B) for all B = ξ_{λ}(A), 1 − m ≤ r ≤ ℓ − 1. Note that we will prove this for all A ∈ V, B ∈ W, B = ξ_{λ}(A).

Clearly, α_{r}(A) = α_{r}(A′) = β_{r}(B) for all r ≠ c. Indeed, x_{i,j} = x′_{i,j} by construction, and x′_{i,j} = y_{i,j} by induction, for all i − j = r ≠ c. Checking that α_{c}(A) = β_{c}(B) is a simple but delicate computation. First, observe that

α_{c}(A′ − r_{c}) − x′_{i_{c},j_{c}} = ∑_{i−j=c,i<i_{c}} max{x_{i−1,j} , x_{i,j−1}} + min{x_{i+1,j} , x_{i,j+1}} − x_{i,j}
+ max{x_{i_{c}−1,j_{c}} , x_{i_{c},j_{c}−1}} − x_{i_{c},j_{c}}

= ∑_{i−j=c−1} x_{i,j} + ∑_{i−j=c+1} x_{i,j} − ∑_{i−j=c} x_{i,j}

= α_{c−1}(A) + α_{c+1}(A) − α_{c}(A), where the first equality follows by definition of ζ, the second equality is obtained by collection of terms, and (A′ − r_{c}) stands for restriction of A to [μ]. Therefore we obtain:

\begin{aligned}β_{c}(B) & = β_{c−1}(B) + β_{c+1}(B) + y_{i_{c},j_{c}} − β_{c}(B − r_{c}) \\ & = α_{c−1}(A) + α_{c+1}(A) − (α_{c}(A′ − r_{c}) − x′_{i_{c},j_{c}}) = α_{c}(A). \end{aligned}

This completes the proof. □

5. A General Bijection

The inductive proof of TPT given in Section 4 can be extended to a piecewise linear map ξ_{λ} : P_{λ}(d) → Q_{λ}(d), which preserves the volume and maps integer points to integer points. However, it is unclear from the construction that this bijection is independent of the choice of corners r_{c} in the proof.

Figure 4. A bijection ξ_{(3,3,3)} = ζ_{0} ∘ ζ_{1} ∘ ζ_{−1} ∘ ⋯ ∘ ζ_{0}.

Theorem 4. The bijection ξ_{λ} defined as above does not depend on the choice of corners r_{c} in the construction.

Proof. By induction, we can write ξ_{λ} as follows:

(∗) ξ_{λ} = ζ_{λ,c} ∘ ζ_{(λ−r_{c}),c′} ∘ ζ_{(λ−r_{c}−r_{c′}),c′′} ∘ …

From now on we drop λ in ζ_{λ,c} if it is clear what partition is meant.

Clearly, ζ_{c} commutes with ζ_{c′}, for all |c − c′| ≥ 2. In other words, if r = r_{c} and r′ = r_{c′} are corners of [λ]; [μ] = [λ] − r, [μ′] = [λ] − r′, then

ζ_{μ,c′} ∘ ζ_{λ,c} = ζ_{μ′,c} ∘ ζ_{λ,c′}.

Thus it suffices to prove that every two products as in (∗) can be obtain from each other by use of these commutations.

Note that the sequence of squares r_{c}, r_{c′}, r_{c′′}, …, defines a standard Young tableau A of shape λ. Consider a graph Γ(λ) with vertices being standard Young tableaux of shape λ (incidentally, there are n!/ ∏_{r} h(r) of them by the HLF), and edges (A, A′), whenever A′ is obtained from A by exchange of values i and i + 1.

Lemma 3. The graph Γ(λ) is connected.

Note that the edges of Γ(λ) correspond to the commutations as above. Indeed, by definition of a Young tableau, the values i and i + 1 cannot be in the same or adjacent diagonals. Thus the Lemma implies that any two products as in (∗) can be obtained by a sequence of commutations and thus give the same result. □

Figure 5. Oriented graph Γ(3, 2).

Proof of Lemma 3. Let A_{0} be the standard Young tableau of shape λ given by f(1, 1) = 1, f(1, 2) = 2, …, f(1, λ_{1}) = λ_{1}, f(2, 1) = λ_{1} +1, …, f(2, λ_{2}) = λ_{1} +λ_{2}, f(3, 1) = λ_{1} +λ_{2} +1, … Let us orient all edges of Γ(λ), so that A → A′ if A and A′ exchange the values of i and i + 1, and i occurs in a row of A′ smaller than that of A. Observe that A_{0} is the only vertex with no outgoing edges in Γ(λ). Therefore, every A is connected to A_{0} in Γ(λ), which proves the result. □

6. The Two Polytopes Theorem and RSK

In this section we deduce from Theorem 3 the numerical result of the Robinson-Schensted-Knuth correspondence.

Let λ = (n^{n}) = (n, n, …, n), n times. In this case [λ] = [n] × [n], ℓ(λ) = m = n. Let d = (d_{1−n}, …, d_{0}, …, d_{n−1}) be as above. Suppose

(⋄) a_{i} = d_{i−n} − d_{i−n−1}, b_{i} = d_{n−i} − d_{n−i+1}, for all 1 ≤ i ≤ n.

Then the integer points in Q_{λ}(d) correspond to contingency tables (nonnegative integer n × n matrices with given row and column sums):

∑_{j=1}^{n} y_{i,j} = a_{i}, ∑_{i=1}^{n} y_{i,j} = b_{j}, y_{i,j} ≥ 0, for all 1 ≤ i, j ≤ n.

We say that f : [λ] → ℤ_{+} is a Young tableau of shape λ, if f(i, j) ≤ f(i, j + 1) and f(i, j) < f(i+1, j), whenever both sides are defined. We say that A has weight a = (a_{1}, …, a_{n}), if |{(i, j) ∈ [λ] : f(i, j) = k}| = a_{k}, for all 1 ≤ k ≤ n.

Theorem 5. (RSK) Let a = (a_{1}, …, a_{n}) and b = (b_{1}, …, b_{n}) be two nonnegative integer arrays such that |a| = |b|. Then the number of contingency tables with row sums a_{i}, and column sums b_{j}, is equal to the number of pairs of Young tableaux of the same shape λ ⊢ n, and weight a and b respectively.

Proof. Let d_{−i} = a_{1} + ⋯ + a_{n−i}, d_{i} = b_{1} + ⋯ + b_{n−i}, for 0 ≤ i ≤ n − 1, so that d_{0} = |a| = |b|. Then a_{i}, b_{j} satisfy (⋄) and the number of contingency tables is equal to e(Q_{λ}(d)).

Now, let A, B be Young tableaux of shape μ = (μ_{1}, …, μ_{n}) ⊢ n with weights a and b, given by functions f_{A} and f_{B}, respectively. Let X = (x_{i,j}) be the reverse plane partition of shape λ, defined by

x_{i,j} = \{ \begin{matrix}|\{k : f_{A}(n − j + 1, k) ≤ i\}|, if i ≤ j; \\ |\{k : f_{B}(n − i + 1, k) ≤ j\}|, if i ≥ j . \end{matrix}

Figure 6. A reverse plane partition X of shape (3, 3, 3) and a corresponding pair of Young tableaux of shape (7, 4, 1) with weights a = (4, 5, 3) and b = (2, 5, 5).

Note that

x_{i,i} = |{k : f_{A}(n − i + 1, k) ≤ i}| = |{k : f_{B}(n − i + 1, k) ≤ i}| = μ_{n−i+1}.

Also, (x_{i,j}) ∈ C(λ), since all the inequalities follow from the definition of Young tableaux. Finally, by definition of the weight, we have

α_{−i}(X) = a_{1}+ … +a_{n−i} = d_{−i}, and β_{i}(X) = b_{1}+ … +b_{n−i} = d_{i}, for 0 ≤ i ≤ n−1.

Therefore, pairs of Young tableaux of the same shape μ ⊢ n and weight a and b, are in bijection with reverse plane partitions X = (x_{i,j}) ∈ P_{λ}(d) of shape λ. This completes the proof. □

Denote by θ the correspondence between reverse plane partitions X and pairs of Young tableaux as in the proof above. Let η = θ · ξ be the bijection between contingency tables Y = (y_{i,j}) and pairs of Young tableaux of the same shape (as in Theorem 5.) By Y^{T} denote the transpose matrix Y^{T} = (y_{i,j}^{T}), where y_{i,j}^{T} = y_{j,i}, 1 ≤ i, j ≤ n.

Corollary 2. If η(Y) = (A, B), then η(Y^{T}) = (B, A).

Proof. By construction, if θ(X) = (A, B), then θ(Y^{T}) = (B, A). It remains to check that ξ(Y^{T}) = (ξ(Y))^{T}. But this follows immediately from Theorem 4 since the transposition simply changes the order of the corners in the definition of ξ_{λ}. □

7. Monotone paths

We say that the squares (i ± 1, j) and (i, j ± 1) are adjacent to (i, j) in ℤ^{2}. A monotone path γ in [λ], denoted by γ ⇝ [λ], is a sequence of adjacent squares r ≺ r′ ≺ r′′ ≺ …, where r, r′, ⋯ ∈ [λ]. Let g : [λ] → ℝ_{+} be any nonnegative function on [λ], which defines a tableau B = (y_{i,j}), where y_{i,j} = g(i, j) for all (i, j) ∈ [λ]. Define the height of a path γ to be the sum ω_{B}(γ) = g(r) + g(r′) + g(r′′) + . . ..

Theorem 6. Let ξ_{λ} : P_{λ}(d) → Q_{λ}(d) be the map defined as above. Fix a square r_{c} = (i_{c}, j_{c}), where 1 − m ≤ c ≤ ℓ − 1; [ν_{c}] = {(i, j) : i ≤ i_{c}, j ≤ j_{c}}. Then for every A = (x_{i,j}), B = (y_{i,j}), B = ξ_{λ}(A), we have

x_{i_{c},j_{c}} = max_{γ⇝[ν_{c}]} ω_{B}(γ).

Figure 7. An example of bijection ξ_{(3,3,3)} : A → B (cf. Figure 4.) The value of A at r_{1} = (3, 2) is equal to the sum along the monotone path from (1, 1) to (3, 2) with maximum height: 4 = 1 + 0 + 3 + 0.

Proof. Use induction. When n = 1 the result is trivial. Suppose it holds for [μ] = [λ] − r_{c}, where r_{c} is the corner of [λ]. By definition of ζ_{λ,c} , we have:

max_{γ⇝[ν_{c}]} ω_{B}(γ) = max{ max_{γ⇝[ν_{c−1}]} ω_{B}(γ) , max_{γ⇝[ν_{c+1}]} ω_{B}(γ)} + y_{i_{c},j_{c}}

= max{x_{i_{c}−1,j_{c}} , x_{i_{c},j_{c}−1}} + (x_{i_{c},j_{c}} − max{x_{i_{c}−1,j_{c}} , x_{i_{c},j_{c}−1}})

= x_{i_{c},j_{c}}

Since the off-diagonal values of ζ_{λ,c} remain unchanged, this implies the result. □

8. Historical remarks and quick guide through the literature

As we mentioned in the introduction, the hook length formula first appeared in [FRT], after it was independently discovered by the authors of that paper (see [Sa]). Various combinatorial proofs were later obtained in [FZ,GNW,Kr,NPS]. We will not review these proofs here, but rather refer the reader to the textbooks [JK,K2,M,Sa,S3] for these and other proofs, and further references.

The hook content formula was discovered by Stanley in [S2]. Note that what we call HCF is really a special case of a more general result in [S2], when the size of the entries f(i, j) in a reverse plane partition is bounded. Lemma 1 is a very special case, for a poset ([λ], ≺), of another general result of Stanley [S1]. Our presentation is elementary and probably well known, although we could not find a precise reference.

The idea to prove HLF via HCF goes back to [S1], and was utilized by Hillman and Grassl in the pioneering work [HG]. The similarity between the Hillman-Grassl bijection and the Robinson-Schensted-Knuth correspondence was observed by Gansner in [G1,G2], who proved versions of Theorem 3 and Lemma 2, although by a different technique.

The proof of TPT that we present here was inspired by [PP]. The continuous version first appeared there as well. Let us emphasize here that d can be any nonnegative real array. The construction of a map ζ̃_{c}, remarkably similar to ζ_{c}, but for diagonals with no corners, was discovered independently in [BK]. There, the authors also pursued “continuous combinatorics”, and obtained the Schützenberger involution as a certain product ∏_{c} ζ̃_{c}. In a different direction, we believe that our proof of TPT is equivalent to a special case of the general approach in [F]. Unfortunately, the translation is quite cumbersome and requires some extra work.

Let us note that Corollary 1 in a special case gives an interpretation of the Ehrhart polynomial of the Birkhoff polytope [P1], long studied by combinatorialists (see e.g. [S3]). Lemma 3 is well known. Exactly this version appeared in [P2]. An advanced generalization, in the language of Bruhat orders, is given in [BW].

Theorem 5 is due to Knuth [K1], who proved it by a bijection, now known as Robinson-Schensted-Knuth correspondence (see [K2,R,Sa,S3]). It is known [PP] that our bijection ξ_{λ} in this special case coincides with RSK (after translation as in the proof). The proof requires the understanding of the classical formulation of the RSK correspondence and goes beyond this paper.

Corollary 2 is a famous symmetry property of RSK [K1], long studied in this context. The result is quite nontrivial when dealing with the original correspondence, and rather immediate from our approach^{1}.

The ‘monotone path’ property of ξ_{λ}, given by Theorem 6, is well known for the RSK correspondence (see [Sa]). The concept of monotone paths generalizes longest increasing subsequences, which were the motivation in [Sc]. One can also extend Greene’s Theorem [Gr] in this case.

To conclude, let us speculate about possible extensions of the HLF. Versions of the map ζ_{λ} exist for all differential posets and even dual graded graphs [F,S3]. The proof of Lemma 1 generalizes to all posets with no difficulty. It is Lemma 2 that is specific for the Young lattice, and is a key to possible generalizations.

1We believe that our construction of ξ_{λ} has a certain advantage when compared to the original construction of the RSK correspondence (we have λ = (n^{n}) in this case.) It seems that with a small exception of the dual RSK (which does not seem to have a “continuous” generalization), all properties of the RSK correspondence are easier to prove in our setting.

Acknowledgements

Over the years the author benefited from helpful conversations with a number of people. It is my pleasure to thank here Ron Adin, Arkady Berenstein, Jean Bétréma, Persi Diaconis, Joseph Donin, Adriano Garsia, Ira Gessel, Alexandre Kirillov, Christian Krattenthaler, Ezra Miller, Jean-Christophe Novelli, Alex Postnikov, Yuval Roichman, Bruce Sagan, Richard Stanley, Sasha Stoyanovskii, Xavier Viennot and Andrei Zelevinsky. Communication with Herb Wilf was educational and entertaining. We also thank the referees for the thorough reading of the paper.

The paper was written when the author was a Fellow at MSRI in Berkeley, CA.

References

[BK] A. Berenstein, A. Kirillov, Groups generated by involutions, Gelfand-Tsetlin patterns, and combinatorics of Young tableaux, St. Petersburg Math. J. 7 (1996), 77–127.

[BW] A. Björner, M. Wachs, Generalized quotients in Coxeter groups, Trans. Amer. Math. Soc. 308 (1988), 1–37.

[F] S. Fomin, Duality of graded graphs; Schensted algorithms for dual graded graphs, J. Alg. Comb. 3, 4 (1994–5), 357–404; 5–45.

[FRT] J. S. Frame, G. de B. Robinson, R. M. Thrall, The hook graphs of the symmetric group, Canad. J. Math. 6 (1954), 316–325.

[FZ] D. S. Franzblau, D. Zeilberger, A bijective proof of the hook-length formula, J. Algorithms 3 (1982), 317–343.

[G1] E. Gansner, Matrix correspondences of plane partition, Pacific J. Math. 92 (1981), 295– 315.

[G2] E. Gansner, The Hillman-Grassl correspondence and the enumeration of reverse plane partitions, J. Combin. Theory, Ser. A 30 (1981), 71–89.

[Gr] C. Greene, An extension of Schensted’s theorem, Advances in Math. 14 (1974), 254–265.

[GNW] C. Greene, A. Nijenhuis, H. S. Wilf, A probabilistic proof of a formula for the number of Young tableaux of a given shape, Adv. in Math. 31 (1979), 104–109.

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

[JK] G. James, A. Kerber, The Representation Theory of the Symmetric Group, Addison-Wesley, Reading, MA, 1981.

[K1] D. Knuth, Permutations, matrices and generalized Young tableaux, Pacific J. Math. 34 (1970), 709–727.

[K2] D. E. Knuth, The Art of Computer Programming (Second Edition), Vol. 3, Sorting and Searching, Addison-Wesley, Reading, Massachusetts, 1998.

[Kr] C. Krattenthaler, Bijective proofs of the hook formulas for the number of the standard Young tableaux, ordinary and shifted, Electr. J. Comb. 2 (1995), #R13.

[M] I. G. Macdonald, Symmetric Functions and Hall Polynomials, second edition, Oxford University Press, London, 1995.

[NPS] J-C Novelli, I. Pak, A. V. Stoyanovskii, A direct combinatorial proof of the hook-length formula, Discrete Math. and Theor. Comp. Sci. 1 (1997), 53–67.

[P1] I. Pak, Four questions on Birkhoff polytope, Annals of Combinatorics 4 (2000), 83–90.

[P2] I. Pak, Ribbon tile invariants, Trans. Amer. Math. Soc. 352 (2000), 5525–5561.

[PP] I. Pak, A. Postnikov, Oscillating tableaux and generalized RSK correspondence, Proc. of Eighth FPSAC Conference, UMN, Minneapolis, 1996.

[R] G. de B. Robinson, Representation Theory of the Symmetric Group, Edinburgh University Press, 1961.

[Sa] B. Sagan, The symmetric group: Representations, Combinatorial Algorithms and Symmetric Functions (Second Edition), Springer, New York, 2001.

[Sc] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179–191.

[S1] R. P. Stanley, Ordered structures and partitions, Memoirs of the AMS 119, AMS, Providence, R.I., 1972.

[S2] R. P. Stanley, Theory and application of plane partitions, I, II, Studies in Appl. Math. 50 (1971), 167–188, 259–279.

[S3] R. P. Stanley, Enumerative Combinatorics, Vol. 1, 2, Cambridge University Press, Cambridge, UK, 1999.