The Number of Occurrences of Patterns in a Random Tree or Forest Permutation

Abstract

The classes of tree permutations and forest permutations were defined by Acan and Hitczenko (2016). We study random permutations of a given length from these classes, and in particular the number of occurrences of a fixed pattern in one of these random permutations. The main results show that the distributions of these numbers are asymptotically normal.

The proof uses representations of random tree and forest permutations that enable us to express the number of occurrences of a pattern by a type of U-statistics; we then use general limit theorems for the latter.