Journal of Combinatorics

Volume 12 (2021)

Number 1

Consecutive permutation patterns in trees and mappings

Pages: 17 – 54

DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n1.a2

Author

Alois Panholzer (Institut für Diskrete Mathematik und Geometrie, Technische Universität Wien, Austria)

Abstract

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.

Received 11 July 2019

Accepted 22 January 2020

Published 4 January 2021