Classical and consecutive pattern avoidance in rooted forests

DOI10.1016/J.JCTA.2022.105699MaRDI QIDQ2102695zbMATHOpenAlexFDO

Authors Swapnil Garg, Alan Peng

Publication date 29 November 2022

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.08889

zbMATH Keywords

pattern avoidanceenumerative combinatoricsrooted forestscluster methodforest-Young diagram

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Exact enumeration problems, generating functions (05A15)

Abstract: Following Anders and Archer, we say that an unordered rooted labeled forest avoids the pattern $sigmainmathcal{S}_k$ if in each tree, each sequence of labels along the shortest path from the root to a vertex does not contain a subsequence with the same relative order as $sigma$. For each permutation $sigmainmathcal{S}_{k-2}$, we construct a bijection between $n$-vertex forests avoiding $(sigma)(k-1)k:=sigma(1)cdotssigma(k-2)(k-1)k$ and $n$-vertex forests avoiding $(sigma)k(k-1):=sigma(1)cdotssigma(k-2)k(k-1)$, giving a common generalization of results of West on permutations and Anders--Archer on forests. We further define a new object, the forest-Young diagram, which we use to extend the notion of shape-Wilf equivalence to forests. In particular, this allows us to generalize the above result to a bijection between forests avoiding $(sigm{a}_1)k(k-1),(sigm{a}_2)k(k-1),dots,(sigm{a}_{e}ll)k(k-1)$ and forests avoiding $(sigm{a}_1)(k-1)k,(sigm{a}_2)(k-1)k,dots,(sigm{a}_{e}ll)(k-1)k$ for $sigm{a}_1,dots,sigm{a}_{e}llinmathcal{S}_{k-2}$. Furthermore, we give recurrences enumerating the forests avoiding $123cdotsk$, $213$, and other sets of patterns. Finally, we extend the Goulden--Jackson cluster method to study consecutive pattern avoidance in rooted trees as defined by Anders and Archer. Using the generalized cluster method, we prove that if two length-$k$ patterns are strong-c-forest-Wilf equivalent, then up to complementation, the two patterns must start with the same number. We also prove the surprising result that the patterns $1324$ and $1423$ are strong-c-forest-Wilf equivalent, even though they are not c-Wilf equivalent with respect to permutations.

Recommendations

• Pattern avoidance in forests of binary shrubs
• Consecutive pattern avoidances in non-crossing trees
• Pattern avoidance in labelled trees
• Pattern avoidance in binary trees
• Non-contiguous pattern avoidance in binary trees
• Rooted forests that avoid sets of permutations
• Pattern avoidance in ternary trees
• The Distribution of Patterns in Random Trees
• Periodic behavior on trees
• Patterns in trees

Cites work

• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A new class of Wilf-equivalent permutations
• An Inversion Theorem for Cluster Decompositions of Sequences with Distinguished Subsequences
• Clusters, generating functions and asymptotics for consecutive patterns in permutations
• Consecutive patterns in permutations
• Constraining strong \(c\)-Wilf equivalence using cluster poset asymptotics
• Counting 1324-avoiding permutations
• Dyck tilings, increasing trees, descents, and inversions
• Increasing trees and alternating permutations
• Pattern avoidance in binary trees
• Pattern avoidance in poset permutations
• Restricted permutations
• Rooted forests that avoid sets of permutations
• Wilf equivalence relations for consecutive patterns
• Wilf-equivalence for singleton classes

Cited in

(6)

• Pattern avoidance in forests of binary shrubs
• Stanley-Wilf limits for patterns in rooted labeled forests
• Pattern avoidance in labelled trees
• Forests and pattern-avoiding permutations modulo pure descents
• Wilf equivalences for patterns in rooted labeled forests
• Dyck paths, binary words, and Grassmannian permutations avoiding an increasing pattern

Describes a project that uses

Uses Software

• OEIS
• BinaryTrees

This page was built for publication: Classical and consecutive pattern avoidance in rooted forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2102695)