Equivalence classes of permutations modulo descents and left-to-right maxima

Jean-Luc Baril; Armen Petrossian

doi:10.1515/puma-2015-0002

.blurhash-client-img { display: none !important; }

Equivalence classes of permutations modulo descents and left-to-right maxima

Pure Mathematics and Applications

Volume 25 (2015): Issue 1 (September 2015)

By: Jean-Luc Baril and Armen Petrossian

Open Access

|Oct 2015

Abstract

In a recent paper [2], the authors provide enumerating results for equivalence classes of permutations modulo excedances. In this paper we investigate two other equivalence relations based on descents and left-to-right maxima. Enumerating results are presented for permutations, involutions, derangements, cycles and permutations avoiding one pattern of length three.

References

[1] J.-L. Baril, Statistics-preserving bijections between classical and cyclic permutations, Inform. Process. Lett., 113 (2003) 17-22.10.1016/j.ipl.2012.10.003
Search in Google Scholar
[2] 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
[3] M. Bona, Combinatorics of permutations, Chapman and Hall/CRC, Second Edition, 2012.
Search in Google Scholar
[4] E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001) 241-265.10.1016/S0012-365X(01)00121-2
Search in Google Scholar
[5] D. C. Foata and M. P. Schützenberger, Théorie Géométrique des Polynômes Euleriens, Lecture Notes in Math., 138, Springer-Verlag, Berlin, 1970.10.1007/BFb0060799
Search in Google Scholar
[6] O. Guibert, E. Pergola and R. Pinzani, Vexillary involutions are enumerated by Motzkin numbers, Ann. Comb., 5 (2001) 153-174.10.1007/PL00001297
Search in Google Scholar
[7] S. Kitaev, Patterns in permutations and words, Springer-Verlag, 2011.10.1007/978-3-642-17333-2
Search in Google Scholar
[8] D. E. Knuth, The art of computer programming, Volume I, Addison-Wesley, Reading MA, Third edition, 1997.
Search in Google Scholar
[9] C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. in Appl. Math., 27 (2001) 510-530.10.1006/aama.2001.0747
Search in Google Scholar
[10] T. Mansour, Combinatorics of Set Partitions, Discrete Mathematics and its Applications, Chapman & Hall/CRC, 2013.10.1201/b12691
Search in Google Scholar
[11] T. Mansour, Permutations avoiding a pattern from Sk and at least two patterns from S3, Ars. Combin., 62 (2002) 227-239.
Search in Google Scholar
[12] T. Mansour and A. Vainshtein, Restricted 132-avoiding permutations, Adv. Appl. Math., 26 (2001) 258-269.10.1006/aama.2000.0719
Search in Google Scholar
[13] 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
[14] J. West, Permutations with forbidden subsequences and stack-sortable permutations, Ph.D. Thesis, MIT, 1990.
Search in Google Scholar
[15] J. West, Generating trees and forbidden subsequences, Local Proceedings of FPSAC 1994, 441-450.
Search in Google Scholar
[16] J. West, Generating trees and the Catalan and Schröder numbers, Discrete Math., 146 (1995) 247-262.
Search in Google Scholar
[17] A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007) 2909-2924.
Search in Google Scholar
[18] N.J.A. Sloane, On-Line Encyclopedia of Integer Sequences, http://oeis.org/.
Search in Google Scholar
[19] R. P. Stanley, Enumerative Combinatorics, Volume I, Cambridge University Press, 2002.
Search in Google Scholar

Articles in this issue

DOI: https://doi.org/10.1515/puma-2015-0002 | Journal eISSN: 1788-800X

Journal RSS Feed

Language: English

Page range: 19 - 29

Submitted on: Jul 8, 2014

Published on: Oct 7, 2015

Published by: Corvinus University of Budapest

In partnership with: Paradigm Publishing Services

Publication frequency: 4 issues per year

Keywords:

permutation,

equivalence class,

descent,

left-to-right maximum,

pattern,

Related subjects:

Theoretical computer sciences,

Business and economics,

Mathematics and statistics for economists,

Mathematics,

Analysis,

Differential equations and dynamical systems

© 2015 Jean-Luc Baril, Armen Petrossian, published by Corvinus University of Budapest
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 25 (2015): Issue 1 (September 2015)