Reduced Words and Plane Partitions
Sergey Fomin
and Anatol N. Kirillov
DOI: 10.1023/A:1008694825493
Abstract
Let w 0 be the element of maximal length in thesymmetric group S n , and let Red( w 0) bethe set of all reduced words for w 0. We prove the identity å ( a 1 , a 2 , \frac{1}{4} ) Ĩ Red( w 0 ) ( x + a 1 )( x + a 2 ) \frac{1}{4} = ( 2 n )! Õ 1 \leqslant i < j \leqslant n \frac2 x + i + j - 1 i + j - 1 , \sum\limits_{(a_1 ,a_2 , \ldots ) \in Red(w_0 )} {(x + a_1 )(x + a_2 )} \cdots = \left( {_2^n } \right)!\prod\limits_{1 \leqslant i < j \leqslant n} {\frac{{2x + i + j - 1}}{{i + j - 1}}} , which generalizes Stanley's [20] formula forthe cardinality of Red( w 0), and Macdonald's [11] formula å a 1 a 2 \frac{1}{4} = ( 2 n ) ! \sum {a_1 a_2 \cdots = (_2^n )} ! .Our approach uses anobservation, based on a result by Wachs [21], that evaluation of certainspecializations of Schubert polynomials is essentially equivalent toenumeration of plane partitions whose parts are bounded from above. Thus,enumerative results for reduced words can be obtained from the correspondingstatements about plane partitions, and vice versa. In particular, identity(*) follows from Proctor's [14] formula for the number of planepartitions of a staircase shape, with bounded largest part.Similar results are obtained for other permutations and shapes; q-analogues are also given.
Pages: 311–319
Keywords: reduced word; plane partition; Schubert polynomial
Full Text: PDF
References
1. S.C. Billey, W. Jockusch, and R.P. Stanley, “Some combinatorial properties of Schubert polynomials,” J. Alg. Combin. 2 (1993), 345-374.
2. P. Edelman and C. Greene, “Balanced tableaux,” Advances in Math. 63 (1987), 42-99.
3. S. Fomin and R.P. Stanley, “Schubert polynomials and the nilCoxeter algebra,” Advances in Math. 103 (1994), 196-207.
4. S. Fomin and A.N. Kirillov, “The Yang-Baxter equation, symmetric functions, and Schubert polynomials,” Discrete Math. 153 (1996), 123-143.
5. S. Fomin, C. Greene, V. Reiner, and M. Shimozono, “Balanced labellings and Schubert polynomials,” European J. Combin. 18 (1997), 373-389.
6. I.M. Gessel and G.X. Viennot, “Determinants, paths, and plane partitions,” (preprint). P1: RPS/RKB P2: RPS Journal of Algebraic Combinatorics KL472-01-Fomin July 31, 1997 11:12 REDUCED WORDS AND PLANE PARTITIONS 319
7. R.C. King, “Weight multiplicities for the classical groups,” Springer Lecture Notes in Physics 50 (1976).
8. K. Koike and I. Terada, “Young-diagrammatic methods for the representation theory of the classical groups of type Bn, Cn, Dn,” J. Algebra 107 (1987), 466-511.
9. W. Kraśkiewicz and P. Pragacz, “Schubert functors and Schubert polynomials,” 1986 (preprint).
10. A. Lascoux, “Polyn\hat omes de Schubert. Une approche historique,” Séries formelles et combinatoire algébrique, P. Leroux and C. Reutenauer (Eds.), Université du Québec `a Montréal, LACIM, pp. 283-296, 1992.
11. I.G. Macdonald, Notes on Schubert polynomials, Laboratoire de combinatoire et d'informatique mathématique (LACIM), Université du Québec `a Montréal, Montréal, 1991.
12. I.G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd edition, Oxford Univ. Press, Oxford, 1995.
13. P.A. MacMahon, Combinatory Analysis, Vols. 1-2, Cambridge University Press, 1915, 1916; reprinted by Chelsea, New York, 1960.
14. R.A. Proctor, unpublished research announcement, 1984.
15. R.A. Proctor, “Odd symplectic groups,” Invent. Math. 92 (1988), 307-332.
16. R.A. Proctor, “New symmetric plane partition identities from invariant theory work of De Concini and Procesi,” European J. Combin. 11 (1990), 289-300.
17. V. Reiner and M. Shimozono, “Key polynomials and a flagged Littlewood-Richardson rule,” J. Combin. Theory, Ser. A 70 (1995), 107-143.
18. J.-P. Serre, Algebres de Lie Semi-Simples Complexes, W.A. Benjamin, New York, 1966.
19. R.P. Stanley, “Theory and applications of plane partitions,” Studies in Appl. Math. 50 (1971), 167-188, 259-279.
20. R.P. Stanley, “On the number of reduced decompositions of elements of Coxeter groups,” European J. Combin. 5 (1984), 359-372.
21. M.L. Wachs, “Flagged Schur functions, Schubert polynomials, and symmetrizing operators,” J. Combin. Theory, Ser. A 40 (1985), 276-289.
22. D.P. Zhelobenko, “The classical groups. Spectral analysis of their finite dimensional representations,” Russ. Math. Surv. 17 (1962), 1-94.
2. P. Edelman and C. Greene, “Balanced tableaux,” Advances in Math. 63 (1987), 42-99.
3. S. Fomin and R.P. Stanley, “Schubert polynomials and the nilCoxeter algebra,” Advances in Math. 103 (1994), 196-207.
4. S. Fomin and A.N. Kirillov, “The Yang-Baxter equation, symmetric functions, and Schubert polynomials,” Discrete Math. 153 (1996), 123-143.
5. S. Fomin, C. Greene, V. Reiner, and M. Shimozono, “Balanced labellings and Schubert polynomials,” European J. Combin. 18 (1997), 373-389.
6. I.M. Gessel and G.X. Viennot, “Determinants, paths, and plane partitions,” (preprint). P1: RPS/RKB P2: RPS Journal of Algebraic Combinatorics KL472-01-Fomin July 31, 1997 11:12 REDUCED WORDS AND PLANE PARTITIONS 319
7. R.C. King, “Weight multiplicities for the classical groups,” Springer Lecture Notes in Physics 50 (1976).
8. K. Koike and I. Terada, “Young-diagrammatic methods for the representation theory of the classical groups of type Bn, Cn, Dn,” J. Algebra 107 (1987), 466-511.
9. W. Kraśkiewicz and P. Pragacz, “Schubert functors and Schubert polynomials,” 1986 (preprint).
10. A. Lascoux, “Polyn\hat omes de Schubert. Une approche historique,” Séries formelles et combinatoire algébrique, P. Leroux and C. Reutenauer (Eds.), Université du Québec `a Montréal, LACIM, pp. 283-296, 1992.
11. I.G. Macdonald, Notes on Schubert polynomials, Laboratoire de combinatoire et d'informatique mathématique (LACIM), Université du Québec `a Montréal, Montréal, 1991.
12. I.G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd edition, Oxford Univ. Press, Oxford, 1995.
13. P.A. MacMahon, Combinatory Analysis, Vols. 1-2, Cambridge University Press, 1915, 1916; reprinted by Chelsea, New York, 1960.
14. R.A. Proctor, unpublished research announcement, 1984.
15. R.A. Proctor, “Odd symplectic groups,” Invent. Math. 92 (1988), 307-332.
16. R.A. Proctor, “New symmetric plane partition identities from invariant theory work of De Concini and Procesi,” European J. Combin. 11 (1990), 289-300.
17. V. Reiner and M. Shimozono, “Key polynomials and a flagged Littlewood-Richardson rule,” J. Combin. Theory, Ser. A 70 (1995), 107-143.
18. J.-P. Serre, Algebres de Lie Semi-Simples Complexes, W.A. Benjamin, New York, 1966.
19. R.P. Stanley, “Theory and applications of plane partitions,” Studies in Appl. Math. 50 (1971), 167-188, 259-279.
20. R.P. Stanley, “On the number of reduced decompositions of elements of Coxeter groups,” European J. Combin. 5 (1984), 359-372.
21. M.L. Wachs, “Flagged Schur functions, Schubert polynomials, and symmetrizing operators,” J. Combin. Theory, Ser. A 40 (1985), 276-289.
22. D.P. Zhelobenko, “The classical groups. Spectral analysis of their finite dimensional representations,” Russ. Math. Surv. 17 (1962), 1-94.