Difference between revisions of "Young tableau"
(→Comments: image) |
|||
Line 16: | Line 16: | ||
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" . | 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 | + | Let $\kappa$ denote a [[partition]] of $m$ (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910017.png" />) as well as its corresponding [[Young diagram|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910025.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910026.png" />'s, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910027.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910028.png" />'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. |
− | < | + | <pre style="font-family: monospace;color:black"> |
+ | ┌───┬───┬───┬───┬───┐ | ||
+ | │ 1 │ 1 │ 1 │ 1 │ 4 │ | ||
+ | ├───┼───┼───┼───┴───┘ | ||
+ | │ 2 │ 2 │ 3 │ | ||
+ | ├───┼───┼───┘ | ||
+ | │ 3 │ 4 │ | ||
+ | └───┴───┘ | ||
+ | </pre> | ||
− | is a semi-standard | + | 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 | + | To each partition $\mu$ of $n$, there are associated two "natural" representations of $S_n$, the symmetric group on $n$ letters: the induced representation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910043.png" /> and the Specht module <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910044.png" />. The representation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910045.png" /> is: |
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910046.png" /></td> </tr></table> | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910046.png" /></td> </tr></table> |
Revision as of 18:51, 9 November 2023
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. $$ \fbox{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 tableau 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$ (,
,
) 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, , of
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
occurs (as a composition factor) in
is equal to the Kostka number
. If
is the Young symmetrizer of a
-tableau
, then the Specht module defined by the underlying diagram is isomorphic to the ideal
of
. This is also (up to isomorphism) the representation denoted by
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) |
Young tableau. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Young_tableau&oldid=54273