Young Tableau
A Young tableau (plural, "tableaux") is a filling of the boxes of a Ferrers diagram with positive
integers. A standard Young tableau with boxes contains each of 1, 2, ...,
once, with entries increasing along each row and down each
column. For example, the standard Young tableaux of size
are given by
,
,
, and
, illustrated above. The bumping
algorithm is used to construct a standard Young tableau from a permutation
of
, and the numbers of standard
Young tableaux of size 1, 2, 3, ... are 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496,
... (OEIS A000085). These numbers can be generated
by the recurrence relation
for integers , with
and
. This is the same as the number of permutation
involutions on
elements (Skiena 1990, p. 32).
The number of all possible standard Young tableaux of a given shape can also be considered, and can be calculated with the hook length formula.
For example, the illustration above shows the 35 standard tableaux of shape .
The Schensted correspondence is a bijection between permutations
of elements and pairs of standard Young
tableaux of the same shape, each containing 1, 2, ...,
once.
A semistandard Young tableau has entries weakly increasing along rows and strictly increasing down columns. Entries may repeat.
See also
Bumping Algorithm, Durfee Square, Ferrers Diagram, Hook Length Formula, Partition, Partition Function P, Permutation Involution, Random Tableau, Schensted Correspondence, Tableau Class, Tableau PromotionExplore with Wolfram|Alpha
References
Bressoud, D. and Propp, J. "How the Alternating Sign Matrix Conjecture Was Solved." Not. Amer. Math. Soc. 46, 637-646, 1999.Comtet, L. "Standard Tableaux." Ch. 2, Exercise 26 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 125-126, 1974.Fulton, W. Young Tableaux: With Applications to Representation Theory and Geometry. New York: Cambridge University Press, 1997.Kreweras, G. "Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers." Cahiers Buro 6, 9-107, 1965.Kreweras, G. "Dénombrements de chemins minimaux à sauts imposés." C. R. Acad. Sci. Paris 263, 1-3, 1966.Kreweras, G. "Sur une extension du problème dir 'de Simon Newcomb.' " C. R. Acad. Sci. Paris 263, 43-45, 1966.Kreweras, G. "Traitement simultané du 'problème de Young' et du 'problème de Simon Newcomb.' " Cahiers Buro 10, 23-31, 1967.Messiah, A. Appendix D in Quantum Mechanics, Vol. 2. Amsterdam, Netherlands: North-Holland, p. 1113, 1961-62.Ruskey, F. "Information on Permutations." https://web.archive.org/web/20140923074938/http://www.theory.csc.uvic.ca/~cos/inf/perm/PermInfo.html#Tableau.Skiena, S. "Young Tableaux." §2.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 63-76, 1990.Skiena, S. S. The Algorithm Design Manual. New York: Springer-Verlag, pp. 254-255, 1997.Sloane, N. J. A. Sequence A000085/M1221 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, 1999.Wilf, H. "The Computer-Aided Discovery of a Theorem about Young Tableaux." J. Symb. Comput. 20, 731-735, 1995.Referenced on Wolfram|Alpha
Young TableauCite this as:
Weisstein, Eric W. "Young Tableau." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/YoungTableau.html