Young tableau

of order $m$

A Young diagram of order $m$ in whose cells the different numbers $1,\ldots,m$ have been inserted in some order, e.g.

┌───┬───┬───┬───┐
│ 5 │ 7 │ 9 │ 4 │
├───┼───┼───┼───┘
│ 8 │ 2 │ 1 │    
├───┼───┴───┘    
│ 3 │            
├───┤            
│ 6 │            
└───┘ 

A Young tableau is called standard if in each row and in each column the numbers occur in increasing order. The number of all Young tableaux for a given Young diagram $t$ of order $m$ is equal to $m!$ and the number of standard Young tableaux is $$ \frac{m!}{\prod\lambda_{ij}} $$

where the product extends over all the cells $c_{ij}$ of $t$ and $\lambda_{ij}$ denotes the length of the corresponding hook.

Comments

In Western literature the phrase Ferrers diagram is also used for a Young diagram. In the Russian literature the phrase "Young tableau" ( "Yunga tablitsa" ) and "Young diagram" ( "Yunga diagramma" ) are used precisely in the opposite way, with "tablitsa" referring to the pictorial representation of a partition and "diagramma" being a filled-in "tablitsa" .

Let $\kappa$ denote a partition of $m$ ($\kappa=(\kappa_1,\ldots,\kappa_t)$, $\kappa_i \in \{0,1,\ldots\}$, $\kappa_1+\cdots+\kappa_t=m$) as well as its corresponding Young diagram, its pictorial representation. Let $\lambda$ be a second partition of $m$. A $\kappa$-tableau of type $\lambda$ is a Young diagram $\kappa$ with its boxes filled with 's, 's, etc. For a semi-standard $\kappa$-tableau of type $\lambda$, the labelling of the boxes is such that the rows are non-decreasing (from left to right) and the columns are strictly increasing (from top to bottom). E.g.

┌───┬───┬───┬───┬───┐
│ 1 │ 1 │ 1 │ 1 │ 4 │
├───┼───┼───┼───┴───┘
│ 2 │ 2 │ 3 │        
├───┼───┼───┘        
│ 3 │ 4 │            
└───┴───┘ 

is a semi-standard $(5,3,2)$-tableau of type $(4,2,2,2)$. The numbers $K(\kappa,\lambda)$ of semi-standard $\kappa$-tableaux of type $\lambda$ are called Kostka numbers.

To each partition $\mu$ of $n$, there are associated two "natural" representations of $S_n$, the symmetric group on $n$ letters: the induced representation and the Specht module . The representation is:

where is the trivial representation of and is the Young subgroup of determined by , , where if and otherwise is the subgroup of permutations on the letters .

The group acts on the set of all -tableaux by permuting the labels. Two -tableaux are equivalent if they differ by a permutation of their labels keeping the sets of indices in each row set-wise invariant. An equivalence class of -tableaux is a -tabloid. The action of on -tableaux induces an action on -tabloids, and extending this linearly over a base field gives a representation of which is evidently isomorphic to . The dimension of is . Given a -tableau , let be the following element of :

where is the column-stabilizer of , i.e. the subgroup of of all permutations that leave the labels of the columns of set-wise invariant.

The Specht module, $[\mu]$, of $\mu$ is the submodule of spanned by all the elements , where is the tabloid of and is a -tableau. Over a field of characteristic zero the Specht modules give precisely all the different absolutely-irreducible representations of . By Young's rule, the number of times that the Specht module over $\mathbf{Q}$ occurs (as a composition factor) in $\rho(\kappa)$ is equal to the Kostka number $K(\kappa,\lambda)$. If $e_t$ is the Young symmetrizer of a $\mu$-tableau $t$, then the Specht module defined by the underlying diagram is isomorphic to the ideal $F[S_n]e_t$ of $F[S_n]. This is also (up to isomorphism) the representation denoted by $T_{\mu}$ in Representation of the symmetric groups. Cf. Majorization ordering for a number of other results involving partitions, Young diagrams and tableaux, and representations of the symmetric groups.

References

[a1]	D. Knuth, "The art of computer programming" , 3 , Addison-Wesley (1973)