Séminaire Lotharingien de Combinatoire 81 (2020), Article B81f

ENUMERATION OF BOUNDED LECTURE HALL TABLEAUX

SYLVIE CORTEEL AND JANG SOO KIM

To Christian Krattenthaler, our determinantal hero

Abstract. Recently the authors introduced lecture hall tableaux in their study of multivariate little q-Jacobi polynomials. In this paper, we enumerate bounded lecture hall tableaux. We show that their enumeration is closely related to standard and semistandard Young tableaux. We also show that the number of bounded lecture hall tableaux occurs as a coefficient in the Schur expansion of s_{λ}(m + y_{1}, …, m + y_{n}). To prove this result, we use two main tools: non-intersecting lattice paths and bijections. In particular, we use ideas developed by Krattenthaler to prove bijectively the hook content formula.

1. Introduction

Recently the authors [9] introduced lecture hall tableaux in their study of multivariate little q-Jacobi polynomials P_{λ}(x; a, b; q) with t = q. They showed that, if we expand the Schur function s_{λ}(x) in terms of P_{μ}(x; a, b; q) and vice versa as

s_{λ}(x) = ∑_{μ} M_{λ,μ}P_{μ}(x; a, b; q), P_{λ}(x; a, b; q) = ∑_{μ} N_{λ,μ}s_{μ}(x),

then the coefficients M_{λ,μ} and N_{λ,μ} can be expressed as generating functions for lecture hall tableaux of shape λ/μ.

A lecture hall tableau is a certain filling of a skew shape λ/μ with nonnegative integers. Since the entries in a lecture hall tableau can be arbitrarily large, there are infinitely many lecture hall tableaux of a given shape. If we impose an upper bound on their entries we can consider the number of lecture hall tableaux. The main goal of this paper is to enumerate such bounded lecture hall tableaux.

Bounded lecture hall objects were first enumerated by the first author, Lee and Savage in [10]. They showed that the number of sequences λ = (λ_{1}, …, λ_{n}) of integers such that

m ≥ \frac{λ_{1}}{1} ≥ \frac{λ_{2}}{2} ≥ ⋯ ≥ \frac{λ_{n}}{n} ≥ 0

is equal to the number of sequences λ = (λ_{1}, …, λ_{n}) of integers such that

m ≥ \frac{λ_{1}}{n} ≥ \frac{λ_{2}}{n − 1} ≥ ⋯ ≥ \frac{λ_{n}}{1} ≥ 0.

2010 Mathematics Subject Classification. Primary: 05A15; Secondary: 33D45, 33D50, 05A30.

Key words and phrases. lecture hall tableau, standard Young tableau, semistandard Young tableau, bijective proof, Schur function.

This number is equal to (m + 1)^{n}. As remarked by Matt Beck [5], this is also the Ehrhart polynomial of the n-cube. This observation started a collection of very interesting papers connecting lecture hall partitions to geometric combinatorics and in particular polytopes. We cite for example [3, 4, 16, 21]. An overview of the techniques and results is presented in the survey by Carla Savage [22].

We will see that counting bounded lecture hall tableaux is naturally related to standard and semistandard Young tableaux. To state our results we first give definitions of related objects.

A partition is a weakly decreasing sequence λ = (λ_{1}, …, λ_{k}) of positive integers. Each integer λ_{i} is called a part of λ. The length ℓ(λ) of λ is the number of parts. We identify a partition λ = (λ_{1}, …, λ_{k}) with its Young diagram, which is a left-justified array of squares, called cells, with λ_{i} cells in the ith row for 1 ≤ i ≤ k. In other words, we consider λ = (λ_{1}, …, λ_{k}) as the set of cells (i, j) such that 1 ≤ i ≤ k and 1 ≤ j ≤ λ_{i}. For two partitions λ and μ we write μ ⊂ λ to mean that the Young diagram of μ is contained in that of λ as a set. In this case, a skew shape λ/μ is defined to be the set-theoretic difference λ \ μ of their Young diagrams. We denote by |λ/μ| the number of cells in λ/μ. A partition λ is also considered as a skew shape by λ = λ/∅.

A tableau of shape λ/μ is a filling of the cells in λ/μ with nonnegative integers. In other words, a tableau is a map T : λ/μ → ℕ, where ℕ is the set of nonnegative integers. A standard Young tableau of shape λ/μ is a tableau of shape λ/μ such that every integer 1 ≤ i ≤ |λ/μ| appears exactly once and the entries are decreasing in each row and in each column. Let SYT(λ/μ) denote the set of standard Young tableaux of shape λ/μ. We note that it is more common to define a standard Young tableau to have entries increasing in each row and column. However, for our purpose in this paper, it is more convenient to have entries decreasing.

It is well known that the number of standard Young tableaux of shape λ is given by the hook length formula due to Frame, Robinson, and Thrall [11]:

(1)  |SYT(λ)| = \frac{|λ|!}{∏_{(i,j)∈λ} h(i, j)},

where h(i, j) = λ_{i} + λ′_{j} − i − j + 1, and λ′_{j} is the number of integers r with 1 ≤ r ≤ ℓ(λ) and λ_{r} ≥ j. There are many proofs of the hook length formula, see the survey by Adin and Roichman [1]. Among these, a remarkable bijective proof of (1) was found by Novelli, Pak, and Stoyanovskii [20] using a “jeu de taquin” sorting algorithm.

A semistandard Young tableau of shape λ/μ is a tableau of shape λ/μ such that the entries are weakly decreasing in each row and strictly decreasing in each column. We denote by SSYT(λ/μ) the set of semistandard Young tableaux of shape λ/μ. We also denote by SSYT_{n}(λ/μ) the set of T ∈ SSYT(λ/μ) with max(T) < n, i.e., the entries of T are taken from {0, 1, …, n − 1}. Stanley [23] showed that the number of such bounded semistandard Young tableaux is given by the hook content formula

(2)  |SSYT_{n}(λ)| = ∏_{(i,j)∈λ} \frac{n + c(i, j)}{h(i, j)},

25 25 21 16 18 21 10 4 8 9 2 0 4 4 0  ^{\frac{25}{8} \frac{25}{9} \frac{21}{10} \frac{16}{5} \frac{18}{6} \frac{21}{7} \frac{10}{8} \frac{4}{9} \frac{8}{3} \frac{9}{4} \frac{2}{5} \frac{0}{6} \frac{4}{2} \frac{4}{3} \frac{0}{4}}  3 2 2 3 3 3 1 0 2 2 0 0 2 1 0

Figure 1. On the left is a lecture hall tableau L ∈ LHT_{n}(λ/μ) for n = 5, λ = (6, 6, 4, 3) and μ = (3, 1). The diagram in the middle shows the number L(i, j)/(n + c(i, j)) for each entry (i, j) ∈ λ/μ. The diagram on the right is the tableau ⌊L⌋.

where c(i, j) = j − i is the content of the cell (i, j). There are also many proofs of the hook content formula. Krattenthaler [14] found a bijective proof of (2) that uses a modified jeu de taquin sorting algorithm. In this paper we will use Krattenthaler’s jeu de taquin to investigate lecture hall tableaux.

An n-lecture hall tableau of shape λ/μ is a tableau L of shape λ/μ satisfying the following conditions:

\frac{L(i, j)}{n + c(i, j)} ≥ \frac{L(i, j + 1)}{n + c(i, j + 1)}, \frac{L(i, j)}{n + c(i, j)} > \frac{L(i + 1, j)}{n + c(i + 1, j)}.

The set of n-lecture hall tableaux of shape λ/μ is denoted by LHT_{n}(λ/μ). For L ∈ LHT_{n}(λ/μ), let ⌊L⌋ be the tableau of shape λ/μ whose (i, j)-entry is ⌊L(i, j)/(n − i + j)⌋, see Figure 1 for an example. The set of n-lecture hall tableaux L ∈ LHT_{n}(λ/μ) with max(⌊L⌋) < m is denoted by LHT_{n,m}(λ/μ). We will sometimes call such n-lecture hall tableaux “m-bounded”. Since the bounded lecture hall tableaux in LHT_{n,1}(λ/μ) play an important role in our paper, we give them a special name. These objects have another description as follows.

A semistandard n-content tableau of shape λ/μ is a semistandard Young tableau S of shape λ/μ with the additional condition that 0 ≤ S(i, j) < n − i + j for every (i, j) ∈ λ/μ. We denote by SSCT_{n}(λ/μ) the set of semistandard n-content tableaux of shape λ/μ. It is easy to see that

SSCT_{n}(λ/μ) = LHT_{n,1}(λ/μ),
SSCT_{n}(λ) = SSYT_{n}(λ).

In this paper we prove the following formula for the number of bounded lecture hall tableaux. Given a partition μ, we use the convention that μ_{i} = 0 for all integers i > ℓ(μ).

Theorem 1.1. For partitions λ and μ with μ ⊂ λ and ℓ = ℓ(λ) ≤ n, we have

|LHT_{n,m}(λ/μ)| = m^{|λ/μ|} det (\binom{λ_{i} + n − i}{μ_{j} + n − j})_{1≤i,j≤ℓ} .

Note that Theorem 1.1 implies that

(3)  |LHT_{n,m}(λ/μ)| = m^{|λ/μ|}|LHT_{n,1}(λ/μ)| = m^{|λ/μ|}|SSCT_{n}(λ/μ)|.

The determinant in Theorem 1.1 has another description in terms of standard Young tableaux.

Proposition 1.2. For partitions λ and μ with μ ⊂ λ and ℓ = ℓ(λ) ≤ n, we have

|SSCT_{n}(λ/μ)| = det (\binom{λ_{i} + n − i}{μ_{j} + n − j})_{1≤i,j≤ℓ} = \frac{|SYT(λ/μ)|}{|λ/μ|!} ∏_{x∈λ/μ}(n + c(x)).

Kirillov and Scrimshaw [13] recently conjectured that the number \frac{|SYT(λ/μ)|}{|λ/μ|!} ∏_{x∈λ/μ}(n + c(x)) on the right hand side of the identity in Proposition 1.2 is always an integer and proposed a problem to find a combinatorial object for this number. Proposition 1.2 gives an affirmative answer to the problem. Theorem 1.1 and Proposition 1.2 together with (1) and (2) immediately imply the following corollary.

Corollary 1.3. For partitions λ and μ with μ ⊂ λ and ℓ(λ) ≤ n, we have

|LHT_{n,m}(λ/μ)| = m^{|λ/μ|} \frac{|SYT(λ/μ)|}{|λ/μ|!} ∏_{x∈λ/μ}(n + c(x)).

In particular, the number of n-lecture hall tableaux of shape λ whose maximum entry is less than nm is

|LHT_{n,m}(λ)| = m^{|λ|}|SSYT_{n}(λ)| = m^{|λ|} ∏_{x∈λ} \frac{n + c(x)}{h(x)}.

Using Naruse’s hook length formula for |SYT(λ/μ)| in [19], we get another enumerative formula.

Corollary 1.4. For partitions λ and μ with μ ⊂ λ and ℓ(λ) ≤ n, the number of m-bounded lecture tableaux of shape λ/μ is

|LHT_{n,m}(λ/μ)| = m^{|λ/μ|} ∏_{x∈λ/μ}(n + c(x)) ∑_{D} ∏_{x∈λ\D} \frac{1}{h(x)},

where the sum is over all excited diagrams D of λ/μ. See [18, 19] for details on excited diagrams.

In this paper we also show that the number of m-bounded lecture hall tableaux occurs naturally as the coefficient in the Schur expansion of s_{λ}(m + y_{1}, …, m + y_{n}). Recall that, for a sequence of variables x = (x_{0}, x_{1}, …), the (skew) Schur function s_{λ/μ}(x) is defined by

s_{λ/μ}(x) = ∑_{T ∈SSYT(λ/μ)} x^{T} ,

where

x^{T} = ∏_{(i,j)∈λ/μ} x_{T (i,j)}.

Note that

s_{λ}(x_{0}, x_{1}, …, x_{n−1}) = ∑_{T ∈SSYT_{n}(λ)} x^{T} ,

and |SSYT_{n}(λ)| = s_{λ}(1^{n}), where (1^{n}) is the sequence (1, 1, …, 1) of n ones.

Theorem 1.5. For integers n, m ≥ 0, variables y_{0}, y_{1}, …, y_{n−1}, and a partition λ with at most n parts, we have

s_{λ}(m + y_{0}, m + y_{1}, …, m + y_{n−1}) = ∑_{μ⊂λ} |LHT_{n,m}(λ/μ)|s_{μ}(y_{0}, y_{1}, …, y_{n−1}).

If m = 1 in Theorem 1.5 we obtain the following formula due to Lascoux [15]:

(4) s_{λ}(1+y_{0}, 1+y_{1}, …, 1+y_{n−1}) = ∑_{μ⊂λ} det (\binom{λ_{i} + n − i}{μ_{j} + n − j})_{1≤i,j≤ℓ(λ)} s_{μ}(y_{0}, y_{1}, …, y_{n−1}).

Lascoux [15] used (4) to compute the Chern classes of the exterior square and symmetric square of a vector bundle, see also [17, Chapter 1, §3, Example 10]. We note Theorem 1.5 can also be obtained from (4) and Theorem 1.1.

Our next theorem is a generalization of Theorem 1.5 to skew shapes. In order to state the theorem we first need to introduce some definitions.

We define

L_{λ/μ}^{n}(x) = ∑_{T ∈LHT_{n}(λ/μ)} x^{⌊T ⌋},

and

S_{λ/μ}^{n}(x) = ∑_{T ∈SSCT_{n}(λ/μ)} x^{T} .

Note that S_{λ}^{n}(x) = s_{λ}(x_{0}, x_{1}, …, x_{n−1}).

The following theorem is the main theorem of this paper, which is a skew version of Theorem 1.5.

Theorem 1.6. Let λ and μ be partitions with μ ⊂ λ and ℓ(λ) ≤ n. For any sequences x = (x_{0}, x_{1}, …) and y = (y_{0}, y_{1}, …) of variables, we have

S_{λ/μ}^{n}(|x| + y) = ∑_{μ⊂ν⊂λ} L_{λ/ν}^{n}(x)S_{ν/μ}^{n}(y),

where |x| = x_{0} + x_{1} + ⋯ and |x| + y = (|x| + y_{0}, |x| + y_{1}, …).

In this paper we give two proofs of Theorem 1.6: one proof uses a Jacobi–Trudi type determinant identity, and the other proof is bijective. In particular the bijective proof of Theorem 1.6 uses a variation of jeu de taquin due to Krattenthaler [14].

If μ = ∅ and x = (1^{m}) in Theorem 1.6, we have

S_{λ}^{n}(m + y) = ∑_{ν⊂λ} L_{λ/ν}^{n}(1^{m})S_{ν}^{n}(y).

Since S_{ν}^{n}(y) = s_{ν}(y_{0}, y_{1}, …, y_{n−1}) for any partition ν, we obtain Theorem 1.5.

We can also deduce (3) from Theorem 1.6 as follows. If x = (x_{0}, …, x_{m−1}) and y = (0, 0, …) in Theorem 1.6, we have

(5)  S_{λ/μ}^{n}(|x|, |x|, …) = L_{λ/μ}^{n}(x).

By definition we have L_{λ/μ}^{n}(1^{m}) = |LHT_{n,m}(λ/μ)| and

(6)  S_{λ/μ}^{n}(|x|, |x|, …) = |x|^{|λ/μ|}S_{λ/μ}^{n}(1, 1, …) = |x|^{|λ/μ|}|SSCT_{n}(λ/μ)|.

Then (3) follows from (5), (6) with x = (1^{m}).

The remainder of this paper is organized as follows. In Section 2 we give a simple proof of Theorem 1.1 using a Jacobi–Trudi type determinant identity. We also prove Proposition 1.2. In Section 3 we prove Theorem 1.6 also using a Jacobi–Trudi identity. The main tool of Sections 2 and 3 is to transform the tableaux into some system of non-intersecting paths on a planar graph and use the Lindström–Gessel–Viennot lemma [12]. In Section 4 we give a bijective proof of Theorem 1.6. In Section 5 we find a connection of our bijection with the bijections due to Novelli, Pak, and Stoyanovskii [20] and Krattenthaler [14]. Finally, in Section 6 we provide some open problems.

Acknowledgements. The authors want to thank the University of California at Berkeley, where this work was started, and BIRS (Banff, Canada), where this work was completed. We want to thank personally the Director of BIRS who accepted to extend our stay at BIRS after the workshop “Asymptotic Algebraic Combinatorics” in March 2019. Both authors would like to thank Curtis Greene and Carla Savage for their precious comments and advice during the elaboration of this paper, Brendon Rhoades, Travis Scrimshaw and U-Keun Song for helpful discussions, and the anonymous referees and Christian Krattenthaler for their careful reading and helpful comments. J.S.K. was supported by NRF grants #2019R1F1A1059081 and #2016R1A5A1008055.

2. Jacobi–Trudi identity

In this section, we interpret an n-lecture hall tableau as a family of non-intersecting lattice paths and give a Jacobi–Trudi type identity for the generating function L_{λ/μ}^{n}(x) for n-lecture hall tableaux of a given shape. We then prove Theorem 1.1 and Proposition 1.2.

The paths we consider are on an infinite directed graph embedded in the plane ℝ^{2} defined as follows.

Definition 2.1. The lecture hall graph G = (V, E) is a directed graph on the vertex set

V = \{(i, \frac{j}{i + 1}) : i, j ∈ ℕ\} ,

whose edge set E consists of

• (nearly) horizontal edges from (i, k+ \frac{r}{i+1}) to (i+1, k+ \frac{r}{i+2}) for i, k ∈ ℕ and 0 ≤ r ≤ i, and

• vertical edges from (i, k + \frac{r+1}{i+1}) to (i, k + \frac{r}{i+1}) for i, k ∈ ℕ and 0 ≤ r ≤ i.

0123456789∞ ⋮⋮⋮012· · · · · ·

Figure 2. The lecture hall graph G.

See Figure 2 for an example of the lecture hall graph G. We note that in [9] a slightly different graph is used to describe lecture hall tableaux. However, both graphs can equally be used for this purpose.

We now consider (directed) paths in the lecture hall graph. A path in G is a (possibly infinite) sequence P of vertices of G such that (u, v) is a directed edge of G for every two consecutive elements u and v in P. If P is a finite path (u_{ℓ}, u_{ℓ−1}, …, u_{1}), we say that P is a path from u_{ℓ} to u_{1}. If P is an infinite path (…, u_{3}, u_{2}, u_{1}) for u_{i} = (a_{i}, b_{i}), i ≥ 1, such that lim_{i→∞} a_{i} = a, we say that P is a path from (a, ∞) to (a_{1}, b_{1}).

From now on every path considered in this section will be either a finite path or an infinite path in G satisfying the above limit condition.

We define the weight wt(P) of a path P to be the product of its edge weights, where the weight of the horizontal edge from (i, k + \frac{r}{i+1}) to (i + 1, k + \frac{r}{i+2}) is defined to be x_{k} and the weight of every vertical edge is defined to be 1. A sequence (P_{1}, …, P_{k}) of paths is said to be non-intersecting if no two paths share a vertex. The weight of the system (P_{1}, …, P_{k}) of paths is defined to be the product ∏_{i=1}^{k} wt(P_{i}) of the weights of the paths. The following lemma gives a way of understanding lecture hall tableaux as non-intersecting paths.

Lemma 2.2. Let λ and μ be partitions satisfying μ ⊂ λ and ℓ = ℓ(λ) ≤ n. Then there exists a bijection between LHT_{n}(λ/μ) and the set of non-intersecting paths (P_{1}, …, P_{ℓ}), where P_{i} is a path from (μ_{i} + n − i, ∞) to (λ_{i} + n − i, 0). This bijection is such that if L ∈ LHT_{n}(λ/μ) corresponds to (P_{1}, …, P_{ℓ}) then

x^{⌊L⌋} = ∏_{i=1}^{ℓ} wt(P_{i}).

Proof. As in [9] the bijection between lecture hall tableaux L and non-intersecting paths (P_{1}, …, P_{ℓ}) is constructed by counting the number of regions under each horizontal edge of each path. Namely, L(i, j) is given by the number of regions under the (j −μ_{i})^{th} horizontal edge of P_{i}. Then the weight of the edge is x_{⌊L(i,j)/(n−i+j)⌋}, so the bijection satisfies the desired property. □

012345678910 ∞ ⋮⋮⋮01234· · · · · · x_{2} x_{1} x_{0} x_{2} x_{2} x_{0} x_{0} x_{3} x_{3} x_{3} x_{1} x_{0} x_{3} x_{2} x_{2}

Figure 3. Non-intersecting paths in G. For each horizontal edge, its weight is shown above it.

Figure 3 shows the non-intersecting paths in G corresponding to the lecture hall tableau L ∈ LHT_{n}(λ/μ) in Figure 1 for n = 5, λ = (6, 6, 4, 3) and μ = (3, 1). The paths in Figure 3 have weight x_{0}^{4}x_{1}^{2}x_{2}^{5}x_{3}^{4}, which is equal to x^{⌊L⌋}. The entries of ⌊L⌋ can be seen on the right of Figure 1.

Recall that x = (x_{0}, x_{1}, …) and that |x| = x_{0} + x_{1} + · · ·. The following proposition is a Jacobi–Trudi type identity for L_{λ/μ}^{n}(x).

Proposition 2.3. Let λ and μ be partitions satisfying μ ⊂ λ and ℓ = ℓ(λ) ≤ n. Then we have

L_{λ/μ}^{n}(x) = det (L_{(λ_{i}−μ_{j}−i+j)}^{μ_{j}+n−j+1}(x))_{1≤i,j≤ℓ} .

Proof. This is a direct consequence of the Lindström–Gessel–Viennot lemma [12], which states that the weight generating function for non-intersecting paths from vertices u_{1}, u_{2}, …, u_{ℓ} to vertices v_{1}, v_{2}, …, v_{ℓ} of the planar graph G is

det(P (u_{j}, v_{i}))_{1≤i,j≤ℓ},

where P (u_{j}, v_{i}) is the weight generating function of the paths from u_{j} to v_{i}. Here we choose u_{j} = (μ_{j} + n − j, ∞), v_{i} = (λ_{i} + n − i, 0), and therefore P (u_{j}, v_{i}) = L_{(λ_{i}−μ_{j}−i+j)}^{μ_{j}+n−j+1}(x). Then the proposition follows from Lemma 2.2. □

We now compute the entries of the matrix of the previous proposition.

Proposition 2.4. For n, k ≥ 0 we have

L_{(k)}^{n}(x) = |x|^{k}\binom{n + k − 1}{k}.

Proof. Let us first recall that

(7)  L_{(k)}^{n}(x) = ∑_{L} x^{⌊L⌋},

where the sum is over the n-lecture hall tableaux L ∈ LHT_{n}(λ) of shape λ = (k), i.e.,

\frac{L(1, 1)}{n} ≥ \frac{L(1, 2)}{n + 1} ≥ ⋯ ≥ \frac{L(1, k)}{n + k − 1} ≥ 0.

Consider the case x = (x_{0}, 0, 0, …). Then the n-lecture hall tableaux L contributing nonzero terms in (7) are those satisfying

1 > \frac{L(1, 1)}{n} ≥ \frac{L(1, 2)}{n + 1} ≥ ⋯ ≥ \frac{L(1, k)}{n + k − 1} ≥ 0.

It is easy to check that for a, b, k ∈ ℕ, the condition 1 > \frac{a}{k} ≥ \frac{b}{k+1} is equivalent to k > a ≥ b. Thus, the above condition is equivalent to n > L(1, 1) ≥ ⋯ ≥ L(1, k) ≥ 0 and we have

L_{(k)}^{n}(x_{0}) := L_{(k)}^{n}(x_{0}, 0, 0, …) = x_{0}^{k}\binom{n + k − 1}{k}.

Now consider the general case x = (x_{0}, x_{1}, …). Fix an n-lecture hall tableau L ∈ LHT_{n}((k)) and let j be the index such that \frac{L(1,j)}{n+j−1} ≥ 1 and \frac{L(1,j+1)}{n+j} < 1. Here we suppose that L_{1,0} = ∞ and L_{1,k+1} = 0 so that the index 0 ≤ j ≤ k is always defined. We can decompose L into two lecture hall tableaux L′ ∈ LHT_{n}((j)) and L′′ ∈ LHT_{n+j}((k − j)) so that L′(1, i) = L(1, i) and L′′(1, i) = L(1, j + i). Then L′ and L′′ satisfy

(8)  \frac{L′(1, 1)}{n} ≥ ⋯ ≥ \frac{L′(1, j)}{n + j − 1} ≥ 1,

(9)  1 > \frac{L′′(1, 1)}{n + j} ≥ ⋯ ≥ \frac{L′′(1, k − j)}{n + k − 1} ≥ 0.

Conversely, for any pair of L′ and L′′ satisfying (8) and (9), we obtain an n-lecture hall tableau L ∈ LHT_{n}((k)). Moreover, the tableaux L′ ∈ LHT_{n}((j)) satisfying the condition (8) are those contributing nonzero terms in L_{(j)}^{n}(0, x_{1}, x_{2}, …) and the tableaux L′′ ∈ LHT_{n+j}((k − j)) satisfying the condition (9) are those contributing nonzero terms in L_{(k−j)}^{n+j}(x_{0}). Therefore,

L_{(k)}^{n}(x_{0}, x_{1}, …) = ∑_{j=0}^{k} L_{(k−j)}^{n+j}(x_{0})L_{(j)}^{n}(0, x_{1}, x_{2}, …).

Now we notice that sequences (L′(1, 1), …, L′(1, j)) such that

\frac{L′(1, 1)}{n} ≥ ⋯ ≥ \frac{L′(1, j)}{n + j − 1} ≥ 1,

are in bijection with sequences (U′(1, 1), …, U′(1, j)) such that

\frac{U′(1, 1)}{n} ≥ ⋯ ≥ \frac{U′(1, j)}{n + j − 1} ≥ 0,

by setting U′(1, i) = L′(1, i) − n + i − 1 for 1 ≤ i ≤ j. This implies that

x^{⌊L′⌋} = ∏_{i=1}^{j} x_{⌊L′_{1,i}/(n−i+1)⌋} = ∏_{i=1}^{j} x_{⌊U′_{1,i}/(n−i+1)⌋+1}.

We get that

L_{(j)}^{n}(0, x_{1}, x_{2}, …) = L_{(j)}^{n}(x_{1}, x_{2}, …).

Therefore

L_{(k)}^{n}(x_{0}, x_{1}, …) = ∑_{j=0}^{k} L_{(k−j)}^{n+j}(x_{0})L_{(j)}^{n}(x_{1}, x_{2}, …).

This gives L_{(k)}^{n}(x_{0}, x_{1}, …) = \binom{n+k−1}{k}|x|^{k} using induction. □

Combining the two previous propositions, we obtain the main theorem in this section.

Theorem 2.5. Let λ and μ be partitions satisfying μ ⊂ λ and ℓ = ℓ(λ) ≤ n. Then we have

L_{λ/μ}^{n}(x) = |x|^{|λ/μ|} det (\binom{λ_{i} + n − i}{μ_{j} + n − j})_{1≤i,j≤ℓ} .

Proof. By Propositions 2.3 and 2.4, we have

L_{λ/μ}^{n}(x) = det (|x|^{λ_{i}−i−μ_{j}+j}\binom{λ_{i} + n − i}{μ_{j} + n − j})_{1≤i,j≤ℓ} .

By factoring out the factor |x|^{λ_{i}−i} for each row i and the factor |x|^{j−μ_{j}} for each column j, we obtain the theorem. □

Setting x = (1^{m}) in Theorem 2.5, we obtain Theorem 1.1. Since |SSCT_{n}(λ/μ)| = L_{λ/μ}^{n}(1, 0, 0, …), Theorem 2.5 implies that

(10)  |SSCT_{n}(λ/μ)| = det (\binom{λ_{i} + n − i}{μ_{j} + n − j})_{1≤i,j≤ℓ} .

Therefore Theorem 2.5 is equivalent to

(11)  L_{λ/μ}^{n}(x) = |x|^{|λ/μ|}|SSCT_{n}(λ/μ)|.

Since SSCT_{n}(λ) = SSYT_{n}(λ), by setting μ = ∅ in (11) we obtain the following corollary.

Corollary 2.6. For a partition λ with at most n parts, we have

L_{λ}^{n}(x) = |x|^{|λ|}s_{λ}(1^{n}).

We finish this section by giving a proof of Proposition 1.2.

Proof of Proposition 1.2. The first equality is shown in (10). It remains to show that

(12)  det (\binom{λ_{i} + n − i}{μ_{j} + n − j})_{1≤i,j≤ℓ} = \frac{|SYT(λ/μ)|}{|λ/μ|!} ∏_{x∈λ/μ}(n + c(x)).

We need the following determinant formula for |SYT(λ/μ)| due to Aitken [2], see also [26, Corollary 7.16.3]:

|SYT(λ/μ)| = |λ/μ|! det (\frac{1}{(λ_{i} − μ_{j} − i + j)!})_{1≤i,j≤ℓ} .

Then (12) follows immediately from Aitken’s formula with the identities

det (\binom{λ_{i} + n − i}{μ_{j} + n − j})_{1≤i,j≤ℓ} = ∏_{i=1}^{ℓ(λ)} \frac{(λ_{i} + n − i)!}{(μ_{i} + n − i)!} det (\frac{1}{(λ_{i} − μ_{j} − i + j)!})_{1≤i,j≤ℓ} ,

and

∏_{i=1}^{ℓ(λ)} \frac{(λ_{i} + n − i)!}{(μ_{i} + n − i)!} = ∏_{x∈λ/μ}(n + c(x)),

which can be easily verified. □

3. Proof of Theorem 1.6 using a Jacobi–Trudi identity

In this section, we prove Theorem 1.6 using a Jacobi–Trudi identity for the generating function

(13)  S_{λ/μ}^{n}(y) = ∑_{T ∈SSCT_{n}(λ/μ)} y^{T} .

To this end we introduce another infinite directed graph. We use the notation ω for the smallest infinite ordinal number, i.e, 1 < 2 < ⋯ < ω.

Definition 3.1. The content graph G′ is the directed graph G′ = (V′, E′) on the vertex set

V′ = \{(i, ω + \frac{r}{i + 1}) : i ∈ ℕ, r ∈ \{0, 1, …, i + 1\}\} ,

whose edge set E′ consists of

• (nearly) horizontal edges from (i, ω + \frac{r}{i+1}) to (i+1, ω + \frac{r}{i+2}) for i ∈ ℕ and 0 ≤ r ≤ i, and

• vertical edges from (i, ω + \frac{r+1}{i+1}) to (i, ω + \frac{r}{i+1}) for i ∈ ℕ and 0 ≤ r ≤ i.

Figure 4 shows the content graph G′. Now to any path P′ in G′, we associate a monomial wt(P′) equal to the product of the weights of the edges of P′, where the weight of the horizontal edge from (i, ω + \frac{r}{i+1}) to (i + 1, ω + \frac{r}{i+2}) is defined to be y_{r}, and the weight of every vertical edge is 1.

The following lemma gives a way to understand a semistandard n-content tableau as non-intersecting paths in G′.

\begin{matrix}0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ ω \\ ω + 1 \\ ⋯ \end{matrix}

Figure 4. The content graph G′.

\begin{matrix}0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ ω \\ ω + 1 \\ ⋯ \\ y_{1} \\ y_{0} \\ y_{0} \\ y_{2} \\ y_{1} \\ y_{1} \\ y_{1} \\ y_{4} \\ y_{3} \\ y_{3} \\ y_{0} \\ y_{0} \end{matrix}

Figure 5. Non-intersecting paths in G′. The weight of each horizontal edge is shown above the edge.

4 3 3 0 0 2 1 1 1 1 0 0

Figure 6. A semistandard n-content tableau of shape λ/μ with n = 4, λ = (6, 4, 3) and μ = (1).

Lemma 3.2. There is a bijection between SSCT_{n}(λ/μ) and the set of non-intersecting paths (P_{1}, …, P_{ℓ}) in G′, where P_{i} starts at u_{i} = (μ_{i} +n−i, ω +1) and ends at v_{i} = (λ_{i} +n−i, ω), for i = 1, …, ℓ. The correspondence between T ∈ SSCT_{n}(λ/μ) and (P_{1}, …, P_{ℓ}) is as follows. The number of regions under the (j − μ_{i})^{th} horizontal step of P_{i} is the entry T (i, j). In this case we have y^{T} = ∏_{i=1}^{n} wt(P_{i}).

Proof. This can be proved similarly to the proof of Lemma 2.2. □

For example, the non-intersecting paths in Figure 5 correspond to the tableau in Figure 6. Note that both have weight y_{0}^{4}y_{1}^{4}y_{2}y_{3}^{2}y_{4}.

The following is a Jacobi–Trudi identity for S_{λ/μ}^{n}(x).

Proposition 3.3. Let λ and μ be partitions satisfying μ ⊂ λ and ℓ = ℓ(λ) ≤ n. Then we have

S_{λ/μ}^{n}(y) = det (S_{(λ_{i}−μ_{j}−i+j)}^{μ_{j}+n−j+1}(y))_{1≤i,j≤ℓ} .

Proof. The proof is similar to that of Proposition 2.3, hence we omit it. □

Since SSCT_{n}(λ) = SSYT_{n}(λ), the definition (13) of S_{λ/μ}^{n}(x) implies that for k ≥ 0 and n ≥ 1,

(14)  S_{(k)}^{n}(y) = s_{(k)}(y_{0}, …, y_{n−1}) = h_{k}(y_{0}, …, y_{n−1}),

0123456789ω ω + 1 ⋮⋮⋮012· · · · · · · · ·

Figure 7. The extended lecture hall graph G^{∗} = G′ ⊎ G.

where h_{k}(y_{0}, …, y_{n−1}) is the complete homogeneous polynomial defined by

(15)  h_{k}(y_{0}, …, y_{n−1}) = ∑_{0≤i_{1}≤···≤i_{k}≤n−1} y_{i_{1}} ⋯ y_{i_{k}}.

Note that y_{0}, …, y_{n−1} are the only variables that actually appear in S_{(k)}^{n}(y) even though y = (y_{0}, y_{1}, …) is an infinite sequence of variables. Using (14), Proposition 3.3 can be restated as

(16)  S_{λ/μ}^{n}(y) = det(h_{λ_{i}−μ_{j}−i+j}(y_{0}, …, y_{μ_{j}+n−j}))_{1≤i,j≤ℓ}.

In order to prove Theorem 1.6 we introduce yet another graph.

Definition 3.4. The extended lecture hall graph G^{∗} is the disjoint union G′ ⊎ G of the content graph G′ and the lecture hall graph G.

We draw the extended lecture hall graph G^{∗} = G′ ⊎ G with G′ on top of G as shown in Figure 7 so that each vertex (i, ω) of G′ can be considered as the “limit” of the sequence of vertices (i, 0), (i, 1), (i, 2), … in G.

We define an ω-path to be a pair Q = (P′, P) satisfying the following conditions: • P′ and P are paths in G′ and G, respectively.

• P′ is a path from (a, ω + 1) to (b, ω) and P is a path from (b, ∞) to (c, 0) for some

a ≤ b ≤ c. In this case we say that Q is an ω-path from (a, ω + 1) to (c, 0). We use the weight wt(P) for a path in G as in Section 2 and define the weight of an ω-path Q = (P′, P) by wt(Q) = wt(P′) wt(P).

We are now ready to prove Theorem 1.6, which states that

(17)  S_{λ/μ}^{n}(|x| + y) = ∑_{μ⊂ν⊂λ} L_{λ/ν}^{n}(x)S_{ν/μ}^{n}(y).

1 25 21 1 0 21 10 4 8 9 2 0 4 4 0

Figure 8. A pair (L, S) of tableaux L ∈ LHT_{n}(λ/ν) and S ∈ SSCT_{n}(ν/μ) for n = 5, λ = (6, 6, 4, 3), μ = (3, 1), and ν = (4, 3). The tableaux L and S are separated by the thick border.

Proof of Theorem 1.6. Let LHS and RHS be the left hand side and the right hand side of (17), respectively. By (16), we have

(18)  LHS = det(h_{λ_{i}−μ_{j}−i+j}(y_{0} + |x|, …, y_{μ_{j}+n−j} + |x|))_{1≤i,j≤ℓ}.

Our strategy is to express RHS also as a determinant that agrees with the determinant in (18) entry-wise.

First, observe that

RHS = ∑_{μ⊂ν⊂λ} L_{λ/ν}^{n}(x)S_{ν/μ}^{n}(y) = ∑_{(L,S)} x^{⌊L⌋}y^{S},

where the sum is over all pairs (L, S) of tableaux L ∈ LHT_{n}(λ/ν) and S ∈ SSCT_{n}(ν/μ) for some partition ν with μ ⊂ ν ⊂ λ. Combining the bijections in Lemmas 2.2 and 3.2, we obtain a bijection between the set of such pairs (L, S) and the set of non-intersecting ωpaths (Q_{1}, …, Q_{ℓ}) such that Q_{i} is an ω-path from u_{i} = (μ_{i}+n−i, ω+1) to v_{i} = (λ_{i}+n−i, 0). Furthermore, under this bijection we have x^{⌊L⌋}y^{S} = wt(Q_{1}) ⋯ wt(Q_{ℓ}), which implies that

RHS = ∑_{(L,S)} x^{⌊L⌋}y^{S} = ∑_{(Q_{1},...,Q_{ℓ})} wt(Q_{1}) ⋯ wt(Q_{ℓ}).

For example, the pair (L, S) of tableaux given in Figure 8 corresponds to the non-inter-secting ω-paths in Figure 9.

By the Lindström–Gessel–Viennot lemma, we have

(19)  RHS = ∑_{(Q_{1},...,Q_{ℓ})} wt(Q_{1}) ⋯ wt(Q_{ℓ}) = det(P̃(u_{j}, v_{i}))_{1≤i,j≤ℓ},

where P̃(u_{j}, v_{i}) is the sum of wt(Q) for all ω-paths Q from u_{j} = (μ_{j} + n − j, ω + 1) to v_{i} = (λ_{i} + n − i, 0). It is easy to see that

(20)  P̃(u_{j}, v_{i}) = ∑_{k=0}^{λ_{i}−μ_{j}−i+j} S_{(k)}^{μ_{j}+n−j+1}(y)L_{(λ_{i}−μ_{j}−i+j−k)}^{μ_{j}+n−j+k+1}(x).

012345678910 ω ω + 1 ⋮⋮⋮01234· · · · · · · · · x_{2} x_{1} x_{0} x_{2} x_{2} x_{0} x_{0} y_{1} y_{0} x_{3} x_{1} x_{0} y_{1} x_{2} x_{2}

Figure 9. Non-intersecting ω-paths in G^{∗}. For each horizontal edge, its weight is shown above it.

By (14) and Proposition 2.4, we have

S_{(k)}^{μ_{j}+n−j+1}(y) = h_{k}(y_{0}, …, y_{μ_{j}+n−j}),
L_{(λ_{i}−μ_{j}−i+j−k)}^{μ_{j}+n−j+k+1}(x) = |x|^{λ_{i}−μ_{j}−i+j−k}\binom{λ_{i} + n − i}{λ_{i} − μ_{j} − i + j − k}.

Therefore, by (18), (19), (20) and the above two equations, it suffices to prove the identity

(21) h_{λ_{i}−μ_{j}−i+j}(y_{0} + |x|, …, y_{μ_{j}+n−j} + |x|)

= ∑_{k=0}^{λ_{i}−μ_{j}−i+j} h_{k}(y_{0}, …, y_{μ_{j}+n−j})|x|^{λ_{i}−μ_{j}−i+j−k}\binom{λ_{i} + n − i}{λ_{i} − μ_{j} − i + j − k}.

Using the definition (15) of the complete homogeneous polynomial, it is not hard to see that

h_{t}(y_{0} + |x|, …, y_{a} + |x|) = ∑_{0≤i_{1}≤···≤i_{t}≤a}(y_{i_{1}} + |x|)(y_{i_{2}} + |x|) ⋯ (y_{i_{t}} + |x|)

= ∑_{k=0}^{t} h_{k}(y_{0}, …, y_{a})h_{t−k}(|x|^{a+k+1}),

where h_{t−k}(|x|^{a+k+1}) means h_{t−k}(\overbrace{|x|, …, |x|}^{a+k+1}). Since h_{t−k}(|x|^{a+k+1}) = |x|^{t−k}\binom{a+t}{t−k}, we obtain

(21) from the above identity by setting a = μ_{j} + n − j and t = λ_{i} − μ_{j} − i + j. The proof is now complete. □

25 25 21 16 18 21 10 4 8 9 2 0 4 4 0  ^{\frac{25}{8} \frac{25}{9} \frac{21}{10} \frac{16}{5} \frac{18}{6} \frac{21}{7} \frac{10}{8} \frac{4}{9} \frac{8}{3} \frac{9}{4} \frac{2}{5} \frac{0}{6} \frac{4}{2} \frac{4}{3} \frac{0}{4}}  1_{3} 7_{2} 1_{2} 1_{3} 0_{3} 0_{3} 2_{1} 4_{0} 2_{2} 1_{2} 2_{0} 0_{0} 0_{2} 1_{1} 0_{0}

Figure 10. On the left is a lecture hall tableau L ∈ LHT_{n}(λ/μ) for n = 5, λ = (6, 6, 4, 3) and μ = (3, 1). The diagram in the middle shows the number L(i, j)/(n + c(i, j)) for each entry (i, j) ∈ λ/μ. The diagram on the right is the corresponding marked tableau T, given by T (i, j) = a_{r}, where a and r are the unique integers satisfying L(i, j) = r · (n − i + j) + a and 0 ≤ a < n − i + j.

4. A bijective proof of the main theorem

In this section, we give a bijective proof of Theorem 1.6. We first introduce some definitions and restate the theorem accordingly.

A marked tableau of shape λ/μ is a map T : λ/μ → ℕ × (ℕ ∪ {∞}). If T (i, j) = (a, r) we say that a is a value and r is a mark. Instead of T (i, j) = (a, r), we will simply write T (i, j) = a_{r}. A marked n-content tableau is a marked tableau T with the condition that, if T (i, j) = a_{r}, then 0 ≤ a < n − i + j. For a marked tableau T of shape λ/μ and a skew shape α ⊂ λ/μ, we denote by T |_{α} the restriction of T to the cells in α.

Let T be a marked tableau of shape λ/μ. For (i, j) ∈ λ/μ, let

wt^{∗}(T (i, j)) = \begin{cases}x_{b}, & if T (i, j) = a_{b} and b ≠ ∞, \\ y_{a}, & if T (i, j) = a_{∞}. \end{cases}

The weight wt^{∗}(T) of T is defined by

wt^{∗}(T) = ∏_{(i,j)∈λ/μ} wt^{∗}(T (i, j)).

Consider an n-lecture hall tableau L ∈ LHT_{n}(λ/μ). We construct a marked tableau T as follows. For each cell (i, j) ∈ λ/μ, let T (i, j) = a_{r}, where r = ⌊L(i, j)/(n + j − i)⌋ and a = L(i, j) − r · (n + j − i). See Figure 10. Clearly, L can be recovered from T. From now on we will identify the lecture hall tableau L with the marked tableau T. Note that under this identification every mark of a lecture hall tableau is a nonnegative integer.

An extended n-lecture hall tableau of shape λ/μ is a marked tableau T : λ/μ → ℕ × (ℕ ∪ {∞}) satisfying the following conditions:

(1) If (i, j) ∈ λ/μ and T (i, j) = a_{r}, then 0 ≤ a < n + j − i.

(2) If (i, j), (i, j +1) ∈ λ/μ and T (i, j) = a_{r}, T (i, j +1) = b_{s}, then we have either r > s, or r = s and a ≥ b.

(3) If (i, j), (i+1, j) ∈ λ/μ and T (i, j) = a_{r}, T (i+1, j) = b_{s}, then we have either r > s, or r = s and a > b.

\begin{matrix}1_{∞} \\ 7_{2} \\ 1_{2} \\ 1_{∞} \\ 0_{∞} \\ 0_{3} \\ 2_{1} \\ 4_{0} \\ 2_{2} \\ 1_{2} \\ 2_{0} \\ 0_{0} \\ 0_{2} \\ 1_{1} \\ 0_{0} \end{matrix}

Figure 11. An extended n-lecture hall tableau L in LHT_{n}^{∗}(λ/μ), where n = 5, λ = (6, 6, 4, 2) and μ = (3, 1). The weight of L is wt^{∗}(L) = x_{0}^{4}x_{1}^{2}x_{2}^{5}x_{3}^{1}y_{0}y_{1}^{2}. The tail of L is indicated by the blue circle.

\begin{matrix}6_{2} \\ 2_{1} \\ 1_{∞} \\ 2_{0} \\ 2_{2} \\ 2_{0} \\ 0_{2} \\ 0_{3} \\ 2_{2} \\ 1_{∞} \\ 1_{0} \\ 0_{0} \\ 0_{1} \\ 0_{2} \\ 0_{∞} \end{matrix}

Figure 12. A marked semistandard n-content tableau S in SSCT_{n}^{∗}(λ/μ), where n = 5, λ = (6, 6, 4, 2) and μ = (3, 1). The weight of S is wt^{∗}(S) = x_{0}^{4}x_{1}^{2}x_{2}^{5}x_{3}^{1}y_{0}y_{1}^{2}. The head of S is indicated by the red cell.

We denote by LHT_{n}^{∗}(λ/μ) the set of extended n-lecture hall tableaux of shape λ/μ. See Figure 11 for an example, where the blue circle will be explained later.

A marked semistandard n-content tableau is a marked tableau T such that the tableau obtained from T by deleting its marks is a semistandard n-content tableau. See Figure 12 for an example, where the red circle will be explained later. We denote by SSCT_{n}^{∗}(λ/μ) the set of marked semistandard n-content tableaux of shape λ/μ. From the definition one can easily see that

(22)  S_{λ/μ}^{n}(|x| + y) = ∑_{T ∈SSCT_{n}^{∗}(λ/μ)} wt^{∗}(T).

Observe that if T is an extended n-lecture hall tableau, then the marks are weakly decreasing in each row and each column, and for all i ∈ ℕ ∪ {∞} the values with mark i form a semistandard n-content tableau. Therefore, if we restrict T to the cells whose marks are not ∞, we obtain an n-lecture hall tableau, which implies that

(23) ∑_{T ∈LHT_{n}^{∗}(λ/μ)} wt^{∗}(T) = ∑_{ν} ( ∑_{T ∈LHT_{n}(λ/ν)} x^{⌊T ⌋} ∑_{T ∈SSCT_{n}(ν/μ)} y^{T} ) = ∑_{ν} L_{λ/ν}^{n}(x)S_{ν/μ}^{n}(y).

By (22) and (23), Theorem 1.6 can be restated as follows.

Theorem 4.1. We have

∑_{T ∈LHT_{n}^{∗}(λ/μ)} wt^{∗}(T) = ∑_{T ∈SSCT_{n}^{∗}(λ/μ)} wt^{∗}(T).

\begin{matrix}0_{5} \\ 3_{3} \\ 2_{3} \\ 4_{2} \\ 7_{1} \\ 7_{2} \\ 1_{2} \\ 6_{0} \\ 6_{1} \\ 5_{0} \\ 4_{0} \\ 2_{∞} \\ 5_{2} \\ 6_{1} \\ 5_{1} \\ 5_{0} \\ 3_{1} \\ 3_{1} \\ 2_{3} \\ 1_{2} \\ 4_{0} \\ 4_{1} \\ 4_{0} \\ 2_{1} \\ 4_{0} \\ 3_{1} \\ 2_{1} \\ 1_{1} \\ 1_{0} \\ 1_{2} \\ P = \\ 0_{5} \\ 3_{3} \\ 2_{3} \\ 4_{2} \\ 7_{1} \\ 7_{2} \\ 7_{1} \\ 6_{0} \\ 6_{1} \\ 5_{0} \\ 4_{0} \\ 2_{∞} \\ 5_{2} \\ 5_{0} \\ 5_{1} \\ 5_{0} \\ 3_{1} \\ 3_{1} \\ 2_{3} \\ 1_{2} \\ 3_{1} \\ 3_{0} \\ 2_{0} \\ 2_{1} \\ 4_{0} \\ 3_{1} \\ 2_{1} \\ 1_{1} \\ 1_{2} \\ 1_{2} \\ Q = \end{matrix}

Figure 13. If u = (2, 3) and v = (5, 5), then ϕ_{vjdt}(P, u) = (Q, v) and ϕ_{mjdt}(Q, v) = (P, u). In each diagram the positions that the active cell visits are enclosed by the thick polygon.

We will construct a weight-preserving bijection between LHT_{n}^{∗}(λ/ν) and SSCT_{n}^{∗}(λ/μ). The basic idea is to sort the values of L ∈ LHT_{n}^{∗}(λ/μ) using a variation of “jeu de taquin” according to a certain order of the cells in λ/μ depending on L itself. Our algorithms are inspired by those due to Krattenthaler [14].

Algorithm 4.2 (Value-jeu de taquin). The value-jdt algorithm is described as follows. Notation: ϕ_{vjdt}(P, u) = (Q, v). Input: A pair (P, u) of a marked tableau P of shape λ/μ and a cell u ∈ λ/μ. Output: A pair (Q, v) of a marked tableau Q of shape λ/μ and a cell v ∈ λ/μ.

Step 1: Set Q = P and v = u. We call v the active cell.

Step 2: Let (i, j) be the coordinate of the active cell v. Let a_{r} = Q(i, j), b_{s} = Q(i, j + 1), and c_{t} = Q(i + 1, j). If (i, j + 1) ∉ λ/μ (resp. (i + 1, j) ∉ λ/μ), then set b_{s} = (−1)_{0} (resp. c_{t} = (−1)_{0}). If a ≥ b and a > c, then stop the process and return (Q, v) as the output. Otherwise, there are two cases.

• If b − 1 > c, then set Q(i, j) = (b − 1)_{s} and Q(i, j + 1) = a_{r} as shown below, where the active cell v is the cell containing a_{r}. Set v = (i, j + 1) and repeat Step 2.

\begin{matrix}a_{r} \\ b_{s} \\ c_{t} \\ → \\ (b − 1)_{s} \\ a_{r} \\ c_{t} \end{matrix}

• If c + 1 ≥ b, then set Q(i, j) = (c + 1)_{t} and Q(i + 1, j) = a_{r} as shown below, the active cell v is the cell containing a_{r}. Set v = (i + 1, j) and repeat Step 2.

\begin{matrix}a_{r} \\ b_{s} \\ c_{t} \\ → \\ (c + 1)_{t} \\ b_{s} \\ a_{r} \end{matrix}

See Figure 13 for an example of the value-jdt algorithm.

Algorithm 4.3 (Mark-jeu de taquin). The mark-jdt algorithm is described as follows. Notation: ϕ_{mjdt}(Q, v) = (P, u). Input: A pair (Q, v) of a marked tableau Q of shape λ/μ and a cell v ∈ λ/μ.

NW NW SE NW SE

Figure 14. The northwest corners are the cells with an “NW” and the southeast corners are the cells with an “SE”.

Output: A pair (P, u) of a marked tableau P of shape λ/μ and a cell u ∈ λ/μ. Step 1: Set P = Q and u = v. We call u the active cell. Step 2: Let (i, j) be the coordinate of the active cell u. Let a_{r} = P (i, j), b_{s} = P (i, j − 1), and c_{t} = P (i − 1, j). If (i, j − 1) ∉ λ/μ (resp. (i − 1, j) ∉ λ/μ), then set b_{s} = ∞_{∞} (resp. c_{t} = ∞_{∞}). If r ≤ s and r ≤ t, then stop the process and return (P, u) as the output. Otherwise, there are two cases.

• If t < r ≤ s, or s, t < r and b ≥ c − 1, then set P (i, j) = (c − 1)_{t} and P (i − 1, j) = a_{r} as shown below, where the active cell u is the cell containing a_{r}. Set u = (i − 1, j) and repeat Step 2.

\begin{matrix}c_{t} \\ a_{r} \\ b_{s} \\ → \\ a_{r} \\ (c − 1)_{t} \\ b_{s} \end{matrix}

• If s < r ≤ t, or s, t < r and c > b + 1, then set P (i, j) = (b + 1)_{s} and P (i, j − 1) = a_{r} as shown below, where the active cell u is the cell containing a_{r}. Set u = (i, j − 1) and repeat Step 2.

\begin{matrix}c_{t} \\ a_{r} \\ b_{s} \\ → \\ c_{t} \\ (b + 1)_{s} \\ a_{r} \end{matrix}

See Figure 13 for an example of the value-jdt algorithm.

Let λ be a partition. An outer corner of λ is a cell u ∉ λ such that λ∪{u} is a partition. An inner corner of λ is a cell u ∈ λ such that λ \ {u} is a partition. For a skew shape λ/μ, a northwest corner of λ/μ is a cell in λ/μ that is an outer corner of μ and a southeast corner of λ/μ is a cell in λ/μ that is an inner corner of λ. See Figure 14 for an example.

Definition 4.4. Let α be a skew shape and L ∈ LHT_{n}^{∗}(α). Suppose that r is the smallest mark and a is the smallest value with mark r in L. Then the tail of L, denoted tail(L), is defined to be the rightmost cell (i, j) ∈ α with L(i, j) = a_{r}. See Figure 11 for an example.

Note that for distinct cells (i, j), (i′, j′) ∈ λ/μ, if L(i, j) = L(i′, j′) = a_{r}, then the fact that L is an element in LHT_{n}^{∗}(λ/μ) ensures that j ≠ j′. Thus the tail of L ∈ LHT_{n}^{∗}(λ/μ) is well-defined. It is clear from the definition that the tail of L is a southeast corner of λ/μ.

Definition 4.5. Let β be a skew shape and S ∈ SSCT_{n}^{∗}(β). Suppose that r is the largest mark and a is the largest value with mark r in S. Then the head of S, denoted head(S), is defined to be the leftmost cell (i, j) ∈ β with S(i, j) = a_{r}. See Figure 12 for an example.

\begin{matrix}T_{i} = \\ α_{i} \\ β_{i} \\ u_{i−1} \\ v_{i} \end{matrix}

Figure 15. A typical diagram with T_{i}, α_{i}, β_{i}, u_{i−1}, and v_{i}. The border between α_{i} and β_{i} is shown with a thick path. The blue circle represents u_{i−1} and the red circle represents v_{i}. The dashed path represents the movement of the active cell in the process of ϕ_{vjdt}(T_{i−1}, u_{i−1}) = (T_{i}, v_{i}).

By a similar argument as before, one can check that if S ∈ SSCT_{n}^{∗}(β), then head(S) is well-defined. Note, however, that head(S) is not necessarily a (northwest or southeast) corner of β.

We are now ready to define a map sending an extended n-lecture hall tableau L ∈ LHT_{n}^{∗}(λ/μ) to a marked semistandard n-content tableau S ∈ SSCT_{n}^{∗}(λ/μ). Recall from the definition that in L the marks are weakly decreasing along each row and column but the values are not sorted. In S, on the contrary, the values are weakly decreasing along each row and strictly decreasing along each column but the marks are not sorted. Our approach is, therefore, to sort the values of L in order to obtain S, and to sort the marks of S in order to obtain L. The two sorting algorithms are described below. See Figure 15 for an illustration of a typical situation and Figure 16 for a concrete example of these algorithms.

Algorithm 4.6 (Value-sorting). The value-sorting algorithm is described as follows. Notation: ϕ_{vsort}(L) = S. Input: An extended n-lecture hall tableau L of shape λ/μ. Output: A marked semistandard n-content tableau S of shape λ/μ. Step 1: Set T_{0} = L, α_{0} = λ/μ, β_{0} = ∅, and u_{0} = tail(T_{0}). Step 2: For i = 1, 2, …, |λ/μ|, define α_{i}, β_{i}, T_{i}, u_{i}, and v_{i} recursively by

(T_{i}, v_{i}) = ϕ_{vjdt}(T_{i−1}, u_{i−1}),
α_{i} = α_{i−1} \ {u_{i−1}},
β_{i} = β_{i−1} ∪ {u_{i−1}},
u_{i} = tail(T_{i}|_{α_{i}}).

Step 3: Return S = T_{|λ/μ|} as the output.

Algorithm 4.7 (Mark-sorting). The mark-sorting algorithm is described as follows. Notation: ϕ_{msort}(S) = L.

\begin{matrix}L = \\ 1_{∞} \\ 3_{1} \\ 4_{0} \\ 3_{1} \\ 2_{1} \\ 2_{1} \\ 4_{0} \\ → \\ 1_{∞} \\ 3_{1} \\ 4_{0} \\ 3_{1} \\ 2_{1} \\ 2_{1} \\ 4_{0} \\ → \\ 1_{∞} \\ 3_{1} \\ 4_{0} \\ 3_{1} \\ 2_{1} \\ 2_{1} \\ 4_{0} \\ → \\ 1_{∞} \\ 3_{1} \\ 4_{0} \\ 3_{1} \\ 2_{1} \\ 2_{1} \\ 4_{0} \\ ↓ \\ 1_{∞} \\ 3_{1} \\ 4_{0} \\ 3_{1} \\ 2_{1} \\ 2_{1} \\ 4_{0} \\ ← \\ 1_{∞} \\ 3_{0} \\ 3_{1} \\ 3_{1} \\ 2_{1} \\ 2_{1} \\ 4_{0} \\ ← \\ 1_{∞} \\ 3_{0} \\ 3_{1} \\ 5_{0} \\ 2_{1} \\ 2_{1} \\ 3_{1} \\ ← \\ 3_{1} \\ 3_{0} \\ 3_{1} \\ 5_{0} \\ 1_{1} \\ 1_{∞} \\ 3_{1} \\ S = \end{matrix}

Figure 16. The value-sorting algorithm applied to L ∈ LHT_{n}^{∗}(λ/μ) returns S ∈ SSCT_{n}^{∗}(λ/μ), where n = 7, λ = (4, 3, 1) and μ = (1). The marksorting algorithm is the reverse process. Each diagram represents T_{i}. The border between α_{i} and β_{i} is drawn by a thick path. The blue circle indicates u_{i} = tail(T_{i}|_{α_{i}}) and the red circle indicates v_{i} = head(T_{i}|_{β_{i}}).

Input: A marked semistandard n-content tableau S of shape λ/μ. Output: An extended n-lecture hall tableau L of shape λ/μ.

Step 1: Set T_{|λ/μ|} = S, α_{|λ/μ|} = ∅, β_{|λ/μ|} = λ/μ, and v_{|λ/μ|} = head(T_{|λ/μ|}).

Step 2: For i = |λ/μ|−1, |λ/μ|−2, …, 0, define α_{i}, β_{i}, T_{i}, u_{i}, and v_{i} recursively by

(T_{i}, u_{i}) = ϕ_{mjdt}(T_{i+1}, v_{i+1}),
α_{i} = α_{i+1} ∪ {u_{i+1}},
β_{i} = β_{i+1} \ {u_{i+1}},
v_{i} = head(T_{i}|_{β_{i}}).

Step 3: Return L = T_{0} as the output.

In order to show that the above algorithms are inverse to each other, we need the following two lemmas.

Lemma 4.8. Let L ∈ LHT_{n}^{∗}(λ/μ). Suppose that α_{i}, β_{i}, T_{i}, u_{i}, and v_{i}, 0 ≤ i ≤ |λ/μ|, are given as in Algorithm 4.6. Then, for i = 1, 2, …, |λ/μ|, the following properties hold:

(1) T_{i}|_{α_{i}} ∈ LHT_{n}^{∗}(α_{i}) and T_{i}|_{β_{i}} ∈ SSCT_{n}^{∗}(β_{i}). In particular, T_{|λ/μ|} ∈ SSCT_{n}^{∗}(λ/μ).

(2) head(T_{i}|_{β_{i}}) = v_{i}.

(3) ϕ_{mjdt}(T_{i}, v_{i}) = (T_{i−1}, u_{i−1}).

Proof. (1): We prove this for i = 0, 1, …, |λ/μ| by induction. Since T_{0}|_{α_{0}} = L and T_{0}|_{β_{0}} = ∅, it is true for i = 0. Let 1 ≤ i ≤ |λ/μ| and suppose that (1) is true for i − 1. Since T_{i−1}|_{α_{i−1}} ∈ LHT_{n}^{∗}(α_{i−1}), we have that u_{i−1} = tail(T_{i−1}|_{α_{i−1}}) is a southeast corner of α_{i−1}. Hence, α_{i} = α_{i−1} \ {u_{i−1}} and β_{i} = β_{i−1} ∪ {u_{i−1}} are skew shapes. When we compute (T_{i}, v_{i}) = ϕ_{vjdt}(T_{i−1}, u_{i−1}), the value-jdt algorithm does not modify the cells in α_{i}, which implies that T_{i}|_{α_{i}} = T_{i−1}|_{α_{i}} = L|_{α_{i}} ∈ LHT_{n}^{∗}(α_{i}) and ϕ_{vjdt}(T_{i−1}|_{β_{i}}, u_{i−1}) = (T_{i}|_{β_{i}}, v_{i}). It is

\begin{matrix}∗ \\ ∗ \\ c_{y} \\ b_{x} \\ ∗ \\ (c + 1)_{y} \\ ∗ \\ b_{x} \\ c_{y} \\ ∗ \\ ∗ \\ b_{x} \end{matrix}

Figure 17. The restrictions of T_{i−1} (on the left), T_{i} (in the middle), and T_{i+1} (on the right) to the cells (g, h − 1), (g, h), (g + 1, h − 1), (g + 1, h).

not hard to check that in the process of ϕ_{vjdt}(T_{i−1}|_{β_{i}}, u_{i−1}) to obtain T_{i}|_{β_{i}}, the values of the cells in β_{i} are weakly decreasing in each row and strictly decreasing in each column with only possible exceptions between the active cell and the cell to the right of it and the cell below it. When the process stops these two possible exceptions are resolved and we obtain T_{i}|_{β_{i}} ∈ SSCT_{n}^{∗}(β_{i}) as desired.

(2): It is clear from the construction that, if r is the largest mark and a is the largest value with mark r in T_{i}|_{β_{i}}, then T_{i}(v_{i}) = a_{r}. If v_{i} is the only cell in β_{i} with this property, then we have head(T_{i}|_{β_{i}}) = v_{i}. Otherwise, we must show that v_{i} is the leftmost cell with this property. To this end suppose that T_{i−1}(u_{i−1}) = T_{i}(u_{i}) = a_{r}, u_{i−1} = (k, l), u_{i} = (k′, l′), and v_{i} = (p, q), v_{i+1} = (p′, q′). Then it is sufficient to show that q′ < q. Since T_{i−1}|_{α_{i−1}} ∈ LHT_{n}^{∗}(α_{i−1}) and u_{i−1} = head(T_{i−1}|_{α_{i−1}}), we have k′ ≥ k and j′ < j.

Let u_{i−1} = w_{0}, w_{1}, w_{2}, …, w_{d} = v_{i} be the sequence of positions of the active cell in the construction of ϕ_{vjdt}(T_{i−1}, u_{i−1}) = (T_{i}, v_{i}). We claim that, when we compute ϕ_{vjdt}(T_{i}, v_{i}), the active cell never enters the position w_{t} if w_{t+1} is south of w_{t}, for 0 ≤ t < d.

Suppose that the claim is false. Then we can find the smallest integer m such that w_{m} = (g, h), w_{m+1} = (g+1, h), and the active cell enters w_{m}. Considering the relative positions of u_{i−1} and u_{i}, one can check that the active cell must enter w_{m} from the east. Now we focus on the restrictions of T_{i−1}, T_{i}, and T_{i+1} to the cells (g, h−1), (g, h), (g+1, h−1), (g+1, h) as in Figure 17. Let T_{i−1}(g+1, h−1) = b_{x} and T_{i−1}(g+1, h) = c_{y}. Since T_{i−1}|_{β_{i−1}} ∈ SSCT_{n}^{∗}(β_{i−1}), we have b ≥ c. Considering the positions of the active cell in the process of ϕ_{vjdt}(T_{i−1}, u_{i−1}) and ϕ_{vjdt}(T_{i}, u_{i}), we obtain T_{i}(g+1, h−1) = b_{x}, T_{i}(g, h) = (c+1)_{y}, T_{i+1}(g+1, h−1) = b_{x}, and T_{i+1}(g, h − 1) = c_{y}. Since T_{i+1}|_{β_{i+1}} ∈ SSCT_{n}^{∗}(β_{i+1}), we have b < c, which is a contradiction to the above fact that b ≥ c. Therefore, the claim is true.

By the above claim, if q′ ≥ q, then the active cell in the process of ϕ_{vjdt}(T_{i}, u_{i}) must move from (z, q − 1) to (z, q) for some z ≥ p. Suppose that z = p. Let T_{i}(p + 1, q − 1) = c_{t}. Since T_{i}(p, q) = a_{r}, the fact that the active cell moved from (p, q − 1) to (p, q) implies that a − 1 > c. However, this means that, when the active cell was in (p, q − 1), its value is at most the value of the cell to the right and greater than the value of the cell below, and the value-jdt algorithm must stop at this stage, which is a contradiction. Therefore, we must have z > p. In this case, since T_{i+1}|_{β_{i+1}} ∈ SSCT_{n}^{∗}(β_{i+1}) and v_{i+1} is strictly below and weakly to the right of v_{i}, the value of T_{i+1}(v_{i+1}) is less than the value of T_{i+1}(v_{i}), which is a contradiction. Therefore, we must have q′ < q, which completes the proof of (2).

(3): By the fact that T_{i−1}|_{β_{i−1}} ∈ SSCT_{n}^{∗}(β_{i−1}) and T_{i−1}|_{β_{i−1}} ∈ SSCT_{n}^{∗}(β_{i}), it is clear that the reverse process of ϕ_{vjdt}(T_{i−1}, u_{i−1}) is given by the mark-jdt algorithm. We only need to check that the process of ϕ_{mjdt}(T_{i}, v_{i}) stops when the active cell reaches the cell u_{i−1}. Let r be the largest mark and a the largest value with mark in T_{i}|_{β_{i}}. Since v_{i} = head(T_{i}|_{β_{i}}), we have T_{i}(v_{i}) = a_{r}, and v_{i} is the leftmost cell with this property. Therefore, the movement of the active cell in the process of ϕ_{mjdt}(T_{i}, v_{i}) continues until the active cell reaches a northwest corner of β_{i}, which is u_{i−1}. If the active cell is at u_{i−1}, then the fact that the mark of every cell in α_{i} is at least r implies that the process of ϕ_{mjdt}(T_{i}, v_{i}) stops. □

Lemma 4.9. Let S ∈ SSCT_{n}^{∗}(λ/μ). Suppose that α_{i}, β_{i}, T_{i}, u_{i}, and v_{i} are given as in Algorithm 4.7. Then, for i = 0, 1, 2, …, |λ/μ| − 1, the following properties hold:

(1) T_{i}|_{α_{i}} ∈ LHT_{n}^{∗}(α_{i}) and T_{i}|_{β_{i}} ∈ SSCT_{n}^{∗}(β_{i}). In particular, T_{0} ∈ LHT_{n}^{∗}(λ/μ).

(2) tail(T_{i}|_{α_{i}}) = u_{i}.

(3) ϕ_{vjdt}(T_{i}, u_{i}) = (T_{i+1}, v_{i+1}).

Proof. This lemma can be proved by arguments similar to those in the proof of Lemma 4.8. We omit the proof. □

We now give a bijective proof of Theorem 4.1.

Theorem 4.10. The map

ϕ_{vsort} : LHT_{n}^{∗}(λ/μ) → SSCT_{n}^{∗}(λ/μ)

is a weight-preserving bijection whose inverse is

ϕ_{msort} : SSCT_{n}^{∗}(λ/μ) → LHT_{n}^{∗}(λ/μ).

Proof. Lemmas 4.8 and 4.9 imply that the two maps ϕ_{vsort} and ϕ_{msort} are inverses of each other. Suppose ϕ_{vsort}(L) = S. In the process of the value-sorting algorithm, the marks and the values with mark ∞ are never changed. Therefore wt^{∗}(L) = wt^{∗}(S). □

Remark 4.11. The bijection allows us to generate a random bounded lecture hall tableau of a given partition shape using Krattenthaler’s random generation of a semistandard Young tableau. It will be interesting to extend this random generation to skew shapes. In [8] a different algorithm is established using a Markov chain on bounded lecture hall tableaux and coupling from the past.

5. A connection between SSCT and SYT

In this section, we use the weight-preserving bijection ϕ_{vsort} : LHT_{n}^{∗}(λ/μ) → SSCT_{n}^{∗}(λ/μ) and its inverse ϕ_{msort} : SSCT_{n}^{∗}(λ/μ) → LHT_{n}^{∗}(λ/μ) to find a connection between |SSCT_{n}(λ/μ)| and |SYT(λ/μ)|.

Recall the sets SYT(λ/μ), SSYT_{n}(λ/μ), LHT_{n}(λ/μ), and SSCT_{n}(λ/μ) defined in the introduction. We also need the following definitions.

A tableau T of shape λ/μ is called standard if every integer 1 ≤ i ≤ |λ/μ| appears exactly once in T. The set of standard tableaux of shape λ/μ is denoted by ST(λ/μ). An n-content tableau of shape λ/μ is a tableau T of shape λ/μ such that 0 ≤ T (i, j) < n−i+j for all (i, j) ∈ λ/μ. The set of n-content tableaux of shape λ/μ is denoted by CT_{n}(λ/μ). A hook tabloid of shape λ is a map H : λ → ℤ satisfying − leg(i, j) ≤ H(i, j) ≤ arm(i, j) for all (i, j) ∈ λ, where leg(i, j) = λ′_{j} − i and arm(i, j) = λ_{i} − j. We denote by HT(λ) the set of hook tabloids of shape λ.

Let us now consider the map ϕ_{vsort} : LHT_{n}^{∗}(λ/μ) → SSCT_{n}^{∗}(λ/μ) restricted to the following sets:

X_{n}(λ/μ) = {L ∈ LHT_{n}^{∗}(λ/μ) : wt^{∗}(L) = x_{1} ⋯ x_{|λ/μ|}},
Y_{n}(λ/μ) = {T ∈ SSCT_{n}^{∗}(λ/μ) : wt^{∗}(T) = x_{1} ⋯ x_{|λ/μ|}}.

Since ϕ_{vsort} is a weight-preserving bijection, we obtain the induced bijection

ϕ_{vsort} : X_{n}(λ/μ) → Y_{n}(λ/μ).

We may naturally identify L ∈ X_{n}(λ/μ) with the pair (A, R) of tableaux of shape λ/μ: if L(i, j) = a_{r} then A(i, j) = a and R(i, j) = r. Then, by the condition on L, we have A ∈ CT_{n}(λ/μ) and R ∈ SYT(λ/μ). This allows us to identify X_{n}(λ/μ) with CT_{n}(λ/μ) × SYT(λ/μ). Similarly, we can identify Y_{n}(λ/μ) with SSCT_{n}(λ/μ) × ST(λ/μ). Using this identification we can consider ϕ_{vsort} as a bijection between these sets:

(24)  ϕ_{vsort} : CT_{n}(λ/μ) × SYT(λ/μ) → SSCT_{n}(λ/μ) × ST(λ/μ).

Therefore we obtain the following corollary, which is a restatement of Proposition 1.2.

Corollary 5.1. For any skew shape λ/μ, we have

\frac{|SSCT_{n}(λ/μ)|}{∏_{x∈λ/μ}(n + c(x))} = \frac{|SYT(λ/μ)|}{|λ/μ|!},

which means that the probability that a random T ∈ CT_{n}(λ/μ) is semistandard is equal to the probability that a random T ∈ ST(λ/μ) is a standard Young tableau.

It is possible to understand the probabilistic description in Corollary 5.1 using the map (24). To this end we note that each element (A, B) ∈ CT_{n}(λ/μ) × SYT(λ/μ) is a fixed point of ϕ_{vsort}, i.e., ϕ_{vsort}(A, B) = (A, B), if and only if A ∈ SSCT_{n}(λ/μ). Similarly, each element (A, B) ∈ SSCT_{n}(λ/μ) × ST(λ/μ) is a fixed point of the inverse map ϕ_{msort} = ϕ_{vsort}^{−1} if and only if B ∈ SYT(λ/μ). The probability that a random A ∈ CT_{n}(λ/μ) is an element in SSCT_{n}(λ/μ) is clearly equal to the probability that a random pair (A, B) ∈ CT_{n}(λ/μ) × SYT(λ/μ) satisfies A ∈ SSCT_{n}(λ/μ). In other words, this is the probability that a random pair (A, B) ∈ CT_{n}(λ/μ) × SYT(λ/μ) is a fixed point of ϕ_{vsort}. By the same argument, we obtain that the probability that a random B ∈ ST(λ/μ) is an element of SYT(λ/μ) is equal to the probability that a random pair (A, B) ∈ SSCT_{n}(λ/μ) × ST(λ/μ) is a fixed point of the map ϕ_{vsort}^{−1}. Since ϕ_{vsort} and ϕ_{vsort}^{−1} are inverses of each other with the same set of fixed points, we obtain that the two probabilities that we consider are equal.

We now consider the map (24) for the case μ = ∅. Since SSCT_{n}(λ) = SSYT_{n}(λ), we have the following bijection:

(25)  ϕ_{vsort} : CT_{n}(λ) × SYT(λ) → SSYT_{n}(λ) × ST(λ).

Recall the two bijections due to Novelli, Pak and Stoyanovskii, and to Krattenthaler.

CT_{n}(λ) × SYT(λ)

SSYT_{n}(λ) × ST(λ)

SSYT_{n}(λ) × HT(λ) × SYT(λ)

ϕ_{vsort}

ϕ_{K}

ϕ_{NP S}

Figure 18. Three maps between three objects.

Theorem 5.2 (Novelli, Pak, Stoyanovskii). For any partition λ, there is a bijection

ϕ_{NP S} : ST(λ) → SYT(λ) × HT(λ).

Theorem 5.3 (Krattenthaler). For any partition λ, there is a bijection

ϕ_{K} : CT_{n}(λ) → SSYT_{n}(λ) × HT(λ).

Note that ϕ_{NP S} naturally induces a bijection

ϕ_{NP S} : SSYT_{n}(λ) × ST(λ) → SSYT_{n}(λ) × HT(λ) × SYT(λ)

by fixing the first component. Similarly ϕ_{K} induces a bijection

ϕ_{K} : CT_{n}(λ) × SYT(λ) → SSYT_{n}(λ) × HT(λ) × SYT(λ).

Then the three maps ϕ_{vsort}, ϕ_{K}, and ϕ_{NP S} are bijections between the three sets CT_{n}(λ) × SYT(λ), SSYT_{n}(λ)×ST(λ), and SSYT_{n}(λ)×HT(λ)×SYT(λ), see Figure 18. These maps are not directly related. It might be interesting to find any connection between these maps.

6. Final remarks

Stanley [24] showed that semistandard Young tableaux and standard Young tableaux fit together nicely in the framework of the P -partition theory, see also [25, Chapter 3] and [26, Chapter 7]. Lecture hall tableaux are also a special case of lecture hall P -partitions introduced by Brändén and Leander [7]. They found a connection between generating functions for the bounded lecture hall P -partitions and colored linear extensions of P. It will be interesting to compare our results with theirs.

Problem 6.1. Investigate bounded lecture hall tableaux using the results of Brändén and Leander [7].

Krattenthaler’s map [14] in fact gives a bijective proof of the following q-analog of (2), also due to Stanley [23]:

∑_{T ∈SSYT_{n}(λ)} q^{|T |} = q^{∑_{i≥1}(i−1)λ_{i}} ∏_{(i,j)∈λ} \frac{[n + c(i, j)]_{q}}{[h(i, j)]_{q}} ,

where [k]_{q} = 1 + q + q^{2} + ⋯ + q^{k−1}. If we only look at the values and ignore the marks, then our jeu de taquin slides in Algorithms 4.2 and 4.3 are essentially the same as those in [14]. Recall that during these algorithms values are changing. Krattenthaler carefully designed his bijection so that these value changes are consistent with the value changes in hook tabloids. Our bijection, on the contrary, does not have hook tabloids, which makes it difficult to follow the change of values. If we can keep track of all the value changes, then it may be possible to find a refinement of Theorem 4.1.

Problem 6.2. Find a q-analogue of Theorem 4.1.

For a partition λ = (λ_{1}, …, λ_{ℓ}) with distinct parts, the shifted Young diagram of λ is an array of squares in which the ith row has λ_{i} squares and is shifted to the right by i − 1 units. Standard Young tableaux and semistandard Young tableaux of a shifted shape can then be defined in a similar fashion. They also enjoy nice enumerative properties as in the case of a usual shape.

Problem 6.3. Find a formula for the number of bounded n-lecture hall tableaux of a given shifted shape.

Note that we cannot expect a nice product formula for this problem. For example, the number of 17-bounded 14-lecture hall tableaux of shape (2, 1) has the prime factorization 2 · 3 · 7 · 17 · 3331.

Let δ_{n} = (n − 1, n − 2, …, 1, 0) and

d_{λ,μ}^{(n)} = det (\binom{λ_{i} + n − i}{μ_{j} + n − j})_{1≤i,j≤n} ,

which is by Proposition 1.2 equal to |SSCT_{n}(λ/μ)|. As mentioned in the introduction, Lascoux [15] used (4) to compute the Chern classes of the exterior square ⋀^{2} E and symmetric square Sym^{2} E of a vector bundle E. To be more precise, let c(E) = ∏_{i=1}^{n}(1 + y_{i}) be the total Chern class of E. Lascoux showed that

(26)  c (⋀^{2} E) = ∏_{1≤i<j≤n}(1 + y_{i} + y_{j}) = ∑_{μ⊂δ_{n}} 2^{|μ|−\binom{n}{2}}d_{δ_{n},μ}^{(n)}s_{μ}(y_{1}, …, y_{n}),
(27)  c(Sym^{2} E) = ∏_{1≤i≤j≤n}(1 + y_{i} + y_{j}) = ∑_{λ⊂δ_{n+1}} 2^{|λ|−\binom{n}{2}}d_{δ_{n+1},λ}^{(n)}s_{λ}(y_{1}, …, y_{n}).

Billey, Rhoades, and Tewari [6, Corollary 4.3] found the following manifestly integral and positive formulas for the Schur expansions of c (⋀^{2} E) and c(Sym^{2} E):

(28)  ∏_{1≤i<j≤n}(1 + y_{i} + y_{j}) = ∑_{μ⊂δ_{n}} r_{μ}^{(n)}s_{μ}(y_{1}, …, y_{n}),
(29)  ∏_{1≤i≤j≤n}(1 + y_{i} + y_{j}) = ∑_{λ⊂δ_{n+1}} _{∑_{μ⊆λ∩δ_{n}} λ/μ a vertical strip}2^{|λ/μ|}r_{μ}^{(n)}s_{λ}(y_{1}, …, y_{n}),

where a vertical strip is a skew shape in which every row has at most one cell and r_{μ}^{(n)} is the number of tableaux of shape μ such that the entries are strictly decreasing along rows and weakly decreasing down columns, and every entry in row i is in {1, 2, …, n − i}.

Comparing the Schur coefficients in (26), (27), (28), and (29), and using the fact d_{λ/μ}^{(n)} = |SSCT_{n}(λ/μ)|, we obtain the following proposition.

Proposition 6.4. For μ ⊆ δ_{n} and λ ⊆ δ_{n+1}, we have

|SSCT_{n}(δ_{n}/μ)| = 2^{|δ_{n}/μ|}r_{μ}^{(n)},
|SSCT_{n}(δ_{n+1}/λ)| = _{∑_{μ⊆λ∩δ_{n}} λ/μ a vertical strip}2^{|δ_{n}/μ|}r_{μ}^{(n)}.

The objects in SSCT_{n}(δ_{n}/μ) and those counting r_{μ}^{(n)} have somewhat similar conditions on their entries but their shapes are complementary: δ_{n}/μ and μ. Understanding the connection between these two objects will be very interesting.

Problem 6.5. Find a bijective proof of Proposition 6.4.

In a forthcoming paper [8], the first author, Keating and Nicoletti show that lecture hall tableaux are in bijection with a certain dimer model on a graph whose faces are hexagons and octagons. Moreover they show that bounded lecture hall tableaux of a “large” shape exhibit the arctic curve phenomenon.

References

[1] R. Adin and Y. Roichman. Standard Young tableaux. In Handbook of enumerative combinatorics, Discrete Math. Appl. (Boca Raton), pages 895–974. CRC Press, Boca Raton, FL, 2015.

[2] A. C. Aitken. The monomial expansion of determinantal symmetric functions. Proc. Royal Soc. Edinburgh (A), 61:300–310, 1943.

[3] M. Beck, B. Braun, M. Köppe, C. D. Savage and Z. Zafeirakopoulos. s-Lecture hall partitions, selfreciprocal polynomials, and Gorenstein cones. Ramanujan J., 36(1-2):123–147, 2015.

[4] M. Beck, B. Braun, M. Köppe, C. D. Savage and Z. Zafeirakopoulos. Generating functions and triangulations for lecture hall cones. SIAM J. Discrete Math., 30:1470–1479, 2016.

[5] M. Beck and C. D. Savage. personal communication (2009).

[6] S. C. Billey, B. Rhoades and V. Tewari. Boolean product polynomials, Schur positivity, and Chern plethysm. Int. Math. Res. Notices, Article rnz261, 2019.

[7] P. Brändén and M. Leander, Lecture hall P -partitions. J. Combin., 11:391–412, 2020.

[8] S. Corteel, D. Keating and M. Nicoletti. Arctic curves for bounded lecture hall tableaux. Preprint,

   https://arxiv.org/abs/1905.02881.

[9] S. Corteel and J. S. Kim. Lecture hall tableaux. To appear in Adv. Math.,

   https://arxiv.org/abs/1804.02489.

[10] S. Corteel, S. Lee and C. D. Savage. Enumeration of sequences constrained by the ratio of consecutive parts. Sém. Lothar. Combin., 54A:Art. B54Aa, 12 pp. (electronic), 2005/07.

[11] J. S. Frame, G. de B. Robinson and R. M. Thrall. The hook graphs of the symmetric groups. Canadian J. Math., 6:316–324, 1954.

[12] I. M. Gessel and X. G. Viennot. Binomial determinants, paths, and hook-length formulas. Adv. Math., 58:300–321, 1985.

[13] A. N. Kirillov and T. Scrimshaw. Hook-content formula using excited Young diagrams. Preprint,

   https://arxiv.org/abs/1904.00371.

[14] C. Krattenthaler. Another involution principle-free bijective proof of Stanley’s hook-content formula. J. Combin. Theory Ser. A, 88(1):66–92, 1999.

[15] A. Lascoux. Classes de Chern d’un produit tensoriel. C. R. Acad. Sci. Paris Sér. A-B, 286(8):385–387, 1978.

[16] F. Liu and R. P. Stanley. The lecture hall parallelepiped. Ann. Combin., 18:473–488, 2014.

[17] I. G. Macdonald. Symmetric functions and Hall polynomials. Second edition. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, 1995.

[18] A. Morales, G. Panova and I. Pak. Hook formulas for skew shapes I. q-analogues and bijections. J. Combin. Theory Ser. A, 154:350–405, 2018.

[19] H. Naruse. Schubert calculus and hook formula. Talk at 73rd Sém. Lothar. Combin., Strobl, Austria,

   2014; available at http://tinyurl.com/z6paqzu.

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

[21] M. C. Olsen, Hilbert bases and lecture hall partitions. Ramanujan J., 47(3):509–531, 2018.

[22] C. D. Savage. The mathematics of lecture hall partitions. J. Combin. Theory Ser. A, 144:443–475, 2016.

[23] R. P. Stanley. Theory and application of plane partitions. I, II. Studies in Appl. Math., 50:167–188; ibid. 50:259–279, 1971.

[24] R. P. Stanley. Ordered structures and partitions. Memoirs of the American Mathematical Society, no. 119. American Mathematical Society, Providence, R.I., 1972.

[25] R. P. Stanley. Enumerative combinatorics. Vol. 1. Second edition. Cambridge University Press, 2011.

[26] R. P. Stanley. Enumerative combinatorics. Vol. 2. Cambridge University Press, 1999.

University of California, Berkeley, United States

  Email address: corteel@berkeley.edu

Sungkyunkwan University, Suwon, South Korea

  Email address: jangsookim@skku.edu