Forests and pattern-avoiding permutations modulo pure descents

Baril, Jean-Luc; Kirgizov, Sergey; Petrossian, Armen

doi:10.1515/puma-2015-0025

Abstract

We investigate an equivalence relation on permutations based on the pure descent statistic. Generating functions are given for the number of equivalence classes for the set of all permutations, and the sets of permutations avoiding exactly one pattern of length three. As a byproduct, we exhibit a permutation set in one-to-one correspondence with forests of ordered binary trees, which provides a new combinatorial class enumerated by the single-source directed animals on the square lattice. Furthermore, bivariate generating functions for these sets are given according to various statistics.

References

[1] E. Babson and E. Steingrímsson, Generalized permutation patterns and a classification of Mahonian statistics, Sém. Lothar. Combin., 44 (2000) Article B44b.
Search in Google Scholar Back to article
[2] E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Directed animals, forests and permutations, Discrete Math., 204 (1999) 41–71.10.1016/S0012-365X(98)00366-5
Search in Google Scholar Back to article
[3] J.-L. Baril, T. Mansour and A. Petrossian, Equivalence classes of permutations modulo excedances, J. Comb., 5 (2014) 453–469.10.4310/JOC.2014.v5.n4.a4
Search in Google Scholar Back to article
[4] J.-L. Baril and A. Petrossian, Equivalence classes of permutations modulo descents and left-to-right maxima, Pure Math. Appl. (PU.M.A.), 25 (2015) 19–29.10.1515/puma-2015-0002
Search in Google Scholar Back to article
[5] J.-L. Baril and S. Kirgizov, The pure descent statistics on permutations, Discrete Math., 340 (2017) 2550–2558.10.1016/j.disc.2017.06.005
Search in Google Scholar Back to article
[6] F. Bergeron, N. Bergeron, R. B. Howlett and D. E. Taylor, A decomposition of the descent algebra of a finite Coxeter group, J. Algebraic Combin., 1 (1992) 23–44.10.1023/A:1022481230120
Search in Google Scholar Back to article
[7] 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.10.1006/jcta.1997.2800
Search in Google Scholar Back to article
[8] M. Bóna, Combinatorics of permutations, Chapman and Hall/CRC, Second Edition, 2012.
Search in Google Scholar Back to article
[9] M. Bousquet-Mélou, New enumerative results on two-dimensional directed animals, Proc. 7th FPSAC, Université de Marne-la-Vallée, Paris, 1995, 103–116.
Search in Google Scholar Back to article
[10] M. Bousquet-Mélou and S. Butler, Forest-like permutations, Ann. Comb., 11 (2007) 335–354.10.1007/s00026-007-0322-1
Search in Google Scholar Back to article
[11] I. Gessel and G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. Math., 58 (1985) 300–321.10.1016/0001-8708(85)90121-5
Search in Google Scholar Back to article
[12] I. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A, 53 (1990) 257–285.10.1016/0097-3165(90)90060-A
Search in Google Scholar Back to article
[13] S. Kitaev, Patterns in permutations and words, Springer-Verlag, 2011.10.1007/978-3-642-17333-2
Search in Google Scholar Back to article
[14] D. E. Knuth, The art of computer programming - Vol. 1, Addison-Wesley, Reading MA, 1973, Third edition, 1997.
Search in Google Scholar Back to article
[15] P. A. MacMahon, Combinatory Analysis. Vols. 1 and 2, Cambridge Univ. Press, Cambridge, UK, 1915 (reprinted by Chelsea, New-York, 1955).
Search in Google Scholar Back to article
[16] T. Mansour, Combinatorics of Set Partitions, Chapman & Hall/CRC, 2013.10.1201/b12691
Search in Google Scholar Back to article
[17] L. Pudwell, Enumeration schemes for permutations avoiding barred patterns, Electron. J. Combin., 17 (2010) #R29.10.37236/301
Search in Google Scholar Back to article
[18] R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin., 6 (1985) 383–406.10.1016/S0195-6698(85)80052-4
Search in Google Scholar Back to article
[19] N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, Published electronically at http://oeis.org/.
Search in Google Scholar Back to article
[20] R. P. Stanley, Enumerative Combinatorics - Vol. 1, Cambridge University Press, 1997.10.1017/CBO9780511805967
Search in Google Scholar Back to article
[21] J. West, Permutations with forbidden subsequences and stack-sortable permutations, Ph.D. Thesis, MIT, 1990.
Search in Google Scholar Back to article
[22] R. M. Wilson and J. H. Lint, A course in combinatorics - Vol. I, Cambridge University Press, 2002.
Search in Google Scholar Back to article

Forests and pattern-avoiding permutations modulo pure descents

Abstract

Paradigm

My account