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

DOI10.1016/J.DISC.2013.12.007zbMATH Open1281.05006arXiv1208.1075OpenAlexW1980600661MaRDI QIDQ394358FDOQ394358

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

Publication date: 27 January 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

Dyck pathsMotzkin pathsbarred patternrestricted permutationsweak avoidance of barred patterns

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

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

Cited In (5)

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

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)