<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 5 Issue 2" %>
Vexillary Involutions are Enumerated by Motzkin Numbers
O. Guibert1, E. Pergola2, and R. Pinzani2
1LaBRI (UMR 5800), Université Bordeaux 1, 351 cours de la Libération, 33405 Talence cédex, France
2Dipartimento di Sistemi e Informatica, via Lombroso, 6/17, 50134 Firenze, Italy
Annals of Combinatorics 5 (2) p.153-174 June, 2001
AMS Subject Classification: 05A05, 05A15
Vexillary permutations are very important for Schubert Polynomials. In this paper, we consider the enumeration of Vexillary involutions, that is, 2143-avoiding involutions. Instead of solving the generating function obtained by a succession system characterizing vexillary involuations, we establish a one-to-one correspondence with 1-2 trees enumerated by Motzkin numbers.
Keywords: bijection, generating tree, permutations with forbidden patterns, vexillary involutions, 1-2 trees, Motzkin numbers


1.  E. Babson and J. West, The permutations 123p4 ... pl and 321pl ... p4 are Wilf equivalent, preprint.

2.  C. Banderier, M. Bousquet, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou, On generating functions of generating trees, Proc. of 11th Formal Power Series and Algebraic Combinatorics, Barcelona, Spain (1999) 40每52.

3.  E. Barcucci, A. Del Lungo, and E. Pergola, Random generation of trees and other combinatorial objects, Theor. Comput. Sci. 218 (1999) 219每232.

4.  E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, ECO: A methodology for the enumeration of combinatorial objects, J. Differ. Equ. Appl. 5 (1999) 435每490.

5.  E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, From Motzkin to Catalan permutations, Discrete Math., to appear.

6.  E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, Directed animals, forests and permutations, Discrete Math. 204 (1999) 41每71.

7.  E. Barcucci, R. Pinzani, and R. Sprugnoli, The Motzkin family, PU.M.A. Ser. A 2 (1991) 249每279.

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

9.  N. Bergeron, A combinatorial construction of the Schubert polynomials, J. Combin. Theory Ser. A 60 (1992) 168每182.

10.  I.N. Bernstein, I.M. Gelfand, and S.I. Gelfand, Schubert cells and cohomology of the spaces G/P, Russ. Math. Surv. 28 (1973) 1每26.

11.  S. Billey and M. Haiman, Schubert polynomials for the classical groups, J. Amer. Math. Soc. 2 (1995) 443每482.

12.  S. Billey,W. Jockush, and R. Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (1993) 345每374.

13.  S. Billey and T.K. Lam, Vexillary elements in the hyperoctahedral group, J. Algebraic Combin. 8 (1998) 139每152.

14.  M. Bóna, Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps, J. Combin. Theory Ser. A 80 (1997) 257每272.

15.  M. Bóna, Permutations avoiding certain patterns: the case of length 4 and some generalizations, Discrete Math. 175 (1997) 55每67.

16.  F.R.K. Chung et al., The number of Baxter permutations, J. Combin. Theory Ser. A 24 (1978) 382每394.

17.  M. Demazure, Désingularisation des variétés de Schubert généralisées, Ann. Sci. Ec. Norm. Super. (4) 7 (1974) 53每88.

18.  R. Donaghey, Restricted plane tree representations of four Motzkin-Catalan equations, J. Combin. Theory Ser. B 22 (1977) 114每121.

19.  R. Donaghey, Automorphisms on Catalan trees and bracketings, J. Combin. Theory Ser. B 29 (1980) 75每90.

20.  R. Donaghey and L.W. Shapiro, Motzkin numbers, J. Combin. Theory Ser. A 23 (1977) 291每301.

21 K. Eriksson and S. Linusson, The size of Fulton's essential set, Elect. J. Combin. 2 (1995) #R6.

22.  S. Fomin and A. Kirillov, Yang-Baxter equation, symmetric functions and Schubert polynomials, Adv. Math. 103 (1994) 196每207.

23.  W. Fulton, Flags, Schubert polynomials, degeneracy loci, and determinantal formulas, Duke Math. J. 65 (1992) 381每420.

24.  I.M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990) 257每285.

25.  S. Gire, Arbres, permutations à motifs exclus et cartes planaires : quelques problèmes algorithmiques et combinatoires, Ph.D. Thesis, University Bordeaux 1, France, 1993.

26.  D. Gouyou每Beauchamps, Standard Young tableaux of height 4 and 5, Europ. J. Combin. 10 (1989) 69每82.

27.  O. Guibert, Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young, Ph.D. Thesis, University Bordeaux 1, France, 1995.

28.  P. Hanlon, Counting interval graphs, Trans. Amer. Math. Soc. 272 (1982) 383每426.

29.  D.E. Knuth, The Art of Computer Programming, Vol. 1, Fundamental Algorithms, Second Edition, Addison-Wesley, Reading, Massachusetts, 1973.

30.  A. Lascoux and M.-P. Schützenberger, Polynômes de Schubert, C. R. Acad. Sci. Paris Sér. I Math. 294 (2) (1982) 447每450.

31.  A. Lascoux and M.-P. Schützenberger, Polynômes de Schubert, C. R. Acad. Sci. Paris Sér. I Math. 295 (1982) 393每398.

32.  A. Lascoux and M.-P. Sch邦tzenberger, Schubert polynomials and the Littlewood-Richardson rule, Lett. Math. Phys. 10 (1985) 111每124.

33.  I.G. Macdonald, Notes on Schubert polynomials, Publication du Laboratoire de Combinatoire et d'Informatique Mathématique de lÚniversité du Québec à Montréal 6, 1991.

34.  I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, Oxford, 1979.

35.  L. Manivel, Fonctions symétriques, polynômes de Schubert et lieux de dégénérescence, Cours Spécialisés 3 Paris: Société Mathématique de France, 1998.

36.  T. Motzkin, Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products, Bull. Amer. Math. Soc. 54 (1948) 352每360.

37.  E. Pergola, ECO: a methodology for enumerating combinatorial objects, Ph.D. Thesis, University of Firenze, Italy, 1998.

38.  A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. Math. 41 (1981) 115每136.

39.  J. Riordan, Enumeration of plane trees by branches and endpoints, J. Combin. Theory Ser. A 19 (1975) 214每222.

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

41.  H.A. Rothe, Ueber permutationen, Beziehlung auf die Stellen ihrer Elemente, Sammlung combinatorisch-analytischer Abhandlungen, Leipzig, 1800.

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

43.  M.P. Sch邦tzenberger, Quelques remarques sur une construction de Schensted, Math. Scand. 12 (1963) 117每128.

44.  N.J.A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973.

45.  F. Sottile, A geometric approach to the combinatorics of Schubert polynomials, Proc. of 7th Formal Power Series and Algebraic Combinatorics, Marne-la-Vall谷e, France (1995) 501每 509.

46.  Z.E. Stankova, Forbidden subsequences, Discrete Math. 132 (1994) 291每316.

47.  R. Stanley, On the number of reduced decompositions of elements of Coxeter groups, Europ. J. Combin. 5 (1984) 359每372.

48.  J. West, Permutations with forbidden subsequences and stack-sortable permutations, Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, 1990.