Pattern avoidance in forests of binary shrubs

MaRDI QIDQ2831896zbMATH OpenFDO

Authors Derek Levin, Peter Nugent, Jay Pantone, Manda Riehl, M. L. Tlachac, David Bevan, Lara Pudwell

Publication date 3 November 2016

Published in Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.08036, https://dmtcs.episciences.org/1541/pdf

zbMATH Keywords

permutation patternslinear extensions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: We investigate pattern avoidance in permutations satisfying some additional restrictions. These are naturally considered in terms of avoiding patterns in linear extensions of certain forest-like partially ordered sets, which we call binary shrub forests. In this context, we enumerate forests avoiding patterns of length three. In four of the five non-equivalent cases, we present explicit enumerations by exhibiting bijections with certain lattice paths bounded above by the line $y=ellx$, for some $ellinmathbb{Q}^{+}$, one of these being the celebrated Duchon's club paths with $ell=2/3$. In the remaining case, we use the machinery of analytic combinatorics to determine the minimal polynomial of its generating function, and deduce its growth rate.

Recommendations

• Rooted forests that avoid sets of permutations
• Classical and consecutive pattern avoidance in rooted forests
• Pattern avoidance in binary trees
• Forests and pattern-avoiding permutations modulo pure descents
• Pattern avoidance in labelled trees

Cited in

(10)

• Pattern-avoiding binary trees -- generation, counting, and bijections
• Classical and consecutive pattern avoidance in rooted forests
• Stanley-Wilf limits for patterns in rooted labeled forests
• Pattern avoidance in k-ary heaps
• Combinatorial generation via permutation languages. VI: Binary trees
• On partially ordered patterns of length 4 and 5 in permutations
• Forests and pattern-avoiding permutations modulo pure descents
• Patterns in treeshelves
• Rises in forests of binary shrubs
• Wilf equivalences for patterns in rooted labeled forests

This page was built for publication: Pattern avoidance in forests of binary shrubs

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