nLab semistandard Young tableau

Redirected from "standard Young tableau".
Contents

Context

Combinatorics

Representation theory

Contents

Idea

In combinatorics a (semi-)standard Young tableau is a labelling of the boxes of a Young diagram with positive natural numbers (a Young tableau) satisfying extra conditions, at the minimum that labels do not decrease to the right and do increase downwards.

The number of (semi-)standard Young tableau of given shape (underlying Young diagram) govern various objects in the representation theory of the symmetric- and general linear group.

Definition

Definition

(Young diagram)
For nn \in \mathbb{N} a positive natural number, a Young diagram with nn boxes is a partition of nn, hence a sequence of weakly decreasing positive natural numbers

(λ 1λ 2λ rows(λ)),λ i + (\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_{rows(\lambda)} ) \,, \;\; \lambda_i \in \mathbb{N}_+

whose sum is nn:

(1)n=iλ i, n \;=\; \underset{i}{\sum} \lambda_i \,,

Definition

(semistandard Young tableau)

Given a Young diagram/partition λ\lambda (Def. ), a semistandard Young tableau TT of shape λ\lambda

  • is an indexed set of positive natural numbers of the following form (a Young tableau):

    (T i,j +) 1irows(λ)1jλ i; \big( T_{i, j} \in \mathbb{N}_+ \big)_{ {1 \leq i \leq rows(\lambda)} \atop { 1 \leq j \leq \lambda_i } } \,;
  • such that these labels are:

    1. weakly increasing to the right/along rows;

      (2)ij 1<j 2T i,j 1T i,j 2 \underset{ i }{\forall} \;\;\;\;\;\; j_1 \lt j_2 \;\Rightarrow\; T_{i, j_1} \leq T_{i, j_2}
    2. strictly increasing downwards/along columns:

      (3)ji 1<i 2T i 1,j<T i 2,j \underset{ j }{\forall} \;\;\;\;\;\; i_1 \lt i_2 \;\Rightarrow\; T_{i_1, j} \lt T_{i_2, j}

Remark

Beware that in a semistandard Young tableau (Def. ):

  • the label T 1,1T_{1, 1} in the top left box is not required to be 1;

  • in some applications (e.g. (7) below), though not in general, the labels are in addition required to be bounded T i,jkT_{i, j} \leq k.

Definition

(standard Young tableau)
A semistandard Young tableau (Def. ) of nn boxes (1) is called a standard Young tableau if every element of {1,,n}\big\{1, \cdots, n\} appears exactly once as a label.

Remark

In particular, in a standard Young tableau (Def.) we have that:

  1. not just the columns but also the rows are strictly increasing (cf. (2)),

  2. the first label of a standard Young tableau must be T 1,1=1T_{1,1} = 1 (cf. Rem. ).

Examples

The following is a semistandard Young tableau that does happen to start with 1 but is not a standard Young tableau:

1 1 1 3 2 3 4 \array{ 1 & 1 & 1 & 3 \\ 2 & 3 \\ 4 }

Properties

Given a partition λPart(n)\lambda \in Part(n), we write

(4)ssYT λinSet ssYT_\lambda \;in\; Set

for the set of semistandard Young tableaux (Def. ) whose underlying Young diagram (i.e. forgetting its labels) is given by λ\lambda.

Given moreover a natural number NN \in \mathbb{N} we write

(5)ssYT λ(N)ssYT λ ssYT_\lambda(N) \;\subset\; ssYT_\lambda

for the subset on those semistandard Young tableau TT whose labels are bounded by NN in that i,jT i,jN\underset{i,j}{\forall}\; T_{i, j } \;\leq\; N.

Relation to Schur polynomials

Given a semistandard Young tableau TT, we write X TX^T for the monomial which contains one factor of the variable x kx_k for each occurrence of kk in the Young tableau:

(6)x Tx 1 #1sx 2 #2s. x^T \;\coloneqq\; x_1^{\#1s} x_2^{\#2s} \cdots \,.

Proposition

For nn \in \mathbb{N} and λ\lambda a partition of nn, the corresponding Schur polynomial s λs_\lambda is equal to the sum over the monomials (6) associated with all semistandard Young tableau of shape λ\lambda (4):

s λ(x 1,x 2,)=TssYT λ,x T. s_\lambda(x_1, x_2, \cdots) \;\;=\;\; \underset{ {T \in ssYT_\lambda}, }{\sum} x^T \,.

(Sagan 01, Def. 4.4.1, review in Sagan Enc., p. 1)

This means that Schur polynomials in a finite set {x 1,,x N}\{x_1, \cdots, x_N\} of variables count semistandard Young tableau (of fixed shape and) with bounded labels (5):

(7)s λ(x 1,,x N)=TssYT λ(N),x T. s_\lambda(x_1, \cdots, x_N) \;\;=\;\; \underset{ {T \in ssYT_\lambda(N)}, }{\sum} x^T \,.

Hook-length formula

See at hook length formula.

Hook-content formula

The hook-content formula expresses the number of semistandard Young-Tableau TT with

  1. shape λ=(λ 1λ i)\lambda = (\lambda_1 \geq \cdots \geq \lambda_i) (a partition),

  2. labels in {1,,N}\{1, \cdots, N\},

  3. sum of labels i,jT i,j\sum_{i,j} T_{i,j}

through the following identification of the generating function for numbers of semistandard Young tableaux (ssYT) as a polynomial in a variable qq:

TssYT λ(N)q i,jT i,j=q iiλ ii{1,,rows(λ)}j{1,,λ j}1q N+content(i,j)1q hook(i,j), \underset{ T \in ssYT_\lambda(N) }{\sum} q^{ \sum_{i,j} T_{i,j} } \;\;=\;\; q^{ \sum_i i \cdot \lambda_i } \underset{ { i \in \{1, \cdots, rows(\lambda)\} } \atop {j \in \{1, \cdots, \lambda_j\}} }{\prod} \frac{ 1 - q^{N + content(i,j)} }{ 1 - q^{\ell hook(i,j)} } \,,

where

content(i,j)j1,AAAAhook(i,j)=length of hook at (i,j)th box. content(i,j) \;\coloneqq\; j - 1 \,, {\phantom{AAAA}} \ell hook(i,j) \;=\; \text{length of hook at (i,j)th box} \,.

See at hook-content formula for more.

Relation to dimensions of irreps

hook length formulahook-content formula
number of standard Young tableauxnumber of semistandard Young tableaux
dimension of irreps of Sym(n)dimension of irreps of SL(n)

Number of sYT with bounded number of rows

We discuss formulas for the number

|sYT n(N)|=λPart(n)rows(λ)N|sYT n| \left\vert sYT_n(N) \right\vert \;=\; \underset{ { \lambda \in Part(n) } \atop { rows(\lambda) \leq N } }{ \sum } \left\vert sYT_n \right\vert

of standard Young tableaux with nn boxes and N\leq N rows.

Asymptotic formulas for large nn

Asymptotically for large nn this is (Regev 81, (F.4.5.1)):

(8)|sYT n(N)| n(Nn) 14N(N1)N nN!(Γ(3/2)π/2) Nj=1NΓ(1+12j) \begin{aligned} \left\vert sYT_n(N) \right\vert & \; \overset{ n \to \infty }{\sim} \; \left( \frac{N}{n} \right)^{ \tfrac{1}{4} N(N-1) } \cdot \frac {N^n} {N!} \cdot \big( \underset{ \sqrt{\pi}/2 }{ \underbrace{ \Gamma(3/2) } } \big)^{- N} \cdot \underoverset {j=1} {N} {\prod} \Gamma \left( 1 + \tfrac{1}{2}j \right) \end{aligned}

Later this appears again as a conjecture in Kotěšovec 13:

(9)|sYT n(N)| j=1NΓ(j/2)Γ(1+j/2)2jN nπ N/2(Nn) 14(N(N1)) =j=1NΓ(1+j/2)2 NN!N nπ N/2(Nn) 14(N(N1)). \begin{aligned} \left\vert sYT_n(N) \right\vert & \;\sim\; \underoverset {j = 1} {N} {\prod} \underset{ \Gamma(1 + j/2) \tfrac{2}{j} }{ \underbrace{ \Gamma(j/2) } } \cdot \frac{N^n}{\pi^{N/2}} \cdot \left( \frac{N}{n} \right)^{ \tfrac{1}{4}(N(N-1)) } \\ & \;=\; \underoverset {j = 1} {N} {\prod} \Gamma \big( 1 + j/2 \big) \cdot \frac{2^N}{N!} \cdot \frac{N^n}{\pi^{N/2}} \cdot \left( \frac{N}{n} \right)^{ \tfrac{1}{4}(N(N-1)) } \,. \end{aligned}

(The first line is the expression conjectured in Kotěšovec 13, under the brace we use the translation formula, and the second line shows agreement with Regev 81 (F.4.5.1) as in (8).)

This may further be re-expressed (Kotěšovec 13, p. 2) in terms of the Barnes G-function G()G(-) (see there):

(10)|sYT n(N)| nj=1NΓ(j/2)G(N/2+1)G(N/2+1/2)G(1/2)N nπ N/2(Nn) 14(N(N1)) \begin{aligned} \left\vert sYT_n(N) \right\vert & \;\underset{n \to \infty}{\sim}\; \underset{ \mathclap{ \frac { G(N/2 + 1) \cdot G(N/2 + 1/2) } { G(1/2) } } }{ \underbrace{ \underoverset {j = 1} {N} {\prod} \Gamma(j/2) } } \cdot \frac{N^n}{\pi^{N/2}} \cdot \left( \frac{N}{n} \right)^{ \tfrac{1}{4}(N(N-1)) } \end{aligned}

Asymptotic formulas for large nn and large NN

Using the large-NN asymptotic expansion (here) of the Barnes G-function

G(N/2+1)Nexp(18N 2ln(N)(316+ln(2)8)N 2+ln(2π)4N112ln(N)+(ζ (1)ln(2)12)) G(N/2 + 1) \underset{N \to \infty}{\sim} \exp \left( \tfrac{1}{8} N^2 ln (N) - \left( \tfrac{3}{16} + \tfrac{ln(2)}{8} \right) N^2 + \tfrac{ln(2\pi)}{4} N - \tfrac{1}{12} ln(N) + \big( \zeta^'(-1) - \tfrac{ln(2)}{12} \big) \right)

inside the large-nn asymptotic expansion (10), we obtain the doubly asymptotic expansion of the number of standard Yound tableaux with nn boxes and N\leq N rows:

(11) ln(|sYT n(N)|) nNnln(N)14N 2ln(n)+14Nln(n) nN+12N 2ln(N)(38+ln(2)4)N 214Nln(N)+ln(2)2N16ln(N) nN+(2ζ (1)ln(2)6lnG(1/2)) \begin{aligned} & ln \big( \left\vert sYT_n(N) \right\vert \big) \\ & \; \underset{ { n \to \infty } \atop { N \to \infty } }{\sim}\; n ln(N) - \tfrac{1}{4}N^2 ln(n) + \tfrac{1}{4}N ln(n) \\ & \phantom{ \underset{ { n \to \infty } \atop { N \to \infty } }{\sim}\; } + \tfrac{1}{2} N^2 ln(N) - \left( \tfrac{3}{8} + \tfrac{ln(2)}{4} \right) N^2 - \tfrac{1}{4} N ln(N) + \tfrac{ln(2)}{2} N - \tfrac{1}{6} ln(N) \\ & \; \phantom{ \underset{ { n \to \infty } \atop { N \to \infty } }{\sim}\; } + \big( 2 \zeta^'(-1) - \tfrac{ln(2)}{6} - ln G(1/2) \big) \end{aligned}

Exact formulas for small NN

Exact formulas for small NN:

|sYT 2n(2)|=(2n)!(n!) 2,|sYT 2n+1(2)|=(2n+1)!n!(n+1)! \left\vert sYT_{2n}(2) \right\vert \;=\; \frac{ (2n)! }{ (n!)^2 } \,, \;\;\;\;\;\; \left\vert sYT_{2n+1}(2) \right\vert \;=\; \frac{ (2n + 1)! }{ n! (n+1)! }
|sYT n(3)|=i=0n/2(n2i)Catalan(i)=Motzkin(n), \left\vert sYT_{n}(3) \right\vert \;=\; \underoverset {i = 0} { \rfloor n/2 \lfloor } {\sum} \left( n \atop {2i} \right) Catalan(i) \;=\; Motzkin(n) \,,

where

This is attributed in Gouyou-Beauchamps 89 to Regev 81.

For N=4,5N = 4,5:

|sYT 2n1(4)|=Catalan(n)Catalan(n),|sYT 2n(4)|=Catalan(n)Catalan(n+1) \left\vert sYT_{2n-1}(4) \right\vert \;=\; Catalan(n) Catalan(n) \,, \;\;\;\;\;\; \left\vert sYT_{2n}(4) \right\vert \;=\; Catalan(n) Catalan(n+1)

due to Gouyou-Beauchamps 89.

References

General

Textbook account:

Survey in the context of Schur functions:

Specifically for standard Young tableaux:

See also the references at Young tableau.

Counting for bounded number of rows

Last revised on November 29, 2022 at 09:46:04. See the history of this page for a list of all contributions to it.