×

zbMATH — the first resource for mathematics

Balanced tableaux. (English) Zbl 0616.05005
A result of R. P. Stanley [Eur. J. Comb. 5, 359-372 (1984; Zbl 0587.20002)] states that the number of maximal chains in the weak ordering of the symmetric group on n letters (i.e. the ordering obtained by transpositions of adjacent elements) is equal to the number of standard Young tableaux of shape \(\lambda =\{n-1,n-2,...,2,1\}\). The authors here give a combinatorial and insightful proof of this identity by demonstrating a natural correspondence between maximal chains and what they define as balanced tableaux of shape \(\lambda\). A tableau is balanced if for each hook in the tableau the number of elements lying in or below the corner is equal to the number of entries in the hook whose value is less than or equal to the value of the corner entry. The authors finish the proof by giving a bijection between standard Young tableaux of shape \(\lambda\) and balanced tableaux of shape \(\lambda\).
Reviewer: D.M.Bressoud

MSC:
05A15 Exact enumeration problems, generating functions
20C30 Representations of finite symmetric groups
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Björner, A, Orderings of Coxeter groups, () · Zbl 0594.20029
[2] Bourbaki, N, Groupes et algebres de Lie, (), Chap. 4, 5, et 6 · Zbl 0483.22001
[3] Frame, J.S; Robinson, G de B; Thrall, R.M, The hook graphs of the symmetric group, Canad. J. math., 6, 316-324, (1954) · Zbl 0055.25404
[4] \scC. Greene, On Schützenberger’s promotion and evacuation operators, in preparation.
[5] Greene, C; Edelman, P, Combinatorial correspondences for Young tableaux, balanced tableaux and maximal chains in the weak Bruhat order of Sn, () · Zbl 0562.05008
[6] Knuth, D.E, Permutations, matrices, and generalized Young tableaux, Pacific J. math., 34, 709-727, (1970) · Zbl 0199.31901
[7] Knuth, D.E, The art of computer programming. vol. 3. searching and sorting, (1973), Addison-Wesley Reading, Mass · Zbl 0302.68010
[8] Lascoux, A; Schützenberger, M.P, Structure de Hopf de l’anneau de cohomologie et de l’anneau de Grothendieck d’une variete de drapeaux, C. R. acad. sci. Paris Sér. I math., 295, 629-633, (1982) · Zbl 0542.14030
[9] Lascoux, A; Schützenberger, M.P, Le monoide plaxique, () · Zbl 0517.20036
[10] Marshall, A.N; Olkin, I, Inequalities: theory of majorization and its applications, (1979), Academic Press Orlando, Fla · Zbl 0437.26007
[11] Robinson, G.de B, On the representations of the symmetric group, Amer. J. math., 60, 745-760, (1938) · Zbl 0019.25102
[12] Schensted, C, Longest increasing and decreasing subsequences, Canad. J. math., 13, 179-191, (1961) · Zbl 0097.25202
[13] Schützenberger, M.P, Quelques remarques sur une construction de Schensted, Math. scand., 13, 117-128, (1963) · Zbl 0216.30202
[14] Schützenberger, M.P, Promotion des morphisms d’ensemble ordonnes, Discrete math., 2, 73-94, (1972) · Zbl 0279.06001
[15] Schützenberger, M.P, Evacuations, (), 257-264 · Zbl 0377.05015
[16] Schützenbergeŕ, M.P, La correspondance de Robinson, (), 59-113 · Zbl 0398.05011
[17] Stanley, R.P, A combinatorial conjecture concerning the symmetric group, (1982), preprint
[18] Stanley, R.P, On the number of reduced decompositions of elements of Coxeter groups, European J. combin., 5, 359-372, (1984) · Zbl 0587.20002
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.