Some Statistics on Restricted 132 Involutions

Olivier Guibert and Toufik Mansour

LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France

{guibert, toufik}@labri.fr

Annals of Combinatorics 6 (3) p.337-348 September, 2002

Abstract:

In [14] Guibert and
Mansour studied involutions on n letters avoiding (or containing exactly once)
132 and avoiding (or containing exactly once) an arbitrary pattern on k letters.
They also established a bijection between 132-avoiding involutions and Dyck
word prefixes of same length. Extending this bijection to bilateral words it
allows to determine more parameters; in particular, we consider the number of
inversions and rises of the involutions on the words. This is the starting point
for considering two different directions: even/odd involutions and statistics
of some generalized patterns. Thus we first study generating functions for the
number of even or odd involutions on n letters avoiding (or containing exactly
once) 132 and avoiding (or containing exactly once) an arbitrary pattern on
k letters. In several interesting cases the generating function depends only
on k and is expressed via Chebyshev polynomials of the second kind. Next, we
consider other statistics on 132-avoiding involutions by counting occurrences
of some generalized patterns, related to the enumeration according to the number
of rises.

References:

1. E. Babson and E. Steingrìmsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. B44b (2000) 18 pp.

2. M. Bóna, The permutation classes equinumerous to the smooth class, Elect. J. Combin. 5 (1998) #R31.

3. P. Brändén, A. Claesson, and E. Steingrìmsson, Continued fractions and increasing subsequences in permutations, Discrete Math., to appear.

4. L. Chottin and R. Cori, Une preuve combinatoire de la rationalité dúne série génératrice associée aux arbres, R.A.I.R.O. Informatique théorique 16 (2) (1982) 113–128.

5. T. Chow and J. West, Forbidden subsequences and Chebyshev polynomials, Discrete Math. 204 (1999) 119–128.

6. F.R.K. Chung, R.L. Graham, V.E. Hoggat, and M. Kleiman, The number of Baxter permutations, J. Combin. Theory, Ser. A 24 (1978) 382–394.

7. A. Claesson, Generalized pattern avoidance, Europ. J. Combin. 22 (2001) 961–973.

8. A. Claesson and T. Mansour, Permutations avoiding a pair of generalized patterns of length three with exactly one dash, preprint, CO/0107044.

9. S. Dulucq, S. Gire, and O. Guibert, Some permutations with forbidden patterns enumerated by central binomial coefficient, Motzkin numbers and Schröder numbers, preprint.

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

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

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

13. 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.

14. O. Guibert and T. Mansour, Restricted 132-involutions and Chebyshev polynomials, Sém. Lothar. Combin. B48a (2002).

15. O. Guibert, E. Pergola, and R. Pinzani, Vexillary involutions are enumerated by Motzkin numbers, Ann. Combin. 5 (2001) 153–174.

16. M. Jani and R.G. Rieper, Continued fractions and Catalan problems, Elect. J. Combin. 7 (2000) #R1.

17. S. Kitaev, Multi-avoidance of generalised patterns, Discrete Math., to appear.

18. D.E. Knuth, The art of computer programming, Vol. 1, Fundamental Algorithms, Addison- Wesley, Reading, Mass., 1973.

19. C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. 27 (2001) 510–530.

20. D. Kremer, Permutations with forbidden subsequences and a generalized Schröder number, Discrete Math. 218 (2000) 121–130.

21. T. Mansour, Continued fractions and generalized patterns, Europ. J. Combin. 23 (3) (2002) 329–344.

22. T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Ann. Combin. 6 (2002) 1–12.

23. T. Mansour, Continued fractions, statistics, and generalized patterns, Ars Combin., to appear.

24. T. Mansour and A. Vainshtein, Restricted permutations, continued fractions, and Chebyshev polynomials, Elect. J. Combin. 7 (2000) #R17.

25. T. Mansour and A. Vainshtein, Restricted 132-avoiding permutations, Adv. Appl. Math. 126 (2001) 258–269.

26. T. Mansour and A. Vainshtein, Layered restrictions and Chebychev polynomials, Ann. Combin. 5 (2001) 451–458.

27. T. Mansour and A. Vainshtein, Restricted permutations and Chebyshev polynomials, Sém. Lothar. Combin. B47c (2002).

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

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

30. Th. Rivlin, Chebyshev Polynomials, From Approximation Theory to Algebra and Number Theory, John Wiley, New York, 1990.

31. A. Robertson, Permutations containing and avoiding 123 and 132 patterns, Discrete Math. Theoret. Comput. Sci. 3 (1999) 151–154.

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

33. A. Robertson, H. Wilf, and D. Zeilberger, Permutation patterns and continuous fractions, Elect. J. Combin. 6 (1999) #R38.

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

35. R. Simion and F.W. Schmidt, Restricted permutations, Europ. J. Combin. 6 (1985) 383–406.

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

37. J. West, Generating trees and forbidden subsequences, Discrete Math. 157 (1996) 363–372.