<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue1" %>
Permutation Sign under the Robinson-Schensted Correspondence
Astrid Reifegerste
Institut für Mathematik, Universität Hannover, Welfengarten 1, 30167 Hannover, Germany
Annals of Combinatorics 8 (1) p.103-112 March, 2004
AMS Subject Classification: 05E10, 05A15
We show how the sign of a permutation can be deduced from the tableaux induced by the permutation under the Robinson-Schensted correspondence. The result yields a simple proof of a conjecture on the squares of imbalances raised recently by Stanley.
Keywords: sign, permutations, tableaux, Robinson-Schensted correspondence, Knuth equivalence, Beissinger algorithm,


1. J.S. Beissinger, Similar constructions for Young tableaux and involutions, and their application to shiftable tableaux, Discrete Math. 67 (1987) 149–163.

2. W.H. Burge, Four correspondences between graphs and generalized Young tableaux, J. Combin. Theory, Ser. A 17 (1974) 12–30.

3. W. Fulton, Young Tableaux, Cambridge University Press, 1997.

4. D.E. Knuth, Permutations, matrices, and generalized Young tableaux, Pacific J. Math. 34 (1970) 709–727.

5. T. Lam, Growth diagrams, domino insertion and sign-imbalance, preprint, 2003, math.CO/0308265.

6. A. Lascoux and M. P. Schützenberger, Le monoide plaxique, Quaderni de la Ricerca Scienti fica 109 (1981) 129–156.

7. A. Reifegerste, Refined sign-balance on 321-avoiding permutations, preprint, 2003, math.CO/0305327.

8. G. de B. Robinson, On the representations of the symmetric group, Amer. J. Math. 60 (1938) 745–760.

9. C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961) 179–191.

10. M.P. Schützenberger, Quelques remarques sur une construction de Schensted, Math. Scand. 12 (1963) 117–128.

11. M.P. Schützenberger, La correspondence de Robinson, In: Combinatoire et repr¨¦sentation du groupe sym¨¦trique, Lecture Notes in Mathematics, Vol. 579, Springer-Verlag, 1977, pp. 59–113.

12. M. Shimozono and D.E. White, A color-to-spin domino Schensted algorithm, Elect. J. Combin. 8 (2001) #R21.

13. J. Sjöstrand, On the sign-imbalance of partition shapes, preprint, 2003, math.CO/0309231.

14. R.P. Stanley, Enumerative Combinatorics, Vols. I, II, Cambridge University Press, 1997, 1999.

15. R.P. Stanley, Some remarks on sign-balanced and maj-balanced posets, preprint, 2002, math.CO/0211113.

16. G. Viennot, Une forme géométrique de la correspondance de Robinson-Schensted, In: Combinatoire et représentation du groupe symétrique, Lecture Notes in Mathematics, Vol. 579, Springer-Verlag, 1977, pp. 29–58.