# Noncontiguous Pattern Containment in Binary Trees

Authors: Lara Pudwell; Connor Scholten; Tyler Schrock; Alexa Serrato
Journal: ISRN Combinatorics
 (2014)

---

## 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.


---

## Body

## 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, treeT avoids tree t if there is no copy of t anywhere inside T. 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 n-leaf binary trees and n-vertex trees. In 2012, Gabriel et al. [7] considered Rowland’s definition of tree pattern in ternary, and more generally in m-ary, trees.The patterns in [6, 7] may be seen as parallel to consecutive patterns in permutations. In those papers, tree T was said to contain tree t as a (contiguous) pattern if t was a contiguous, rooted, ordered, subtree of T. 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 n
,
ℓ
∈
ℤ
+, any two ℓ-leaf noncontiguous binary tree patterns are avoided by the same number of n-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 t, we turn our attention to the number of trees with exactly k copies of tree pattern t, making pattern avoidance the special case where k
=
0. Ultimately, we study the total number of copies of a given tree pattern in the set of all n-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 the set of all 132-avoiding permutations of length n.All trees in this paper are rooted and ordered. We will focus on full binary trees, that is, trees in which each vertex has 0 or 2 (ordered children). Two children with a common parent aresibling vertices. A vertex with no children is aleaf and a vertex with 2 children is aninternal vertex. A binary tree with n leaves has n
-
1 internal vertices, and the number of such trees is given by the nth Catalan number (OEIS A000108). For simplicity of computation, we adopt the convention that there are zero rooted binary trees with zero leaves. The first few binary trees are shown in Figure 1, with names that will be referred to throughout the paper.Figure 1
Binary trees with at most4 leaves.


## 2. Definitions and Notation

TreeT contains t as a (noncontiguous) tree pattern if t can be obtained from T via a finite sequence of edge contractions. Conversely, T avoids t if there is no sequence of edge contractions that produces t from T. For example, consider the three trees shown in Figure 2. T avoids t
4 as a contiguous pattern, but T contains t
4 noncontiguously (contract both dashed edges). On the other hand, T avoids t
6 both contiguously and noncontiguously since no vertex of T has a left child and a right child, both of which are internal vertices.Figure 2
Three binary trees.The definition of pattern in the previous paragraph is unambiguous for deciding the question “doesT contain t?” but becomes more complicated when determining “how many copies of t are in T?” To remove ambiguity, we make the convention that if an edge between a parent vertex and a child vertex is contracted, then the edge from the parent to its other child must be contracted simultaneously.Definet
r
t
(
n
,
k
) to be the number of n-leaf binary trees that contain exactly k copies of tree pattern t noncontiguously. For any tree T, let c
o
t
(
T
) be the number of copies of t in T. We write 𝕋
n for the set of n-leaf binary trees and 𝕋
=
∪
n
≥
1
𝕋
n. Further, let ℓ
(
t
) be the number of leaves of t. We are particularly interested in determining t
r
t
(
n
,
k
) for various choices of t, n, and k. To this end, we define
(1)
F
t
(
x
,
y
)
:
=
∑
T
∈
𝕋
‍
x
ℓ
(
T
)
y
c
o
t
(
T
)
=
∑
n
≥
1
∑
k
≥
0
‍
t
r
t
(
n
,
k
)
x
n
y
k
.
In [8], the authors were concerned with pattern avoidance, so they focused on t
r
t
(
n
,
0
). They showed the following enumeration.Theorem 1 (Dairyko et al. [8]).
Letℓ
∈
ℤ
+ and t be a binary tree pattern with ℓ leaves. Then
(2)
F
t
(
x
,
0
)
=
∑
n
≥
1
‍
tr
t
(
n
,
0
)
x
n
=
∑
i
=
0
⌊
(
ℓ
-
2
)
/
2
⌋
(
-
1
)
i
·
(
ℓ
-
(
i
+
2
)
i
)
·
x
i
+
1
∑
i
=
0
⌊
(
ℓ
-
1
)
/
2
⌋
(
-
1
)
i
·
(
ℓ
-
(
i
+
1
)
i
)
·
x
i
.Corollary 2 (Dairyko et al. [8]).
Fixℓ
∈
ℤ
+. Let t and s be two ℓ-leaf binary tree patterns. Then
(3)
F
t
(
x
,
0
)
=
F
s
(
x
,
0
)
.We obtain a parallel result to Corollary2 if we focus on
(4)
to
c
t
(
n
)
:
=
∑
k
=
1
∞
‍
k
·
t
r
t
(
n
,
k
)
=
∑
T
∈
𝕋
n
‍
c
o
t
(
T
)
.
We compute to
c
t
(
n
) for any tree t and n
∈
ℤ
+ in Section 3. In Section 4, we find a functional equation for F
t
(
n
,
k
) for any path tree (i.e., any tree avoiding t
6 in Figure 1), and in Section 5 we consider t
r
t
(
n
,
k
) for any tree pattern t with at most 4 leaves. Finally, in Section 6 we consider implications for pattern containment in permutations.


## 3. Total Number of Copies

In this section, we computeto
c
t
(
n
)
=
∑
k
=
1
∞
‍
k
·
t
r
t
(
n
,
k
)
=
∑
T
∈
𝕋
n
‍
c
o
t
(
T
), that is, the total number of occurrences of tree pattern t in 𝕋
n, for any tree pattern t and any positive integer n. Theorem 3 is parallel to a result of Steyaert and Flajolet [1]. They showed that the total number of occurrences of a (contiguous) ℓ-leaf binary tree pattern in all n-leaf binary trees is independent of the tree pattern and is (
2
n
-
ℓ
n
-
ℓ
). As it turns out, for noncontiguous tree patterns, we also have the following.Theorem 3.
Fixℓ
∈
ℤ
+. Let t and s be two ℓ-leaf binary tree patterns. Then
(5)
t
o
c
t
(
n
)
=
t
o
c
s
(
n
)
for
n
≥
0
.The fact thatto
c
t
(
n
)
=
to
c
s
(
n
) does not guarantee t
r
t
(
n
,
k
)
=
t
r
s
(
n
,
k
) for various choices of k. While Corollary 2 guarantees t
r
t
(
n
,
0
)
=
t
r
s
(
n
,
0
) and Theorem 3 guarantees ∑
k
=
1
∞
‍
k
·
t
r
t
(
n
,
k
)
=
∑
k
=
1
∞
‍
k
·
t
r
s
(
n
,
k
), it is often the case that t
r
t
(
n
,
k
)
≠
t
r
s
(
n
,
k
) when k
≥
1.In the following argument we give a bijective proof of Theorem3. Notice that this is a different approach from the proof of Theorem  1 in [8], which relies on algebraic manipulation of recurrences and generating functions.Since we are concerned withpairs
(
t
,
s
) of ℓ-leaf binary trees, we make some definitions allowing us to more precisely compare t and s. First, theintersection of trees t and s is the largest contiguous rooted tree that is contained in both t and s and includes the root vertex. For example, Figure 3 shows trees t
4 and t
6 along with their intersection.Figure 3
Two neighboring trees and their intersection; white vertices are breaking points.Twoℓ-leaf trees whose intersection has exactly ℓ
-
1 leaves are calledneighboring trees. Thus, t
4 and t
6 in Figure 3 are neighboring trees. On the other hand, t
4 and its left-right reflection t
4
r are nonneighboring since their intersection has only 2 leaves. By definition, if t and s are neighboring trees, then each of them has exactly two vertices that are not part of the intersection. Call the vertex on each tree that is the parent of the nonintersection vertices thebreaking point. For example, in Figure 2, the breaking point of t is the left child of the left child of the root. The breaking point of s is the right child of the root. In fact, since both t’s breaking point and s’s breaking point are part of their intersection, we can identify both breaking points on either of the original trees or on their intersection.Given neighboring treest and s, we define a map ϕ
t
,
s from the set of copies of t in 𝕋
n to the set of copies of s in 𝕋
n. If t appears noncontiguously, we may still identify a (possibly noncontiguous) copy of t
∩
s using only edges from that copy of t. The breaking points along this copy of t
∩
s are then uniquely determined.Given a copyc of t in a particular n-leaf tree, find both breaking points on the intersection and swap the subtrees that have the breaking points as their roots. We have now obtained an n-leaf tree with a unique copy of s that has the same intersection with c and the same breaking points. This copy of s is c
^
=
ϕ
t
,
s
(
c
). Figure 4 shows a copy of t
4 being mapped to a copy of t
6 via ϕ
t
4
,
t
6.Figure 4
An application ofϕ
t
4
,
t
6.Sincet and s are neighboring trees, it is clear that ϕ
t
,
s maps a copy of t to a copy of s. Further, ϕ
t
,
s
-
1
=
ϕ
s
,
t since ϕ
t
,
s only involves swapping two well-defined subtrees. Thus, ϕ
t
,
s is a bijection from the set of copies of t in 𝕋
n to the set of copies of s in 𝕋
n.The fact thatϕ
t
,
s is a bijection shows that Theorem 3 is true when t and s are neighboring trees. To show that the theorem holds in general we need the following lemma.Lemma 4.
Given twoℓ-leaf trees t and s, there is a finite sequence t
=
t
1, t
2
,
…
,
t
p
=
s of trees such that for any i, (1
≤
i
<
p), t
i and t
i
+
1 are neighboring trees.Proof.
Lett and s be nonneighboring ℓ-leaf binary trees whose intersection is a j-leaf tree. Clearly, j
≥
2 since both trees share the root vertex and its two children.
To obtaint
i
+
1 from t
i, remove a pair of leaves with a common parent from t
i that are not in the intersection of t
i and s and attach them to a leaf of t
i that is not a leaf of s. The new tree has a larger intersection with s. Repeat until the intersection has ℓ
-
1 leaves.Since any twoℓ-leaf tree patterns are a finite sequence of neighboring trees apart, we have that ϕ
t
p
-
1
,
s
∘
⋯
∘
ϕ
t
2
,
t
3
∘
ϕ
t
,
t
2 provides a bijection between all copies of t in 𝕋
n and all copies of s in 𝕋
n, so Theorem 3 is true.Theorem3 also generalizes naturally for copies of m-ary tree patterns within the set of all m-ary trees with n leaves. The definition of intersection and breaking points remains unchanged, and the swapping action of ϕ
t
,
s still applies. To find a sequence of neighboring trees, we need only to move collections of m vertices with a common parent instead of pairs, and the rest of the argument goes through as expected.Now that we know thatto
c
t
(
n
) is the same for all ℓ-leaf trees t, we define to
c
ℓ
(
n
)
=
to
c
t
(
n
) where t is an ℓ-leaf tree and compute to
c
ℓ
(
n
) in general.Our first proposition deals with the pathological case ofℓ
=
1.Proposition 5.
t
o
c
1
(
n
)
=
C
n
-
1 where C
n is the nth Catalan number.Proof.
There is exactly one way to contract all edges of a tree to produce the one-leaf tree. Since there is one copy of the one-leaf tree in any given binary tree and there areC
n
-
1 binary trees with n leaves, we see that there are C
n
-
1 copies of the one-leaf tree in 𝕋
n.Proposition 6.
t
o
c
2
(
n
)
=
(
n
-
1
)
C
n
-
1.Proof.
There is only one two-leaf tree and the number of copies of this tree in treeT is equal to the number of internal vertices of T, which is one less than the number of leaves of T. Since there are n
-
1 copies of the two-leaf tree in any n-leaf tree and there are C
n
-
1
n-leaf trees, to
c
2
(
n
)
=
(
n
-
1
)
C
n
-
1.More generally, we obtain the following recurrence forto
c
ℓ
(
n
).Proposition 7.
(6)
t
o
c
ℓ
(
n
)
=
2
∑
k
=
1
n
-
1
‍
C
k
-
1
t
o
c
ℓ
(
n
-
k
)
+
∑
k
=
1
n
-
1
‍
C
k
-
1
t
o
c
ℓ
-
1
(
n
-
k
)
.Proof.
Considerℓ-leaf tree pattern t. A copy of t in T can (a) be fully contained in the left subtree of T’s root, (b) be fully contained in the right subtree of T’s root, or (c) include T’s root.
For the first case, suppose thatT
^ is an (n
-
k)-leaf tree containing t. T
^ appears C
k
-
1 times as the left subtree of some n-leaf tree in 𝕋
n. Therefore, the number of times t that is fully contained in a left subtree of an n-leaf tree in 𝕋
n is ∑
k
=
1
n
-
1
‍
C
k
-
1
to
c
ℓ
(
n
-
k
). The same sum also counts the number of times t that is fully contained in a right subtree of an n-leaf tree in 𝕋
n.
If a copy oft includes the root of T, we must count copies of t’s left subtree to the left of the root and t’s right subtree to the right of the root. By Theorem 3, we may assume that t is the ℓ-leaf right comb, that is, the unique ℓ-leaf tree where every left child is a leaf. This means that the number of ways for an n-leaf tree to have a copy of t that includes the root is ∑
k
=
1
n
-
1
‍
C
k
-
1
to
c
ℓ
-
1
(
n
-
k
) where C
k
-
1 counts copies of the 1-leaf left subtree addressed in Proposition 5, and to
c
ℓ
-
1
(
n
-
k
) counts copies of the (ℓ
-
1)-leaf right comb in the right subtree.Fixℓ
∈
ℤ
+, and let t
ℓ
(
x
)
=
∑
i
=
1
∞
‍
to
c
ℓ
(
i
)
x
i. Then, using the recurrence of Proposition 7, we have that
(7)
t
ℓ
(
x
)
=
t
1
(
x
)
t
ℓ
-
1
(
x
)
1
-
2
t
1
(
x
)
.
We know from Proposition 5 that t
1
(
x
)
=
(
1
-
1
-
4
x
)
/
2, the generating function for the Catalan numbers, so by induction, we have
(8)
t
ℓ
(
x
)
=
(
-
1
2
)
ℓ
(
-
1
+
1
-
4
x
)
ℓ
(
1
-
4
x
)
ℓ
-
1
.
Moreover, the following theorem enumerates all copies of a given ℓ-leaf tree in 𝕋
n for any ℓ
,
n
∈
ℤ
+.Theorem 8.
Consider(9)
∑
n
≥
1
∑
ℓ
≥
1
‍
t
o
c
ℓ
(
n
)
x
n
y
ℓ
=
∑
ℓ
=
1
∞
‍
t
ℓ
(
x
)
y
ℓ
=
1
-
4
x
(
1
-
1
-
4
x
)
y
(
y
+
2
)
1
-
4
x
-
y
.Table1 gives values of to
c
ℓ
(
n
) for 1
≤
n
≤
10 and 1
≤
ℓ
≤
8. As expected, to
c
ℓ
(
n
)
=
0 if ℓ
>
n and to
c
n
(
n
)
=
1. It also follows that to
c
n
-
a
(
n
) is a polynomial in n of degree a. Further, to
c
1
(
n
) and to
c
2
(
n
) were given above. to
c
3
(
n
)
=
2
2
n
-
3
-
(
2
n
-
1
n
)
+
(
2
n
-
3
n
-
1
); this is entry A006419 in the Online Encyclopedia of Integer Sequences [11], which gives several other combinatorial interpretations. to
c
ℓ
(
n
) for ℓ
≥
4 appear to be new sequences to the literature.Table 1
toc
ℓ
(
n
) for small n and ℓ.
n
∖
ℓ
1
2
3
4
5
6
7
8
1
1
0
0
0
0
0
0
0
2
1
1
0
0
0
0
0
0
3
2
4
1
0
0
0
0
0
4
5
15
7
1
0
0
0
0
5
14
56
37
10
1
0
0
0
6
42
210
176
68
13
1
0
0
7
132
792
794
392
108
16
1
0
8
429
3003
3473
2063
731
157
19
1
9
1430
11440
14893
10254
4395
1220
215
22
10
4862
43758
63004
49024
24465
8249
1886
282


## 4. Pattern Containment of Path Trees

Now that we knowto
c
t
(
n
) for any ℓ-leaf tree, we turn our attention to computing t
r
t
(
n
,
k
) for particular tree patterns. In this section we give a functional equation for
(10)
F
t
(
x
,
y
)
=
∑
T
∈
𝕋
‍
x
ℓ
(
T
)
y
c
o
t
(
T
)
=
∑
n
≥
1
∑
k
≥
0
‍
t
r
t
(
n
,
k
)
x
n
y
k
for the case where t is a path tree, that is, t has no vertex which has both left and right grandchildren. Each ℓ-leaf path tree can be encoded uniquely by a word in {
L
,
R
}
ℓ
-
2. The two leaf tree is encoded by the empty word. For ℓ
>
2, consider w
=
w
1
,
…
,
w
ℓ
-
2
∈
{
L
,
R
}
ℓ
-
2, then w encodes the tree whose root’s right child is a leaf, and whose root's left child is the root of the subtree encoded by w
2
,
…
,
w
ℓ
-
2. Similarly, if w
1
=
R, w encodes the tree whose root’s left child is a leaf and whose root's right child is the root of the subtree encoded by w
2
,
…
,
w
ℓ
-
2. For a path tree t whose encoding is w
1
,
…
,
w
ℓ, the deletion d
(
t
) is the tree whose encoding is w
2
,
…
,
w
ℓ
-
2. Note that d
ℓ
-
2
(
t
) is the 2-leaf tree for any t
∈
𝕋
ℓ. Several iterations of the deletion map on the path tree with word encoding L
R
R
L are shown in Figure 5.Figure 5
The deletion map for path trees.Theorem 9.
Givenℓ-leaf path tree t, let
(11)
G
t
(
x
,
y
0
,
…
,
y
ℓ
-
2
)
=
∑
T
∈
𝕋
‍
x
ℓ
(
t
)
y
0
c
o
t
(
T
)
y
1
c
o
d
(
t
)
(
T
)
y
2
c
o
d
2
(
t
)
(
T
)
,
…
,
y
ℓ
-
2
c
o
d
ℓ
-
2
(
t
)
(
T
)
.
Then
(12)
G
t
(
x
,
y
0
,
…
,
y
ℓ
-
2
)
=
x
+
y
ℓ
-
2
G
t
(
x
,
y
0
,
p
1
y
1
,
…
,
p
ℓ
-
2
y
ℓ
-
2
)
×
G
t
(
x
,
y
0
,
q
1
y
1
,
…
,
q
ℓ
-
2
y
ℓ
-
2
)
,
where p
i
=
y
i
-
1 and q
i
=
1 if d
i
(
t
) is the left subtree of d
i
-
1
(
t
) and p
i
=
1 and q
i
=
y
i
-
1 if d
i
(
t
) is the right subtree of d
i
-
1
(
t
).Observe that settingy
1
=
y
2
=
⋯
=
y
ℓ
-
2
=
1 causes every catalytic variable to drop out, leaving F
t
(
x
,
y
)
=
G
t
(
x
,
y
,
1
,
…
,
1
).Proof.
In this generating function, the weightwt
(
T
) of a given tree T is wt
(
T
)
=
x
ℓ
(
t
)
y
0
c
o
t
(
T
)
y
1
c
o
d
(
t
)
(
T
)
y
2
c
o
d
2
(
t
)
(
T
)
⋯
y
ℓ
-
2
c
o
d
ℓ
-
2
(
t
)
(
T
). Clearly, for t
1, the one-leaf tree wt
(
t
1
)
=
x.
Now, for other treesT we see that each copy of some d
i
(
t
) (0
≤
i
≤
ℓ
-
2) either (a) is contained entirely in the left subtree of T, (b) is contained entirely in the left subtree of T, or (c) includes the root of T. The weight-enumerator for copies of d
i
(
t
) (0
≤
i
≤
ℓ
-
2) covered in cases (a) and (b) is G
t
(
x
,
y
0
,
y
1
,
…
,
y
ℓ
-
2
)
G
t
(
x
,
y
0
,
y
1
,
…
,
y
ℓ
-
2
). If the word representation of d
i
(
t
) begins with L, a copy of d
i
(
t
) including the root consists of the root, the two edges emanating from the root, and a copy of d
i
+
1
(
t
) in the left subtree of t. The p
i contributions keep track of copies of d
i
(
t
) formed in this way. Similarly, the q
i contributions keep track of copies of d
i
(
t
) that include the root of T when d
i
(
t
)’s word representation begins with R. The y
ℓ
-
2 factor keeps track of the copy of the two-leaf tree, t
2, that includes the root of T.For example, ift is the tree in Figure 5, we have
(13)
G
t
(
x
,
y
0
,
y
1
,
y
2
,
y
3
,
y
4
)
=
x
+
y
4
G
t
(
x
,
y
0
,
y
0
y
1
,
y
2
,
y
3
,
y
3
y
4
)
×
G
t
(
x
,
y
0
,
y
1
,
y
1
y
2
,
y
2
y
3
,
y
4
)
.For even larger trees, we obtain even more complicated functional equations which are hard to solve in general but straightforward to extract initial terms from via the computer.For nonpath trees, the interaction of the left and right subtrees ofT makes this computation more tedious. Analysis of G
t for for small path trees appears in the following section. A parallel argument holds for m-ary path tree containment, although it requires complicated notation for the p
i and q
i terms.


## 5. Pattern Containment of Small Trees

We have already seen that whent is the one-leaf tree, t
r
t
(
n
,
1
)
=
C
n
-
1 and t
r
t
(
n
,
k
)
=
0 if k
≠
1. Similarly, we know that when t is the two-leaf tree and n
≥
ℓ, then t
r
t
(
n
,
n
-
1
)
=
C
n
-
1 and t
r
t
(
n
,
k
)
=
0 if k
≠
n
-
1. If t
r is the left-right reflection of tree t, then t
r
t
r
(
n
,
k
)
=
t
r
t
r
(
n
,
k
) for any n and k since if tree T contains k copies of t, then T
r contains k copies of t
r. This means that we need only to consider one three-leaf tree (t
3 in Figure 1) and three different four-leaf trees (t
4, t
5, and t
6 in Figure 1) to completely classify tree patterns with at most four leaves.


### 5.1. Containing a 3-Leaf Tree

Following the result of Theorem9, we have that
(14)
G
t
3
(
x
,
y
0
,
y
1
)
=
x
+
y
1
G
t
3
(
x
,
y
0
,
y
0
y
1
)
G
t
3
(
x
,
y
0
,
y
1
)
,
and F
t
3
(
x
,
y
)
=
G
t
3
(
x
,
y
,
1
)
=
x
+
x
2
+
(
y
+
1
)
x
3
+
(
y
3
+
y
2
+
2
y
+
1
)
x
4
+
(
y
6
+
y
5
+
2
y
4
+
3
y
3
+
3
y
2
+
3
y
+
1
)
x
5
+
(
y
10
+
y
9
+
2
y
8
+
3
y
7
+
5
y
6
+
5
y
5
+
7
y
4
+
7
y
3
+
6
y
2
+
4
y
+
1
)
x
6
+
⋯.Several nice sequences quickly appear. In particular,(i)
as expected,t
r
t
3
(
n
,
0
)
=
1.
(ii)
t
r
t
3
(
n
,
1
)
=
n
-
2 for n
≥ (ogf x
2
/
(
1
-
x
)
2).
(iii)
t
r
t
3
(
n
,
2
)
=
(
i
-
2
2
) for n
≥
3 (OEIS A000217, ogf x
3
/
(
1
-
x
)
3).
(iv)
t
r
t
3
(
n
,
3
)
=
(
n
-
3
1
)
+
(
n
-
3
2
)
+
(
n
-
3
3
) for n
≥
3 (OEIS A004006, ogf x
3
(
1
-
x
+
x
2
)
/
(
1
-
x
)
4).Each of these formulas can be proved directly by case analysis. In general,t
r
t
3
(
n
,
k
) has a rational ordinary generating function with denominator (
x
-
1
)
k
+
1, but the numerator has increasingly many terms as k increases.


### 5.2.  Containing a 4-Leaf Tree

4-leaf trees provide the first opportunity to consider trees with an equal number of leaves that are not reflections of one another. We must consider three different tree patterns for a complete analysis. Two of these three trees fall under the scope of Theorem9.Fort
4, we have the functional equation
(15)
G
t
4
(
x
,
y
0
,
y
1
,
y
2
)
=
x
+
y
2
G
t
4
(
x
,
y
0
,
y
0
y
1
,
y
1
y
2
)
G
t
4
(
x
,
y
0
,
y
1
,
y
2
)
.Particular sequences are as follows.(i)
As expected,t
r
t
4
(
n
,
0
)
=
2
n
-
2 for n
≥
2.
(ii)
t
r
t
4
(
n
,
1
)
=
(
n
-
3
)
2
n
-
4 for n
≥
4 (OEIS A001787).
(iii)
t
r
t
4
(
n
,
2
)
=
(
n
-
4
)
(
n
-
1
)
2
n
-
7 for n
≥
5 (OEIS A001793).
(iv)
t
r
t
4
(
n
,
3
)
=
(
(
(
n
-
5
)
(
n
-
3
)
(
n
+
2
)
)
/
3
)
2
n
-
9 for n
≥
6 (OEIS A055585).t
r
t
4
(
n
,
k
) for k
≥
4 is new to the OEIS, but each of the sequences above is referenced as the number of 132-avoiding permutations of a given length containing a particular number of copies of the pattern 123. We will see more about this connection to pattern-avoiding permutations in Section 6.Fort
5, we have the functional equation
(16)
G
t
5
(
x
,
y
0
,
y
1
,
y
2
)
=
x
+
y
2
G
t
5
(
x
,
y
0
,
y
0
y
1
,
y
2
)
G
t
5
(
x
,
y
0
,
y
1
,
y
1
y
2
)
.Particular sequences are as follows.(i)
As expected,t
r
t
5
(
n
,
0
)
=
2
n
-
2 for n
≥
2.
(ii)
t
r
t
5
(
n
,
1
)
=
(
n
-
2
)
2
n
-
5 for n
≥
4 (OEIS A001792).t
r
t
5
(
n
,
k
) for k
≥
2 is new to the OEIS. t
r
t
5
(
n
,
1
) shows up in a number of combinatorial contexts from compositions to the game of Hex. Also, notice that t
r
t
4
(
n
,
k
)
≠
t
r
t
5
(
n
,
k
) when k
>
0.t
6 is not a path tree, and thus requires other techniques. If we consider the polynomial g
t
6
,
n
(
y
)
=
∑
T
∈
𝕋
n
‍
y
c
o
t
6
(
T
), we obtain the recursion below. Consider
(17)
g
t
6
,
n
(
y
)
=
{
1
,
n
=
1
∑
i
=
1
n
-
1
‍
y
(
i
-
1
)
(
n
-
i
-
1
)
g
t
6
,
i
(
y
)
g
t
6
,
n
-
i
(
y
)
,
otherwise
.
Here, i counts the number of leaves to the left of the root, y
(
i
-
1
)
(
n
-
i
-
1
) accounts for copies of t
6 including the root of T, and g
t
6
,
i
(
y
) (resp. g
t
6
,
n
-
i
(
y
)) accounts for copies of t
6 entirely contained in the left (resp. right) subtree of T.Particular sequences are as follows.(i)
As expected,t
r
t
6
(
n
,
0
)
=
2
n
-
2 for n
≥
2.
(ii)
t
r
t
6
(
n
,
1
)
=
2
n
-
4 for n
≥
4 (ogf x
3
/
(
1
-
2
x
)).
(iii)
t
r
t
6
(
n
,
2
)
=
2
n
-
3 for n
≥
5 (ogf 4
x
4
/
(
1
-
2
x
)).
(iv)
t
r
t
6
(
n
,
3
)
=
2
n
-
3 for n
≥
6 (ogf 8
x
5
/
(
1
-
2
x
)).
(v)
t
r
t
6
(
n
,
4
) has ogf (
16
x
6
+
6
x
4
)
/
(
1
-
2
x
).In fact, it is clear that for any fixedk and sufficiently large n, t
r
t
6
(
n
,
k
)
/
t
r
t
6
(
n
-
1
,
k
)
=
2. This is because there is a finite number of ways to arrange exactly k copies of t
6 before the only option is to take an (n
-
1)-leaf tree with k copies of t
6 and make it to be either the left subtree or the right subtree of a new n-leaf tree. The numerators of the ordinary generating functions for t
r
t
6
(
n
,
k
) for fixed k have increasingly many terms as k grows larger.Larger nonpath trees introduce additional difficulties. Counting copies of the left (resp. right) subtree oft
6 is equivalent to counting single vertices. Counting copies of a nonpath tree that includes the root is more complicated when either subtree is larger.We end this section with a conjecture. Further computational data suggests this is the case, but settling this question in general remains an open problem.Conjecture 10.
tr

t
(
n
,
k
)
=
tr

s
(
n
,
k
) for all k
≥
0 and n
≥
1 if and only if s
=
t
r.


## 5.1. Containing a 3-Leaf Tree

Following the result of Theorem9, we have that
(14)
G
t
3
(
x
,
y
0
,
y
1
)
=
x
+
y
1
G
t
3
(
x
,
y
0
,
y
0
y
1
)
G
t
3
(
x
,
y
0
,
y
1
)
,
and F
t
3
(
x
,
y
)
=
G
t
3
(
x
,
y
,
1
)
=
x
+
x
2
+
(
y
+
1
)
x
3
+
(
y
3
+
y
2
+
2
y
+
1
)
x
4
+
(
y
6
+
y
5
+
2
y
4
+
3
y
3
+
3
y
2
+
3
y
+
1
)
x
5
+
(
y
10
+
y
9
+
2
y
8
+
3
y
7
+
5
y
6
+
5
y
5
+
7
y
4
+
7
y
3
+
6
y
2
+
4
y
+
1
)
x
6
+
⋯.Several nice sequences quickly appear. In particular,(i)
as expected,t
r
t
3
(
n
,
0
)
=
1.
(ii)
t
r
t
3
(
n
,
1
)
=
n
-
2 for n
≥ (ogf x
2
/
(
1
-
x
)
2).
(iii)
t
r
t
3
(
n
,
2
)
=
(
i
-
2
2
) for n
≥
3 (OEIS A000217, ogf x
3
/
(
1
-
x
)
3).
(iv)
t
r
t
3
(
n
,
3
)
=
(
n
-
3
1
)
+
(
n
-
3
2
)
+
(
n
-
3
3
) for n
≥
3 (OEIS A004006, ogf x
3
(
1
-
x
+
x
2
)
/
(
1
-
x
)
4).Each of these formulas can be proved directly by case analysis. In general,t
r
t
3
(
n
,
k
) has a rational ordinary generating function with denominator (
x
-
1
)
k
+
1, but the numerator has increasingly many terms as k increases.


## 5.2.  Containing a 4-Leaf Tree

4-leaf trees provide the first opportunity to consider trees with an equal number of leaves that are not reflections of one another. We must consider three different tree patterns for a complete analysis. Two of these three trees fall under the scope of Theorem9.Fort
4, we have the functional equation
(15)
G
t
4
(
x
,
y
0
,
y
1
,
y
2
)
=
x
+
y
2
G
t
4
(
x
,
y
0
,
y
0
y
1
,
y
1
y
2
)
G
t
4
(
x
,
y
0
,
y
1
,
y
2
)
.Particular sequences are as follows.(i)
As expected,t
r
t
4
(
n
,
0
)
=
2
n
-
2 for n
≥
2.
(ii)
t
r
t
4
(
n
,
1
)
=
(
n
-
3
)
2
n
-
4 for n
≥
4 (OEIS A001787).
(iii)
t
r
t
4
(
n
,
2
)
=
(
n
-
4
)
(
n
-
1
)
2
n
-
7 for n
≥
5 (OEIS A001793).
(iv)
t
r
t
4
(
n
,
3
)
=
(
(
(
n
-
5
)
(
n
-
3
)
(
n
+
2
)
)
/
3
)
2
n
-
9 for n
≥
6 (OEIS A055585).t
r
t
4
(
n
,
k
) for k
≥
4 is new to the OEIS, but each of the sequences above is referenced as the number of 132-avoiding permutations of a given length containing a particular number of copies of the pattern 123. We will see more about this connection to pattern-avoiding permutations in Section 6.Fort
5, we have the functional equation
(16)
G
t
5
(
x
,
y
0
,
y
1
,
y
2
)
=
x
+
y
2
G
t
5
(
x
,
y
0
,
y
0
y
1
,
y
2
)
G
t
5
(
x
,
y
0
,
y
1
,
y
1
y
2
)
.Particular sequences are as follows.(i)
As expected,t
r
t
5
(
n
,
0
)
=
2
n
-
2 for n
≥
2.
(ii)
t
r
t
5
(
n
,
1
)
=
(
n
-
2
)
2
n
-
5 for n
≥
4 (OEIS A001792).t
r
t
5
(
n
,
k
) for k
≥
2 is new to the OEIS. t
r
t
5
(
n
,
1
) shows up in a number of combinatorial contexts from compositions to the game of Hex. Also, notice that t
r
t
4
(
n
,
k
)
≠
t
r
t
5
(
n
,
k
) when k
>
0.t
6 is not a path tree, and thus requires other techniques. If we consider the polynomial g
t
6
,
n
(
y
)
=
∑
T
∈
𝕋
n
‍
y
c
o
t
6
(
T
), we obtain the recursion below. Consider
(17)
g
t
6
,
n
(
y
)
=
{
1
,
n
=
1
∑
i
=
1
n
-
1
‍
y
(
i
-
1
)
(
n
-
i
-
1
)
g
t
6
,
i
(
y
)
g
t
6
,
n
-
i
(
y
)
,
otherwise
.
Here, i counts the number of leaves to the left of the root, y
(
i
-
1
)
(
n
-
i
-
1
) accounts for copies of t
6 including the root of T, and g
t
6
,
i
(
y
) (resp. g
t
6
,
n
-
i
(
y
)) accounts for copies of t
6 entirely contained in the left (resp. right) subtree of T.Particular sequences are as follows.(i)
As expected,t
r
t
6
(
n
,
0
)
=
2
n
-
2 for n
≥
2.
(ii)
t
r
t
6
(
n
,
1
)
=
2
n
-
4 for n
≥
4 (ogf x
3
/
(
1
-
2
x
)).
(iii)
t
r
t
6
(
n
,
2
)
=
2
n
-
3 for n
≥
5 (ogf 4
x
4
/
(
1
-
2
x
)).
(iv)
t
r
t
6
(
n
,
3
)
=
2
n
-
3 for n
≥
6 (ogf 8
x
5
/
(
1
-
2
x
)).
(v)
t
r
t
6
(
n
,
4
) has ogf (
16
x
6
+
6
x
4
)
/
(
1
-
2
x
).In fact, it is clear that for any fixedk and sufficiently large n, t
r
t
6
(
n
,
k
)
/
t
r
t
6
(
n
-
1
,
k
)
=
2. This is because there is a finite number of ways to arrange exactly k copies of t
6 before the only option is to take an (n
-
1)-leaf tree with k copies of t
6 and make it to be either the left subtree or the right subtree of a new n-leaf tree. The numerators of the ordinary generating functions for t
r
t
6
(
n
,
k
) for fixed k have increasingly many terms as k grows larger.Larger nonpath trees introduce additional difficulties. Counting copies of the left (resp. right) subtree oft
6 is equivalent to counting single vertices. Counting copies of a nonpath tree that includes the root is more complicated when either subtree is larger.We end this section with a conjecture. Further computational data suggests this is the case, but settling this question in general remains an open problem.Conjecture 10.
tr

t
(
n
,
k
)
=
tr

s
(
n
,
k
) for all k
≥
0 and n
≥
1 if and only if s
=
t
r.


## 6. Connections to Pattern-Avoiding Permutations

Several sequences obtained by counting trees that contain noncontiguous binary tree patterns are already known in the literature for pattern-containing permutations. In this section, we make the relationship between trees and permutations explicit.To this end, let𝒮
n denote the set of permutations of length n. As in the introduction, given π
∈
𝒮
n and ρ
∈
𝒮
k we say that π contains ρ as a pattern if there exist indices 1
≤
i
1
<
⋯
<
i
k
≤
n such that π
i
a
<
π
i
b if and only if ρ
a
<
ρ
b. Let 𝒮
n
(
Q
)
=
{
π
∈
𝒮
n
∣
∀
ρ
∈
Q
,
π avoid ρ
} and s
n
(
Q
)
=
|
𝒮
n
(
Q
)
|. For example, s
n
(
{
12
}
)
=
1 for n
≥
1 since the only way to avoid the pattern 12 is to be the decreasing permutation of length n. It is also well known that if ρ
∈
𝒮
3, then s
n
(
{
ρ
}
)
=
C
n where C
n is the nth Catalan number.The following theorem provides an initial relationship between pattern-avoiding trees and pattern-avoiding permutations that we seek to expand.Theorem 11 (Dairyko et al. [8]).
Lett be any binary tree pattern with k
≥
2 leaves. Then
(18)
tr

t
(
n
,
0
)
=
s
n
-
1
(
{
132,12
⋯
(
k
-
2
)
(
k
-
1
)
}
)
.In fact, a stronger statement is true. It is well known that the set of binary trees withn leaves is in bijection with the set of permutations of length n
-
1 which avoid the pattern 132.To see this, label the root of treet with the label n
-
1. Now, suppose that there are i internal vertices to the right of the root and (
n
-
i
-
2
) internal vertices to the left of the root. The i vertices on the right will receive labels from the set {
1
,
…
,
i
} and the vertices on the left will receive labels from the set {
i
+
1
,
…
,
n
-
2
}. For each subtree, give the root the largest available label and continue recursively until each internal vertex has been labeled.Now, there is a natural left-to-right ordering of the vertices oft; in particular, for each vertex v, all vertices in v’s left subtree are to the left of v and all vertices in v’s right subtree are to the right of v. Read the labels of the vertices from left to right to obtain a permutation π
∈
𝒮
n
-
1. Necessarily, π avoids 132 because all labels to the left of a given vertex have larger labels than all labels to the right.This correspondence between 132-avoiding permutations and binary trees is not new. If one ignores the leaves in our trees, the bijection given above is a symmetry of the correspondence between postorder-labeled trees with inorder-read permutations found in [12]. Further work connecting permutations to binary trees in the context of sorting can be found in [13–18].To make this result even stronger we turn tomesh patterns. Mesh patterns were introduced by Brändén and Claesson [19] in a search for more compact expressions for various permutation statistics. They were later generalized by Úlfarsson [20] to unify the results for permutation patterns used in characterizing Schubert varieties and in analyzing stack-sortability.The graph of permutationπ
=
π
1
⋯
π
n is obtained by plotting the points {
(
i
,
π
i
)
∣
1
≤
i
≤
n
} in the Cartesian plane. If π contains ρ
∈
𝒮
m as a classical pattern, as defined above, then the graph of π has m rows and m columns whose points appear in the same arrangement as the points in the graph of ρ.The graph of a mesh pattern is the graph of a classical permutation with some squares in the graph shaded. For example, the graph of 132 and the graph of a mesh pattern with underlying permutation pattern 132 are shown in Figure6. A copy of a mesh pattern is a copy of the underlying classical pattern but where no points appear in the shaded regions. A permutation is said to avoid a mesh pattern if it contains no copies of the mesh pattern. For example, the permutation 2413, whose graph is also shown in Figure 6, contains 132 as evidenced by the subsequence 243. However, 2413 avoids the mesh pattern shown because there is no copy of 132 where all gray regions are empty; in particular, the only copy of 132 is given by the subsequence 243, but the point for the digit 1 appears in the gray strip at the bottom of the mesh pattern.Figure 6
2413, 132, and a mesh pattern.The bijection above between binary trees and 132-avoiding permutations associates each tree with a classical permutation pattern in a natural way. However, sometimes the pattern corresponding to a particular tree may embed in a larger permutation without the tree pattern being embedded in the corresponding larger tree. For example, the permutations 3241, 3421, and 321 and their corresponding trees are shown in Figure7. Notice that while 3241 contains a copy of 321, the corresponding tree does not contain a copy of the 4-leaf right comb. Also, while 3421 contains precisely 2 copies of the permutation pattern 321, the corresponding tree only contains one copy of the 4-leaf right comb. We repair this discrepancy by associating trees with mesh patterns.Figure 7
The permutations 3241, 3421, and 321 with their corresponding trees.The discrepancy between tree patterns and permutation patterns occurs precisely when patternρ has a descent, that is, a pair of adjacent elements such that ρ
i
>
ρ
i
+
1. A descent in a permutation pattern can be embedded in a tree either as one vertex being the right child (or right descendant) of another vertex or as one vertex being in the left subtree and the other in the right subtree of a third vertex. For example, in Figure 7, when 3241 contains the permutation pattern 321, the descent 32 embeds with the 2 vertex as right child of the 3 vertex, while the descent 21 embeds in two separate subtrees of the 4 vertex.To prevent the split of a descent between two subtrees, we associate each tree pattern with a mesh permutation pattern in the following way.(1)
Given tree patternt, compute π
t, the permutation given by the vertex-labeling bijection above.
(2)
Construct the permutation graph ofπ
t.
(3)
For each descent inπ
t, shade all squares between and above the two points involved in the descent. Call the resulting mesh pattern π
t
^.Now, copies ofπ
t
^ in permutation π
T correspond precisely to copies of tree t in T since the possibility of splitting t between left and right subtrees, without using the root, is removed. Figure 8 shows this correspondence for the 4-leaf tree patterns and Figure 9 shows the correspondence for an even larger tree pattern.Figure 8
4-leaf tree patterns and their corresponding mesh patterns.Figure 9
A 9-leaf tree pattern and its corresponding mesh pattern.Now, using this map from tree patternst to mesh patterns π
t
^ we obtain the following stronger version of Theorem 11.Theorem 12.
Lett be any binary tree pattern with ℓ
≥
2 leaves. Then
(19)
tr

t
(
n
,
0
)
=
s
n
-
1
(
{
132
,
π
t
^
}
)
=
s
n
-
1
(
{
132,12
⋯
(
ℓ
-
2
)
(
ℓ
-
1
)
}
)
.In particular, this restatement gives a set ofC
ℓ Wilf-equivalent pattern sets of the form {
132
,
π
t
^
} for any integer ℓ, and furthermore, since the increasing pattern 12
…
(
ℓ
-
1
) corresponding to the ℓ-leaf left comb has no descents, each of these is pattern pairs equivalent to the classical pattern pair {
132,12
⋯
(
ℓ
-
1
)
}.We also obtain a stronger statement for pattern containment once we augment our current notation for permutation patterns. Because of the bijection between trees and 132-avoiding permutations, we are concerned with permutations in𝒮
n
(
{
132
}
). Now, let
(20)
a
n
,
k
(
q
)
=
{
π
∈
𝒮
n
(
{
132
}
)
∣
π
contains
exactly
k
copies
of
pattern
q
}
.
We saw above that a
n
-
1,0
(
π
t
^
)
=
t
r
t
(
n
,
0
). In fact, the correspondence given above yields the following result of which Theorem 11 is a special case.Theorem 13.
Lett be any binary tree pattern with ℓ
≥
2 leaves. Then tr

t
(
n
,
k
)
=
a
n
-
1
,
k
(
π
t
^
).Because of this correspondence,t
r
t
3
(
n
,
k
) counts 132-avoiding permutations with k copies of 12, t
r
t
4
(
n
,
k
) counts 132-avoiding permutations with k copies of 123, and so on.Further, Theorem3 causes us to revisit the question of the total number of copies of a given pattern within the set of all length n permutations. To this end, let A
n
(
q
) be the number of copies of pattern q in 𝒮
n
(
{
132
}
).Bóna [9, 10] shows that A
n
(
213
)
=
A
n
(
231
)
=
A
n
(
312
) and, for sufficiently large n, A
n
(
123
)
<
A
n
(
213
)
=
A
n
(
231
)
=
A
n
(
312
)
<
A
n
(
321
). In the context of tree patterns, we obtain the following corollary to Theorem 3.Corollary 14.
Given an integerℓ
∈
ℤ
+, there exist C
ℓ mesh patterns π
t
^ for which A
n
(
π
t
^
)
=
A
n
(
12
⋯
(
ℓ
-
1
)
)
=
t
o
c

t
(
n
).This corollary provides a hidden symmetry to Bóna’s result in that there is a mesh patternπ
t
^ associated with each 4-leaf tree t for which A
n
(
π
t
^
)
=
A
n
(
123
)
=
to
c
t
(
n
).



---

*Source: 316535-2014-03-24.xml*