Noncontiguous Pattern Containment in Binary Trees

Source abstract

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 n -leaf trees the same number of times. We give a functional equation for the multivariate generating function for number of n -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.