Back to Search
Start Over
Pattern avoidance in forests of binary shrubs
- Source :
- University of Strathclyde, Scopus-Elsevier, NASA Astrophysics Data System
-
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=\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.
- Subjects :
- Discrete mathematics
General Computer Science
Binary number
Theoretical Computer Science
Combinatorics
Lattice (order)
FOS: Mathematics
Enumeration
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Analytic combinatorics
Combinatorics (math.CO)
QA
Bijection, injection and surjection
Partially ordered set
Mathematics
Subjects
Details
- ISSN :
- 13658050
- Database :
- OpenAIRE
- Journal :
- University of Strathclyde, Scopus-Elsevier, NASA Astrophysics Data System
- Accession number :
- edsair.doi.dedup.....da7f4b3ae10d31e5c214db7a485223ee