Noncontiguous pattern containment in binary trees (Q2449274)

Summary: We consider the enumeration of binary trees containing noncontiguous binary tree patterns. First, we show that any two \(\ell\)-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.