Permutations weakly avoiding barred patterns and combinatorial bijections to generalized Dyck and Motzkin paths

DOI10.1016/J.DISC.2013.12.007MaRDI QIDQ394358zbMATH OpenOpenAlexFDO

Authors Phan Thuan Do, Dominique Rossin, Thi Thu Huong Tran

Publication date 27 January 2014

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.1075

zbMATH Keywords

Dyck pathsMotzkin pathsbarred patternrestricted permutationsweak avoidance of barred patterns

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

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\mathrm{...}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.

Recommendations

• Permutations with restricted patterns and Dyck paths
• Dyck paths and restricted permutations
• Motzkin paths and reduced decompositions for permutations with forbidden patterns
• scientific article; zbMATH DE number 2245581
• Pattern avoidance in permutations: Linear and cyclic orders

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• Classical sequences revisited with permutations avoiding dotted pattern
• Classification of bijections between 321- and 132-avoiding permutations
• Dyck path enumeration
• Dyck paths with no peaks at height \(k\)
• ECO-generation for \(p\)-generalized Fibonacci and Lucas permutations
• Enumerating permutations avoiding three Babson-Steingrímsson patterns
• Enumeration schemes for permutations avoiding barred patterns
• Excluded permutation matrices and the Stanley-Wilf conjecture
• From Motzkin to Catalan permutations
• Generalized permutation patterns and a classification of the Mahonian statistics
• Generating trees and the Catalan and Schröder numbers
• On bijections between 231-avoiding permutations and Dyck paths
• Permutations with restricted patterns and Dyck paths
• Restricted permutations
• Restricted permutations and the wreath product

Cited in

(6)

• Dyck paths and restricted permutations
• Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths
• Cycles in the graph of overlapping permutations avoiding barred patterns
• Classical sequences revisited with permutations avoiding dotted pattern
• Combinatorial generation via permutation languages. I: Fundamentals
• Dyck paths, binary words, and Grassmannian permutations avoiding an increasing pattern

This page was built for publication: Permutations weakly avoiding barred patterns and combinatorial bijections to generalized Dyck and Motzkin paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q394358)