Avoiding patterns in irreducible permutations

Abstract : We explore the classical pattern avoidance question in the case of irreducible permutations, i.e., those in which there is no index $i$ such that $\sigma (i+1) - \sigma (i)=1$. The problem is addressed completely in the case of avoiding one or two patterns of length three, and several well known sequences are encountered in the process, such as Catalan, Motzkin, Fibonacci, Tribonacci, Padovan and Binary numbers. Also, we present constructive bijections between the set of Motzkin paths of length $n-1$ and the sets of irreducible permutations of length $n$ (respectively fixed point free irreducible involutions of length $2n$) avoiding a pattern $\alpha$ for $\alpha \in \{132,213,321\}$. This induces two new bijections between the set of Dyck paths and some restricted sets of permutations.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.13-30
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01352852
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 16 août 2016 - 14:56:42
Dernière modification le : mercredi 13 décembre 2017 - 14:20:29
Document(s) archivé(s) le : jeudi 17 novembre 2016 - 10:31:25

Fichier

2343-9853-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01352852, version 1

Collections

Citation

Jean-Luc Baril. Avoiding patterns in irreducible permutations. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.13-30. 〈hal-01352852〉

Partager

Métriques

Consultations de la notice

126

Téléchargements de fichiers

104