### Abstract

**Q**

^{+}, one of these being the celebrated Duchon’s club paths with ℓ = 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.

Language | English |
---|---|

Number of pages | 22 |

Journal | Discrete Mathematics and Theoretical Computer Science |

Volume | 18 |

Issue number | 2 |

Publication status | Published - 21 Jul 2016 |

### Fingerprint

### Keywords

- pattern avoidance
- permutation patterns
- linear extensions

### Cite this

*Discrete Mathematics and Theoretical Computer Science*,

*18*(2).

}

*Discrete Mathematics and Theoretical Computer Science*, vol. 18, no. 2.

**Pattern avoidance in forests of binary shrubs.** / Bevan, David; Levin, Derek; Nugent, Peter; Pantone, Jay; Pudwell, Lara; Riehl, Manda; Tlachac, ML.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Pattern avoidance in forests of binary shrubs

AU - Bevan, David

AU - Levin, Derek

AU - Nugent, Peter

AU - Pantone, Jay

AU - Pudwell, Lara

AU - Riehl, Manda

AU - Tlachac, ML

PY - 2016/7/21

Y1 - 2016/7/21

N2 - 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 = ℓx , for some ℓ ∈ Q+ , one of these being the celebrated Duchon’s club paths with ℓ = 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.

AB - 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 = ℓx , for some ℓ ∈ Q+ , one of these being the celebrated Duchon’s club paths with ℓ = 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.

KW - pattern avoidance

KW - permutation patterns

KW - linear extensions

UR - https://dmtcs.episciences.org/

M3 - Article

VL - 18

JO - Discrete Mathematics and Theoretical Computer Science

T2 - Discrete Mathematics and Theoretical Computer Science

JF - Discrete Mathematics and Theoretical Computer Science

SN - 1365-8050

IS - 2

ER -