TOPICS
Search

Young Tableau


YoungTableaux

A Young tableau (plural, "tableaux") is a filling of the boxes of a Ferrers diagram with positive integers. A standard Young tableau with n boxes contains each of 1, 2, ..., n once, with entries increasing along each row and down each column. For example, the standard Young tableaux of size n=3 are given by {{1,2,3}}, {{1,3},{2}}, {{1,2},{3}}, and {{1},{2},{3}}, illustrated above. The bumping algorithm is used to construct a standard Young tableau from a permutation of {1,...,n}, 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

 a_n=a_(n-1)+(n-1)a_(n-2)

for integers n>=3, with a_1=1 and a_2=2. This is the same as the number of permutation involutions on n elements (Skiena 1990, p. 32).

YoungTableaux3211

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 {3,2,1,1}.

The Schensted correspondence is a bijection between permutations of n elements and pairs of standard Young tableaux of the same shape, each containing 1, 2, ..., n 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 Promotion

Explore 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 Tableau

Cite this as:

Weisstein, Eric W. "Young Tableau." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/YoungTableau.html

Subject classifications