Avoiding patterns in irreducible permutations
Jean-Luc Baril
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
σ(i+1)-σ(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 α for
α∈{132,213,321}. This induces
two new bijections between the set of Dyck paths and some restricted
sets of permutations.
Full Text: PDF