Consecutive permutation patterns in trees and mappings

We initiate an enumerative study of consecutive permutation patterns in rooted labelled trees by analysing the number of trees of a certain size that avoid a single consecutive permutation pattern of length $3$, and the corresponding number of trees that contain this pattern a specified number of times. Using a generating functions approach based on combinatorial decompositions with respect to the node with smallest label in the tree, we are able to characterize for all three classes of permutation patterns of length $3$ the corresponding generating functions solutions. Via methods of analytic combinatorics applied to these generating functions we can provide asymptotic results for the number of trees avoiding a certain pattern and central limit theorems for the number of occurrences of a pattern. Moreover, we extend our analysis from trees to mappings and carry out corresponding enumerative studies concerning avoidance and occurrence of a single consecutive permutation pattern of length $3$ for functional digraphs of mappings $f : {\lbrace 1, \dotsc , n \rbrace} \to {\lbrace 1, \dotsc , n \rbrace}$. Close connections between the study of certain patterns in trees and mappings are also shown bijectively.

Keywords

permutation patterns, labelled trees, mappings, generating functions, asymptotic enumeration

2010 Mathematics Subject Classification

Primary 05A15, 05C05. Secondary 05C30.

Full Text (PDF format)

Received 11 July 2019

Accepted 22 January 2020

Published 4 January 2021