Signed enumeration of ribbon tableaux: an approach through growth diagrams
Dominique Gouyou-Beauchamps1
and Philippe Nadeau2
1Laboratoire de Recherche en Informatique, Université Paris Sud, 91405 Orsay, France
2Fakultät für Mathematik, Universität Wien, Garnisongasse 3, 1090 Vienna, Austria
2Fakultät für Mathematik, Universität Wien, Garnisongasse 3, 1090 Vienna, Austria
DOI: 10.1007/s10801-011-0324-2
Abstract
We give an extension of the famous Schensted correspondence to the case of ribbon tableaux, where ribbons are allowed to be of different sizes. This is done by extending Fomin's growth diagram approach of the classical correspondence, in particular by allowing signs in the enumeration. As an application, we give in particular a combinatorial proof, based on the Murnaghan-Nakayama rule, for the evaluation of the column sums of the character table of the symmetric group.
Pages: 67–102
Keywords: keywords ribbon tableaux; growth diagrams; murnaghan-Nakayama rule; garsia-Milne involution principle; RSK correspondence
Full Text: PDF
References
1. Bessenrodt, C., Olsson, J.: On the sequence A085642. In: The On-line Encyclopedia of Integer Se- quences (2004)
2. Chauve, C., Dulucq, S.: A geometric version of the Robinson-Schensted correspondence for skew oscillating tableaux. Discrete Math. 246(1-3), 67-81 (2002)
3. Dulucq, S., Sagan, B.E.: The Robinson-Schensted correspondence for skew-oscillating tableaux. In: Proceedings of the 4th Conference on Formal Power Series and Algebraic Combinatorics, Amsterdam, The Netherlands, pp. 129-142. Amsterdam, Elsevier (1995)
4. Dulucq, S., Sagan, B.E.: La correspondance de Robinson-Schensted pour les tableaux oscillants gauches. Discrete Math. 139(1-3), 129-142 (1995)
5. Fomin, S.V.: The generalized Robinson-Schensted-Knuth correspondence. Zap. Nau\check c. Semin. LOMI 155(Differentsialnaya Geometriya, Gruppy Li i Mekh. VIII):156-175, 195 (1986)
6. Fomin, S.: Duality of graded graphs. J. Algebr. Comb. 3(4), 357-404 (1994)
7. Fomin, S.: Schensted algorithms for dual graded graphs. J. Algebr. Comb. 4(1), 5-45 (1995)
8. Fomin, S.: Schur operators and Knuth correspondences. J. Comb. Theory, Ser. A 72(2), 277-292 (1995)
9. Fomin, S., Stanton, D.: Rim Hook Lattices. Algebra Anal. 9(5), 140-150 (1997)
10. Fulton, W.: Young Tableaux. London Mathematical Society Student Texts, vol.
35. Cambridge University Press, Cambridge (1997). With applications to representation theory and geometry
11. Garsia, A., Milne, S.: Method for constructing bijections for classical partition identities. Proc. Natl. Acad. Sci. USA 78(4, part 1), 2026-2028 (1981)
12. Garsia, A., Milne, S.: A Rogers-Ramanujan bijection. J. Comb. Theory, Ser. A 31(3), 289-339 (1981)
13. Isaacs, I.M.: Character Theory of Finite Groups. Dover, New York (1994). Corrected reprint of the 1976 original (Academic Press, New York; MR0460423 (57 #417))
14. Kerber, A.: Applied Finite Group Actions. Algorithms and Combinatorics, vol. 19, 2nd edn. Springer, Berlin (1999) J Algebr Comb (2012) 36:67-102
15. Macdonald, I.G.: Symmetric Functions and Hall Polynomials. Oxford Mathematical Monographs, 2nd edn. Clarendon/Oxford University Press, New York (1995)
16. Murnaghan, F.D.: On the representations of the symmetric group. Am. J. Math. 59(3), 437-488 (1937)
17. Nakayama, T.: On some modular properties of irreducible representations of a symmetric group. I. Jpn. J. Math. 18, 89-108 (1941)
18. Roby, T.: The connection between the Robinson-Schensted correspondence for skew oscillating tableaux and graded graphs. Discrete Math. 139(1-3), 481-485 (1995). Formal power series and algebraic combinatorics (Montreal, PQ, 1992)
19. Sagan, B.E.: Shifted tableaux, Schur Q-functions, and a conjecture of R. Stanley. J. Comb. Theory, Ser. A 45(1), 62-103 (1987)
20. Sagan, B.E.: The Symmetric Group. Graduate Texts in Mathematics, vol. 203, 2nd edn. Springer, New York (2001). Representations, combinatorial algorithms, and symmetric functions
21. Sagan, B.E., Stanley, R.P.: Robinson-Schensted algorithms for Skew tableaux. J. Comb. Theory, Ser. A 55(2), 161-193 (1990)
22. Schensted, C.: Longest increasing and decreasing subsequences. Can. J. Math. 13, 179-191 (1961)
23. Shimozono, M., White, D.E.: Color-to-spin ribbon Schensted algorithms. Discrete Math. 246(1-3), 295-316 (2002). Formal power series and algebraic combinatorics (Barcelona, 1999)
24. Sloane, N.: On-line encyclopedia of integer sequences. Accessible from N. Sloane's homepage
25. Stanley, R.P.: Differential posets. J. Am. Math. Soc. 1(4), 919-961 (1988)
26. Stanley, R.P.: Variations on differential posets. In: Invariant Theory and Tableaux, Minneapolis, MN,
1988. IMA Vol. Math. Appl., vol. 19, pp. 145-165. Springer, New York (1990)
27. Stanley, R.P.: Enumerative Combinatorics, vol.
2. Cambridge Studies in Advanced Mathematics, vol.
62. Cambridge University Press, Cambridge (1999). With a foreword by Gian-Carlo Rota and
2. Chauve, C., Dulucq, S.: A geometric version of the Robinson-Schensted correspondence for skew oscillating tableaux. Discrete Math. 246(1-3), 67-81 (2002)
3. Dulucq, S., Sagan, B.E.: The Robinson-Schensted correspondence for skew-oscillating tableaux. In: Proceedings of the 4th Conference on Formal Power Series and Algebraic Combinatorics, Amsterdam, The Netherlands, pp. 129-142. Amsterdam, Elsevier (1995)
4. Dulucq, S., Sagan, B.E.: La correspondance de Robinson-Schensted pour les tableaux oscillants gauches. Discrete Math. 139(1-3), 129-142 (1995)
5. Fomin, S.V.: The generalized Robinson-Schensted-Knuth correspondence. Zap. Nau\check c. Semin. LOMI 155(Differentsialnaya Geometriya, Gruppy Li i Mekh. VIII):156-175, 195 (1986)
6. Fomin, S.: Duality of graded graphs. J. Algebr. Comb. 3(4), 357-404 (1994)
7. Fomin, S.: Schensted algorithms for dual graded graphs. J. Algebr. Comb. 4(1), 5-45 (1995)
8. Fomin, S.: Schur operators and Knuth correspondences. J. Comb. Theory, Ser. A 72(2), 277-292 (1995)
9. Fomin, S., Stanton, D.: Rim Hook Lattices. Algebra Anal. 9(5), 140-150 (1997)
10. Fulton, W.: Young Tableaux. London Mathematical Society Student Texts, vol.
35. Cambridge University Press, Cambridge (1997). With applications to representation theory and geometry
11. Garsia, A., Milne, S.: Method for constructing bijections for classical partition identities. Proc. Natl. Acad. Sci. USA 78(4, part 1), 2026-2028 (1981)
12. Garsia, A., Milne, S.: A Rogers-Ramanujan bijection. J. Comb. Theory, Ser. A 31(3), 289-339 (1981)
13. Isaacs, I.M.: Character Theory of Finite Groups. Dover, New York (1994). Corrected reprint of the 1976 original (Academic Press, New York; MR0460423 (57 #417))
14. Kerber, A.: Applied Finite Group Actions. Algorithms and Combinatorics, vol. 19, 2nd edn. Springer, Berlin (1999) J Algebr Comb (2012) 36:67-102
15. Macdonald, I.G.: Symmetric Functions and Hall Polynomials. Oxford Mathematical Monographs, 2nd edn. Clarendon/Oxford University Press, New York (1995)
16. Murnaghan, F.D.: On the representations of the symmetric group. Am. J. Math. 59(3), 437-488 (1937)
17. Nakayama, T.: On some modular properties of irreducible representations of a symmetric group. I. Jpn. J. Math. 18, 89-108 (1941)
18. Roby, T.: The connection between the Robinson-Schensted correspondence for skew oscillating tableaux and graded graphs. Discrete Math. 139(1-3), 481-485 (1995). Formal power series and algebraic combinatorics (Montreal, PQ, 1992)
19. Sagan, B.E.: Shifted tableaux, Schur Q-functions, and a conjecture of R. Stanley. J. Comb. Theory, Ser. A 45(1), 62-103 (1987)
20. Sagan, B.E.: The Symmetric Group. Graduate Texts in Mathematics, vol. 203, 2nd edn. Springer, New York (2001). Representations, combinatorial algorithms, and symmetric functions
21. Sagan, B.E., Stanley, R.P.: Robinson-Schensted algorithms for Skew tableaux. J. Comb. Theory, Ser. A 55(2), 161-193 (1990)
22. Schensted, C.: Longest increasing and decreasing subsequences. Can. J. Math. 13, 179-191 (1961)
23. Shimozono, M., White, D.E.: Color-to-spin ribbon Schensted algorithms. Discrete Math. 246(1-3), 295-316 (2002). Formal power series and algebraic combinatorics (Barcelona, 1999)
24. Sloane, N.: On-line encyclopedia of integer sequences. Accessible from N. Sloane's homepage
25. Stanley, R.P.: Differential posets. J. Am. Math. Soc. 1(4), 919-961 (1988)
26. Stanley, R.P.: Variations on differential posets. In: Invariant Theory and Tableaux, Minneapolis, MN,
1988. IMA Vol. Math. Appl., vol. 19, pp. 145-165. Springer, New York (1990)
27. Stanley, R.P.: Enumerative Combinatorics, vol.
2. Cambridge Studies in Advanced Mathematics, vol.
62. Cambridge University Press, Cambridge (1999). With a foreword by Gian-Carlo Rota and
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition