Bijections for an identity of Young Tableaux

A. Regev and D. Zeilberger

Recall that partition λ = (λ_{1}, …, λ_{k}) is a weakly-decreasing sequence of positive integers, and if n = λ_{1} + ⋯ + λ_{k} we say that λ is a partition of n and write λ ⊢ n and l(λ) = k. For example λ(3, 3, 2, 2) is a partition of 10 and l(λ) = 4. A convenient way to represent a

partition λ is via its Ferrers diagram, that consists of l(λ) left-justified lines of dots, such that the i-th row has λ_{i} dots. If you replace the dots by empty boxes, you would get what is called a Young diagram. Finally recall that a standard Young Tableau (SYT) of shape

λ ⊢ n is any way of placing the integers {1, 2, …, n} into the empty boxes of the Young diagram in such a way that all the rows and all the columns are increasing. For example [[1, 2, 4, 6], [3, 5, 7], [8, 9]] is a SYT of shape (4, 3, 2). Let H(k, ℓ; n) = {λ ⊢ n | λ_{k+1} ≤ ℓ}

denote the partitions of n in the (k, ℓ) hook. For example, H(k, 0; n) are the partitions of λ ⊢ n with ℓ(λ) ≤ k. Let f^{λ} denote the number of standard Young tableaux (SYT) of shape λ. One then observes the following intriguing identity:

∑_{μ∈H(1,1;n+1)}(f^{μ})^{2} = ∑_{λ∈H(2,0;2n)} f^{λ}.

We give this identity a bijective proof by showing that both

∑_{μ∈H(1,1;n+1)}(f^{μ})^{2},  (1)

∑_{λ∈H(2,0;2n)} f^{λ},  (2)

can be mapped bijectively to the set of row-increasing matrices of shape (n, n), and hence, by composing, to each other. We describe these bijections.

The input for both (1) and (2) is a 2 × n matrix of integers a_{1} … a_{n} b_{1} … b_{n}

such that {a_{1}, …, a_{n}} ∪ {b_{1}, … b_{n}} = {1, 2, …, 2n},

a_{1} < a_{2} < ... < a_{n} and b_{1} < b_{2} < ... < b_{n}.

Description of the bijection for (1)

Here the output is: Two standard tableaux of the same (1, 1)-hook shape. Let |{a_{1}, …, a_{n}} ∩ {1, …, n}| = k, so {a_{1}, …, a_{n}} ∩ {1, …, n} = {a_{i_{1}} < ⋯ < a_{i_{k}}}. Form now a SYT in the (1, 1) hook as follows:

Its (first) row is

1, a_{i_{1}} + 1, ⋯, a_{i_{k}} + 1;

its (first) column is made of the remaining integers

{1, … n + 1} \ { 1, a_{i_{1}} + 1, ⋯, a_{i_{k}} + 1} = {a′_{j_{1}}, …, a′_{j_{n−k}}}

in increasing order. This gives the first SYT – of (1, 1)-hook shape (k + 1, 1^{n−k}).

It follows that

|{a_{1}, …, a_{n}} ∩ {n + 1, …, 2n}| = n − k,

so denote

{a_{1}, …, a_{n}} ∩ {n + 1, …, 2n} = {b_{t_{1}} < ⋯ < b_{t_{n−k}}}.

Since n + 1 ≤ b_{t_{1}}, hence 2 ≤ b_{t_{1}} − (n − 1). Form the numbers

1 < b_{t_{1}} − (n − 1) < ⋯ < b_{t_{n−k}} − (n − 1)

and place them, in that (increasing) order, in the column of the second (1,1)-hook shape tableau, and the complement integers

{1, …, n + 1} \ {1, b_{t_{1}} − (n − 1), …, b_{t_{n−k}} − (n − 1)}

in increasing order, in the row (after the corner 1). This gives the second SYT – again of shape (k + 1, 1^{n−k}). This map is clearly a bijection.

Description of the bijection for (2)

Here the output is a SYT whose shape is a ≤ 2-rowed partition of 2n If for all i a_{i} < b_{i}, then it is a SYT, and do nothing (the output is the input).

Otherwise, let i be the smallest index such that a_{i} > b_{i}. Replace the above array by

b_{1} … b_{i−1} b_{i} a_{i} a_{i+1} … a_{n} a_{1} … a_{i−1} b_{i+1} b_{i+2} b_{i+3} … b_{n}

If this is a SYT, then stop. Otherwise continue: Typically we arrive at a two rows array

c_{1}, … c_{s} … c_{r} d_{1} … d_{s}

with s ≤ r, r + s = 2n, with c_{1} < ⋯ < c_{r} and with d_{1} < ⋯ < d_{s}. If c_{j} < d_{j}, j = 1, …, s then this array is SYT and we are done. Otherwise let i be the smallest index such that c_{i} > d_{i}, then replace the above array by

d_{1} … d_{i−1} d_{i} c_{i} c_{i+1} … c_{s−1} … c_{r} c_{1} … c_{i−1} d_{i+1} d_{i+2} d_{i+3} … d_{s}

Continue until a SYT is reached: thus the process stops at a SYT of shape λ ∈ H(k, 0; 2n).

Remark. Let λ = (λ_{1}, λ_{2}, …) be a partition, λ_{1} ≥ λ_{2} ≥ … and denote λ^{+1} = (λ_{1} + 1, λ_{2}, λ_{3} …). The same bijections can be applied to similar arrays of shape (n + 1, n), yielding a bijective proof for the SYT identity

∑_{μ∈H(2,0;2n+1)} f^{μ} = ∑_{λ∈H(1,1;n+2)} f^{λ} · f^{λ^{+1}}.

Amitai Regev, Department of Mathematics, The Weizmann Institute of Science, Rehovot, Israel. amitai.regev at weizmann.ac.il

Doron Zeilberger, Mathematics Department, Rutgers University (New Brunswick), Piscataway, NJ, USA. zeilberg at math.rutgers.edu .