Permutations Avoiding Bipartite Partially Ordered Patterns Have a Regular Insertion Encoding

Bean, Christian; Nadeau, Émile; Pantone, Jay; Ulfarsson, Henning

Abstract

We prove that any class of permutations defined by avoiding a partially ordered pattern (POP) with height at most two has a regular insertion encoding and thus has a rational generating function. Then, we use Combinatorial Exploration to find combinatorial specifications and generating functions for hundreds of other permutation classes defined by avoiding a size 5 POP, allowing us to resolve several conjectures of Gao and Kitaev (2019) and of Chen and Lin (2024).

Citation

Bean, C., Nadeau, É., Pantone, J., & Ulfarsson, H. (2024). Permutations Avoiding Bipartite Partially Ordered Patterns Have a Regular Insertion Encoding. The Electronic Journal of Combinatorics, 31(3), Article P3.3. https://doi.org/10.37236/12686

• Journal Article Type: Article
• Acceptance Date: Apr 8, 2024
• Online Publication Date: Jul 12, 2024
• Publication Date: Jul 12, 2024
• Deposit Date: Aug 21, 2024
• Journal: The Electronic Journal of Combinatorics
• Print ISSN: 1077-8926
• Publisher: Electronic Journal of Combinatorics
• Peer Reviewed: Peer Reviewed
• Volume: 31
• Issue: 3
• Article Number: P3.3
• DOI: https://doi.org/10.37236/12686
• Public URL: https://keele-repository.worktribe.com/output/886934
• Publisher URL: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v31i3p3