Young Tableau

The Young Tableau of a Young Diagram is obtained by placing the numbers 1, ..., $n$ in the $n$ boxes of the diagram. A ``standard'' Young tableau is a Young tableau in which the numbers form a nondecreasing sequence along each line and along each column. The standard Young tableaux of size three are given by $\{\{1, 2, 3\}\}$, $\{\{1, 3\}, \{2\}\}$, $\{\{1, 2\}, \{3\}\}$, and $\{\{1\}, \{2\}, \{3\}\}$. The number of standard Young tableaux of size 1, 2, 3, ... are 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (Sloane's A000085). These numbers can be generated by the Recurrence Relation

$$a(n)=a(n-1)+(n-1)a(n-2)$$

with $a(1)=1$ and $a(2)=2$.

There is a correspondence between a Permutation and a pair of Young tableaux, known as the Schensted Correspondence. The number of all standard Young tableaux with a given shape (corresponding to a given Young Diagram) is calculated with the Hook Length Formula. The Bumping Algorithm is used to construct a standard Young tableau from a permutation of $\{1, \ldots, n\}$.

See also Bumping Algorithm, Hook Length Formula, Involution (Set), Schensted Correspondence, Young Diagram

References

Fulton, W. Young Tableaux with Applications to Representation Theory and Geometry. New York: Cambridge University Press, 1996.

Ruskey, F. ``Information on Permutations.'' http://sue.csc.uvic.ca/~cos/inf/perm/PermInfo.html#Tableau.

Skiena, S. S. The Algorithm Design Manual. New York: Springer-Verlag, pp. 254-255, 1997.

Sloane, N. J. A. Sequence A000085/M1221 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.