### 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 = ℓ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.Original language | English |
---|---|

Number of pages | 22 |

Journal | Discrete Mathematics and Theoretical Computer Science |

Volume | 18 |

Issue number | 2 |

Publication status | Published - 21 Jul 2016 |

### Keywords

- pattern avoidance
- permutation patterns
- linear extensions

## Fingerprint Dive into the research topics of 'Pattern avoidance in forests of binary shrubs'. Together they form a unique fingerprint.

## Cite this

Bevan, D., Levin, D., Nugent, P., Pantone, J., Pudwell, L., Riehl, M., & Tlachac, ML. (2016). Pattern avoidance in forests of binary shrubs.

*Discrete Mathematics and Theoretical Computer Science*,*18*(2). https://dmtcs.episciences.org/1541