Jean-Luc Baril - Avoiding patterns in irreducible permutations

dmtcs:2158 - Discrete Mathematics & Theoretical Computer Science, January 18, 2016, Vol. 17 no. 3 -
Avoiding patterns in irreducible permutationsArticle

Authors: Jean-Luc Baril 1

  • 1 Laboratoire Electronique, Informatique et Image [UMR6306]

We explore the classical pattern avoidance question in the case of irreducible permutations, <i>i.e.</i>, 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.

Volume: Vol. 17 no. 3
Section: Combinatorics
Published on: January 18, 2016
Submitted on: January 17, 2013
Keywords: Motzkin path, involution,Pattern avoiding permutation, irreducible permutation, succession,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 577 times.
This article's PDF has been downloaded 589 times.