TOPICS
Search

Young Tableau


YoungTableaux

The Young tableau (plural, "tableaux") of a Ferrers 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 an increasing sequence along each line and along 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 number 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)

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}.

There is a correspondence between a permutation and a pair of Young tableaux, known as the Schensted correspondence.

A Young tableau in which numbers are nondecreasing along lines and increasing along columns is called a semistandard Young tableau.


See also

Bumping Algorithm, Durfee Square, Ferrers Diagram, Hook Length Formula, Partition, Partition Function P, Permutation Involution, Random Tableau Schensted Correspondence, Tableau Class

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.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 class de problèmes de dénombrement liés au treillis des partitions d'entiers." Cahiers Buro 6, 2-107, 1965.Kreweras, G. "Dénombrements de chemins minimaux à sauts imposés." Comptes Rendus Acad. Sci. Paris 263, 1-3, 1966.Kreweras, G. "Sur une extension du problème dir 'de Simon Newcomb.' " Comptes Rendus 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." 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 Web Resource. https://mathworld.wolfram.com/YoungTableau.html

Subject classifications