Avoiding patterns in irreducible permutations - Archive ouverte HAL Access content directly
Journal Articles Discrete Mathematics and Theoretical Computer Science Year : 2016

Avoiding patterns in irreducible permutations

(1)
1

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.
Fichier principal
Vignette du fichier
2343-9853-1-PB.pdf (335.73 Ko) Télécharger le fichier
Origin : Explicit agreement for this submission
Loading...

Dates and versions

hal-01352852 , version 1 (16-08-2016)

Identifiers

Cite

Jean-Luc Baril. Avoiding patterns in irreducible permutations. Discrete Mathematics and Theoretical Computer Science, 2016, Vol. 17 no. 3 (3), pp.13-30. ⟨10.46298/dmtcs.2158⟩. ⟨hal-01352852⟩
253 View
766 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More