Classical and consecutive pattern avoidance in rooted forests

DOI10.1016/J.JCTA.2022.105699zbMATH Open1502.05004arXiv2005.08889OpenAlexW3025292272MaRDI QIDQ2102695FDOQ2102695

Authors: Swapnil Garg, Alan Peng 

Publication date: 29 November 2022

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

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.

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

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

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)

Cites Work

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

Cited In (4)

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

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)