Combinatorial bijections from hatted avoiding permutations in $S_n(132)$ to generalized Dyck and Motzkin paths

Abstract

We introduce a new concept of permutation avoidance pattern called hatted pattern, which is a natural generalization of the barred pattern. We show the growth rate of the class of permutations avoiding a hatted pattern in comparison to barred pattern. We prove that Dyck paths with no peak at height $p$, Dyck paths with no $ud...du$ and Motzkin paths are counted by hatted pattern avoiding permutations in $\s_n(132)$ by showing explicit bijections. As a result, a new direct bijection between Motzkin paths and permutations in $\s_n(132)$ without two consecutive adjacent numbers is given. These permutations are also represented on the Motzkin generating tree based on the Enumerative Combinatorial Object (ECO) method.

19 pages, 9 figures

References in corpus (3)

• Two Bijections for Dyck Path Parameters
• On bijections between 231-avoiding permutations and Dyck paths
• Bijections from Dyck paths to 321-avoiding permutations revisited