Noncontiguous Pattern Containment in Binary Trees

We consider the enumeration of binary trees containing noncontiguous binary tree patterns. First, we show that any two -leaf binary trees are contained in the set of all -leaf trees the same number of times. We give a functional equation for the multivariate generating function for number of -leaf trees containing a specified number of copies of any path tree, and we analyze tree patterns with at most 4 leaves. The paper concludes with implications for pattern containment in permutations. 1. Introduction Pattern avoidance has been studied in a number of combinatorial objects including permutations, words, partitions, and graphs. In this paper, we consider such pattern questions in trees. Conceptually, tree avoids tree if there is no copy of anywhere inside . Pattern avoidance in vertex-labeled trees has been studied in various contexts by Steyaert and Flajolet [1], Flajolet et al. [2], Flajolet and Sedgewick [3], and Dotsenko [4] while Khoroshkin and Piontkovski [5] considered generating functions for general unlabeled tree patterns in a different setting. In 2010, Rowland [6] explored contiguous pattern avoidance in binary trees (i.e., rooted ordered trees in which each vertex has 0 or 2 children). He chose to work with binary trees because there is natural bijection between -leaf binary trees and -vertex trees. In 2012, Gabriel et al. [7] considered Rowland’s definition of tree pattern in ternary, and more generally in -ary, trees. The patterns in [6, 7] may be seen as parallel to consecutive patterns in permutations. In those papers, tree was said to contain tree as a (contiguous) pattern if was a contiguous, rooted, ordered, subtree of . In 2012, Dairyko et al. [8] considered noncontiguous patterns in binary trees in order to introduce a tree pattern analogue of classical permutation patterns. In particular, they showed that for any , any two -leaf noncontiguous binary tree patterns are avoided by the same number of -leaf trees and gave an explicit generating function for this enumeration. In this paper, we follow the definition of tree pattern in [8] to mirror the idea of classical pattern avoidance in permutations. However, instead of focusing on trees that do not contain tree pattern , we turn our attention to the number of trees with exactly copies of tree pattern , making pattern avoidance the special case where . Ultimately, we study the total number of copies of a given tree pattern in the set of all -leaf trees to mirror the work of Bóna in [9, 10] where he considers the total number of copies of a given permutation pattern of length 3 in