David Bevan ; Derek Levin ; Peter Nugent ; Jay Pantone ; Lara Pudwell et al. - Pattern avoidance in forests of binary shrubs

dmtcs:1322 - Discrete Mathematics & Theoretical Computer Science, July 21, 2016, Vol. 18 no. 2, Permutation Patterns 2015 - https://doi.org/10.46298/dmtcs.1322
Pattern avoidance in forests of binary shrubsArticle

Authors: David Bevan ORCID; Derek Levin ; Peter Nugent ORCID; Jay Pantone ; Lara Pudwell ; Manda Riehl ; ML Tlachac ORCID

    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=\ell x$, for some $\ell\in\mathbb{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.


    Volume: Vol. 18 no. 2, Permutation Patterns 2015
    Section: Permutation Patterns
    Published on: July 21, 2016
    Submitted on: July 21, 2016
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 1035 times.
    This article's PDF has been downloaded 790 times.