×

zbMATH — the first resource for mathematics

Standard Young tableaux of height 4 and 5. (English) Zbl 0672.05012
The number of standard Young tableaux the shape of which has n cells or boxes and at most k rows is denoted by \(S^ k_ n\). The motivation to find expressions for \(S^ k_ n\) comes from various other areas besides combinatorics such as the theory of symmetric functions, invariant theory, algebraic geometry, the theory of polynomials identities. The Procesi-Razmyslov theory of trace identities, and the theory of algorithms.
Formulae for \(S^ 2_ n\) and \(S^ 3_ n\) are known, and the Catalan number or Motzkin number appear in these expressions. In the present paper, exact formulae for \(S^ 4_ n\) and \(S^ 5_ n\) are obtained. The proofs are combinatorial. First, a bijection between involutions and labelled Motzkin words is recalled. Then stacks of an involution are introduced, the height of which are related to the lengths of descreasing sequences in the involution. Connections between stacks and labelled Motzkin words are examined. Such considerations lead to a bijection between standard Young tableaux having at most 4 rows and pairs of non- crossing Dyck paths, thus enabling the author to obtain formulae for \(S^ 4_ n\) and \(S^ 5_ n\). Finally it is shown that the corresponding generating functions are not algebraic.
Reviewer: J.Van der Jeugt

MSC:
05A17 Combinatorial aspects of partitions of integers
11P81 Elementary theory of partitions
05A15 Exact enumeration problems, generating functions
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cori, R.; Dulucq, S.; Viennot, G., Shuffle or parenthesis systems and Baxter permutations, J. comb. theory A, 43, 1-22, (1986) · Zbl 0662.05004
[2] Dulucq, S., Equations avec operateurs: un outil combinatoire, ()
[3] Flajolet, P., Combinatorial aspects of continued fractions, Discr. math., 32, L25-161, (1980) · Zbl 0445.05014
[4] Frame, J.S.; De, G.; Robinson, B.; Thrall, R.M., The hook graphs of the symmetric group, Can. J. math., 6, 316-324, (1954) · Zbl 0055.25404
[5] Francon, J.; Viennot, G., Permutations selon leurs pics, creux, montees et doubles descentes, nombres d’Euler et nombres de Genocchi, Discr. math., 28, 21-35, (1979) · Zbl 0409.05003
[6] Frobenius, G., Uber die charaktere de symmetrischen gruppen, Preuss. akad. wiss. sitz., 516-534, (1900) · JFM 31.0129.02
[7] Gansner, E., Matrix correspondances and the enumeration of plane partions, (1979), Ph.D. thesis, M.I.T.
[8] Gessel, I.M.; Viennot, G., Binomial determinants, paths and hook length formulae, Adv. math., 58, 300-321, (1985) · Zbl 0579.05004
[9] Gouyou-Beauchamps, D., Chemins sous-diagonaux et tableaux de Young, colloque de combinatoire enumerative, Montreal, UQAM juin 1985, L.N. math., 1234, 112-125, (1986)
[10] Greene, C., An extension of Schensted’s theorem, Adv. math.,, 14, 254-265, (1974) · Zbl 0303.05006
[11] Greene, C.; Nijenhuis, A.; Wilf, H.S., A probabilistic proof of a formula for the number of Young tableaux of a given shape, Adv. math.,, 31, L04-109, (1979) · Zbl 0398.05008
[12] Hillman, A.P.; Grassl, R.M., Reverse plane partitions and tableau hook numbers, J. comb. theory, ser. A,, 21, 216-221, (1976) · Zbl 0341.05008
[13] Jungen, R., Sur LES series de Taylor n’ayant que des singularites algebrico-logarithmiques sur leur cercle de convergence, Comment. math. helv., 3, 226-306, (1931) · JFM 57.0373.03
[14] Knuth, D.E., Permutations, Matrices and generalized Young tableaux, Pacific J. math.,, 34, 709-727, (1970) · Zbl 0199.31901
[15] Knuth, D.E., The art of computer programming, () · Zbl 0191.17903
[16] Mullin, R.C., The enumeration of Hamiltonian polygons in triangular maps, Pacific J. math.,, 16, 139-145, (1966) · Zbl 0137.43001
[17] Nakayama, T., On some modular properties of irreductible representations of a symmetric group, I, 11, jap. J. math.,, 17, 411-423, (1940) · Zbl 0061.04001
[18] Regev, A., Asymptotic values for degrees associated with strips of Young diagrams, Adv. math.,, 41, 115-136, (1981) · Zbl 0509.20009
[19] Remmel, J.B., Bijective proofs of formulae for the numbers of standard Young tableaux, Linear and multilinear algebra, 11, 45-100, (1982) · Zbl 0485.05005
[20] Remmel, J.B.; Whitney, R., A bijective proof of the hook formula for the number of column strict tableaux with bounded entries, Europ. J. comb.,, 4, 45-63, (1983) · Zbl 0521.05007
[21] De, G.; Robinson, B., On the representation of the symmetric groups, Am. J. math., 60 (1938), 745-760; 69 (1947), 286-298;, 70, 277-294, (1948) · Zbl 0036.15501
[22] Sagan, B., Enumeration of partitions with hooklengths, Europ. J. comb.,, 3, 85-94, (1982) · Zbl 0483.05010
[23] DeSainte-Catherine, M., Couplages et pfaffiens en combinatoire, physique theorique et informatique, (1983), These 3 6,e cycle, Bordeaux
[24] Schensted, C., Longest increasing and decreasing subsequences, Cand. J. math.,, 13, 179-191, (1961) · Zbl 0097.25202
[25] Schutzenberger, M.P., Quelques remarques sur une construction de Schensted, Math. scand.,, 12, 117-128, (1963) · Zbl 0216.30202
[26] Stanley, R.P., Ordered structures and partitions, (1971), Thesis, Harvard University
[27] Stanley, R.P., Differentiability finite power series, Europ. J. comb.,, 1, 175-188, (1980) · Zbl 0445.05012
[28] Tutte, W.T., A census of Hamiltonian polygons, Can. J. math.,, 14, 402-417, (1962) · Zbl 0105.17601
[29] Viennot, G., Chain and antichain families grids and Young tableaux, () · Zbl 0555.05004
[30] Young, A., On quantitative substitutional analysis II, Proc. lond. math. soc.,, 34, 361-397, (1902) · JFM 33.0158.03
[31] Franzblau, D.; Zeilberger, D., A bijection proof of the hook-lengths formula, J. algorithms,, 3, 317-343, (1982) · Zbl 0498.68042
[32] D. Zeilberger: A short hook-lengths bijection inspired by the Greene-Nijenhuis-Wilf proof, preprint. · Zbl 0551.05010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.