6533b7dcfe1ef96bd12734ea
RESEARCH PRODUCT
Avoiding patterns in irreducible permutations
Jean-luc Barilsubject
Motzkin pathFibonacci numberMathematics::CombinatoricsGeneral Computer ScienceSigmaBinary number[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]Fixed point[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]ConstructiveTheoretical Computer SciencesuccessionCombinatorics[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]irreducible permutationinvolutionDiscrete Mathematics and CombinatoricsBijection injection and surjectionPattern avoiding permutationMathematicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2016-01-18 |