Pattern avoidance in labelled trees

zbMATH Open1295.05204arXiv1110.0844MaRDI QIDQ658978FDOQ658978

Authors: Vladimir Dotsenko 

Publication date: 9 February 2012

Published in: Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Abstract: We discuss a new notion of pattern avoidance motivated by the operad theory: pattern avoidance in planar labelled trees. It is a generalisation of various types of consecutive pattern avoidance studied before: consecutive patterns in words, permutations, coloured permutations etc. The notion of Wilf equivalence for patterns in permutations admits a straightforward generalisation for (sets of) tree patterns; we describe classes for trees with small numbers of leaves, and give several bijections between trees avoiding pattern sets from the same class. We also explain a few general results for tree pattern avoidance, both for the exact and the asymptotic enumeration.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Pattern avoidance in binary trees
• Rooted forests that avoid sets of permutations
• Pattern avoidance in ternary trees
• Classical and consecutive pattern avoidance in rooted forests
• Non-contiguous pattern avoidance in binary trees

zbMATH Keywords

asymptotic enumerationplanar labelled trees

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Exact enumeration problems, generating functions (05A15) Planar graphs; geometric and topological aspects of graph theory (05C10) Asymptotic enumeration (05A16) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cited In (11)

• Non-contiguous pattern avoidance in binary trees
• Classical and consecutive pattern avoidance in rooted forests
• Periodicity vectors for labelled trees
• Consecutive pattern avoidances in non-crossing trees
• On the free Lie algebra with multiple brackets
• Combinatorial generation via permutation languages. VI: Binary trees
• Supertrees
• Pattern avoidance in binary trees
• Rooted forests that avoid sets of permutations
• Noncontiguous pattern containment in binary trees
• Enumeration of some classes of pattern avoiding matchings, with a glimpse into the matching pattern poset

Uses Software

• CAV
• BinaryTrees
• NAIVE
• DAVID_IAN
• JODO
• BLANKS
• SYMGJ
• SPGJ
• GJseries
• GJSAW
• GJsqfree

This page was built for publication: Pattern avoidance in labelled trees

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