Séminaire Lotharingien de Combinatoire 67 (2012), Article B67b

PATTERN AVOIDANCE IN LABELLED TREES

VLADIMIR DOTSENKO

Abstract. We discuss a new notion of pattern avoidance motivated by operad theory: pattern avoidance in planar labelled trees. It is a generalisation of various types of consecutive pattern avoidance studied before: consecutive patterns in words, permutations, coloured permutations, etc. The notion of Wilf equivalence for patterns in permutations admits a straightforward generalisation for (sets of) tree patterns; we describe classes for trees with small numbers of leaves, and give several bijections between trees avoiding pattern sets from the same class. We also explain a few general results for tree pattern avoidance, both for exact and asymptotic enumeration.

1. Introduction

For pattern avoidance in words, apart from the “real word interpretation” (enumerate words not containing any “obscene” subwords), the pattern avoidance problem arises from studying (noncommutative) algebras with monomial relations. For example, describing words in the alphabet {A, B, …, Z} not containing the word FCUK as a subword is equivalent to figuring out which monomials in generators x_{1}, …, x_{26} form a basis in the algebra 𝕜⟨x_{1}, …, x_{26} | x_{6}x_{3}x_{21}x_{11} = 0⟩. The significance of algebras with monomial relations is, in turn, explained by the theory of Gröbner bases, which gives a method of finding a “monomial replacement” for every algebra with monomial relations [40]. Similarly, consecutive pattern avoidance in permutations [2, 5] and coloured permutations [29] can be interpreted in terms of shuffle algebras with monomial relations [9]. The goal of this paper is to introduce to the combinatorics audience a new notion of pattern avoidance naturally arising when studying operads. Operads are similar to associative algebras, but while associative algebras and groups capture the kind of associativity that one observes when composing transformations of some set, operads capture the associativity exhibited when composing operations with several arguments. The property of an operation of having more than one argument results in a choice that is not present in the choice of algebras: one may either assume that our operations do not possess any symmetries or allow symmetries in the picture. In the former case, the pattern avoidance in question is the pattern avoidance in planar rooted trees; a few papers, both of combinatorial spirit [1, 33, 36, 13] and operads-inspired [28] have been dealing with the arising questions of enumeration. In the case of operations with symmetries, the corresponding notion has not been studied before, and this paper is an attempt to give an elementary introduction to the arising research area. The “right” notion of a monomial relation for operations with symmetries is not as obvious as one might think: the action of symmetries makes every relation have too many consequences, and the arising class of “operads with monomial relations” appears to be far too narrow to be truly interesting or useful. The way to define monomial relations which avoids narrowing down matters, and which in particular led to a theory of operadic Gröbner bases, was suggested in [8]; the corresponding algebraic object is called a shuffle operad. In this paper we, however, shall try to concentrate on the combinatorial aspects of the subject, touching the algebraic aspects only briefly; for details on the algebraic aspects, see, for example, [6, 7, 8]. Though we attempt to keep this article relatively self-contained, familiarity with the key results of the theory of consecutive pattern avoidance in permutations could be useful; for relevant historical information on pattern avoidance as well as the state-of-art of this area the reader is referred to the recent monograph [24].

There are several types of questions in the theory of tree patterns which are meaningful from the operadic viewpoint. First of all, for a given set of patterns, exact enumeration results for trees avoiding that set are very important. Some examples of that sort appear in the following sections; in many cases the corresponding sequences of numbers are well known in combinatorics, but in many other cases one ends up with sequences that appear to be unrelated to classical enumeration problems. Second, there is the question of asymptotic enumeration. We shall prove some results of that sort relying on the Golod–Shafarevich technique [17] (which has recently been rediscovered in relation to combinatorics of pattern avoidance [3, 4, 35]). Also, there is a question of recognising the class of generating functions arising in this type of enumerating questions. However, while for word avoidance the answer is that the generating functions arising as answers for enumerating the avoidance of finite sets of words are always rational, even for consecutive pattern avoidance in permutations the class of arising generating functions does not have a satisfactory description. The answer is known if one ignores the leaf labels completely; in that case, the generating functions are algebraic (as proved in [36] in the case of binary trees, in [13] in the case of ternary trees, and in [22] in the general case). For the notion of tree pattern avoidance discussed here, it follows from one of the theorems of [22] that under some additional assumptions on the set of patterns (“shuffle regularity”) the generating functions for tree pattern avoidance are differentially algebraic (i.e., satisfy algebraic differential equations with polynomial coefficients). Finally, it is interesting to enumerate the Wilf equivalence classes of sets of tree patterns^{1}, and we discuss some basic results of this kind.

This paper is organised as follows. In Section 2, we define planar labelled rooted trees and tree patterns, and we show that this notion includes the classical types of consecutive pattern avoidance as particular cases. In Section 3, we present some results on asymptotics for tree pattern avoidance, and we introduce the notion of growth rate for a given set of patterns. In Section 4, we formulate an exact enumeration result on tree pattern avoidance which follows from our work with Khoroshkin [7], and we discuss some consequences of that result and related questions. Finally, in Section 5 we discuss various examples of patterns with small numbers of leaves. Each of these sections also contains some conjectures and natural questions that are beyond the scope of this paper. We also included an appendix explaining how pattern avoidance in trees arises in the operadic context.

Acknowledgements. I wish to thank Anton Khoroshkin and Dmitri Piontkovski for sending me a copy of their forthcoming preprint [22].

2. Planar labelled tree patterns

2.1. Tree patterns. Trees have vertices and edges. A rooted tree is a tree with a distinguished vertex, called the root. A rooted tree can be directed “away from the root”; this way every vertex except for the root has exactly one parent. Vertices whose common parent is a given vertex v are called children of v. Vertices that have at least one child are called internal, vertices with no children are called leaves. A planar rooted tree is a rooted tree together with a total order on the set of children of each vertex, we shall think of it as of embedded in the plane, the children of each vertex placed in increasing order from left to right.

Throughout the paper, X = ⨆ _{n≥2} X_{n} is a finite alphabet represented as a disjoint union of its subsets X_{n}, n ≥ 2.

Definition 1. A planar X-labelled rooted tree is a planar rooted tree T with no internal vertices having exactly one child, and with a labelling of all vertices fulfilling the following restrictions:

- every internal vertex v with m children is labelled by an element x_{v} ∈ X_{m};

- every leaf of T is labelled by a positive integer in such a way that the following two conditions are satisfied:

1Equivalence classes for “strong equivalence” might lead to interesting combinatorial results as well, but are much less natural from the operad point of view.

(1) (labelling set condition) the leaf labels are in one-to-one correspondence with the set [l] = {1, 2, …, l} (where l is the number of leaves of T);

(2) (local increasing condition) if we temporarily assign to each internal vertex v the smallest of the labels of leaves that are descendants of v in T (thus every vertex of T, should it be an internal vertex or a leaf, has an integer assigned to it), then for each internal vertex i the integers assigned to its children increase from left to right.

Notation: for i ≥ 0, l ≥ 1 we denote by LT _{i,l}(X) the set of planar X-labelled rooted trees with i internal vertices and l leaves,

(1)  LT _{l}(X) = ⋃_{i≥0} LT _{i,l}(X)

is the set of planar X-labelled rooted trees with l leaves,

(2)  LT (X) = ⋃_{i≥0,l≥1} LT _{i,l}(X)

is the set of all planar X-labelled rooted trees. In particular, LT _{0,l}(X) is non-empty only for l = 1 (and in that case it consists of exactly one element, a one-vertex tree with no edges), and LT _{1}(X) = LT _{0,1}(X) (since every internal vertex has at least two children, hence in the presence of an internal vertex we end up with at least two leaves).

Example 1. Let X = X_{2} = {∘, •}. The following tree is in LT _{7,8}(X):

(3)  _{•}^{∘}^{•}  ^{∘}^{∘}  ^{∘}  ^{∘}^{1} ^{3} ^{2} ^{7} ^{4} ^{6}^{5}  ^{8} .

A tree T is said to be a left (right) comb if for every internal vertex of T only its leftmost (rightmost) child may not be a leaf. Note that the local increasing condition makes the notions of “left” and “right” very different: for example, if a planar rooted tree t is a left comb, the only restriction on the leaf labels is that the leftmost leaf of t is labelled by 1; by contrast, if t is a right comb, there is only one leaf labelling satisfying the local increasing condition.

Most of the time throughout the paper we consider only the case X = X_{d}, thus assuming that for our trees all internal vertices have the same number of children (that is, d children). This assumption is mostly technical (it allows for closed formulas in various statements), in particular, all the asymptotic results we prove and conjecture in Section 3 are expected to be true in full generality. One particular simplification is that for such trees the number of internal vertices and the number of leaves are related: every tree with k internal vertices has kd − k + 1 leaves.

Let us prove a basic enumerative result which will be useful later.

Proposition 1. For X = X_{d}, we have

(4)  |LT _{kd−k+1}(X)| = |X_{d}|^{k} \frac{(kd)!}{(d!)^{k} · k!}.

Proof.For our purposes it is useful to consider, along with planar X-labelled rooted trees, two other types of trees. We denote by \overline{T}_{n}(X) the set of planar rooted trees with n leaves whose internal vertices are labelled by X, and by T_{n}(X) the set of planar rooted trees with n leaves whose internal vertices are labelled by X, and whose leaves are labelled by {1, 2, …, n} (in all possible ways).

Recall that for X = X_{d} = {•}, we have [39]

(5)  |\overline{T}_{kd−k+1}(X)| = \frac{1}{kd − k + 1} \binom{kd}{k}.

For the general case, we note that |\overline{T}_{kd−k+1}(X)| is |X_{d}|^{k} times larger, since every of k internal vertices should acquire a label from X_{d}. Also, it is clear that

(6)  |LT _{kd−k+1}(X)| = \frac{1}{(d!)^{k}}|T_{kd−k+1}(X)|,

since for each of the k internal vertices of a tree only one of the d! permutations of its subtrees fulfils the local increasing condition. Finally,

(7)  |T_{kd−k+1}(X)| = (kd − k + 1)!|\overline{T}_{kd−k+1}(X)|,

since all leaf labelling are allowed in T_{kd−k+1}(X), and the formula follows.

By a subtree of a planar labelled rooted tree T we always mean a subtree S with its root at one of the internal vertices of T such that for each internal vertex of S all its children in T are also its children in S. (This way we can guarantee that the labels of internal vertices make sense for S.) Note that the second condition on leaf-labelling assigns to each internal vertex of a tree T a temporary integer label, so that a subtree S of a tree T almost belongs to LT (X): its leaves are labelled by integers such that the local increasing condition is satisfied (but the labelling set condition might not be satisfied). Replacing, for a subtree S with l leaves, its leaf labels by 1, 2, …, l in the unique orderpreserving way, we shall obtain a tree st(S) ∈ LT (X) which we call the standardisation of S.

Definition 2. A tree T ∈ LT (X) is said to contain a tree P ∈ LT (X) as a pattern if there exists a subtree S of T for which P = st(S). Otherwise T is said to avoid S.

Example 2. Let us recall the tree from Example 1, and consider its subtree represented by thick lines in the following figure:

(8)  _{•}^{∘}^{•}  ^{∘}^{∘}  ^{∘}  ^{∘}^{1} ^{3} ^{2} ^{7} ^{4} ^{6}^{5}  ^{8} .

This subtree acquires the leaf numbering^{1} ^{•} ^{5} _{∘} ^{2} ^{∘} ^{4}, and after standard-

isation we get^{1} ^{•} ^{4} _{∘} ^{2} ^{∘} ^{3}. So^{1} ^{•} ^{4} _{∘} ^{2} ^{∘} ^{3} occurs in our tree as a pattern.

Throughout the paper, we only consider one type of tree patterns, so we often use the term “tree pattern” where one should say “planar labelled rooted tree pattern”; we hope that the reader will appreciate this attempt of keeping terminology simple.

Let us fix some set of labels X, and consider pattern avoidance for planar X-labelled trees. The central question arising in the theory of pattern avoidance is that of enumeration of objects that avoid the given set of forbidden patterns 𝒫 or, more generally, that contain exactly d occurrences of patterns from 𝒫. This question naturally leads to the following equivalence relations for tree patterns. Two sets of tree patterns 𝒫, 𝒫′ ⊂ LT (X) are said to be Wilf equivalent (notation: 𝒫 ∼_{W} 𝒫′) if, for every l, the number of 𝒫-avoiding trees with l leaves is equal to the number of 𝒫′-avoiding trees with l leaves. (In the case of (non-consecutive) permutation patterns the same notion was introduced by Wilf [42].) More generally, 𝒫 and 𝒫′ are said to be (strongly) equivalent (notation: 𝒫 ∼ 𝒫′) if, for every l and every k ≥ 0, the number of trees with l leaves that have k occurrences of patterns from 𝒫 is equal to the number of trees with l leaves that have k occurrences of patterns from 𝒫′.

For enumeration, we shall primarily use exponential generating functions with respect to the number of leaves in trees, so that, for example, the generating functions for the label set X and the pat-

tern set 𝒫 are f_{X}(z) = ∑_{n≥1} \frac{|X_{n}|z^{n}}{n!} and f_{𝒫} (z) = ∑_{l≥1} \frac{|𝒫∩LT _{l}(X)|z^{l}}{l!} , respec-

tively. We shall denote the set of all trees avoiding the pattern set 𝒫 by LT _{no-𝒫} (X), and its subset consisting of trees with l leaves by LT _{l,no-𝒫} (X). The corresponding generating function is denoted by f_{no-𝒫} (z):

(9)  f_{no-𝒫} (z) = ∑_{l≥1} \frac{|LT _{l,no-𝒫} (X)|z^{l}}{l!}.

Remark 1. One can also include a second variable in the generating function to count the internal vertices separately, and use the series

(10)  g_{no-𝒫} (z, t) = ∑_{i,l≥1} \frac{|LT _{i,l,no-𝒫} (X)|t^{i}z^{l}}{l!},

which in particular would make all the sets finite when internal vertices of our trees are allowed to have a single child (and the label set X includes X_{1}). To keep the exposition simple, we avoid discussing these subtleties here.

The key feature of exponential generating functions in the context of planar X-labelled rooted trees is expressed by the following proposition.

Proposition 2. Suppose that 𝒦 and ℒ are two sets of planar X-labelled rooted trees. Let us define a set ℳ as follows: it consists of all trees T that have an occurrence of a tree pattern from 𝒦 rooted at the root of T, with the additional condition that all the subtrees rooted at the leaves of that pattern are occurrences of tree patterns from ℒ. Then

(11)  f_{ℳ} (z) = f_{𝒦} (f_{ℒ} (z)).

Proof.Clearly,

(12)  f_{𝒦} (f_{ℒ} (z)) = ∑_{l≥1} \frac{|𝒦 ∩ LT _{l}(X)|(f_{ℒ} (z))^{l}}{l!} ,

and it remains to note that the coefficient of z^{n} in (f_{ℒ} (z))^{l} is the number of ordered forests of l tree patterns from ℒ with the total leaf set \{1, …, n\}, therefore \frac{(f_{ℒ} (z))^{l}}{l!} can be thought of as the enumerator for forests satisfying the increasing condition for minimal leaves.

2.2. Tree patterns and other types of consecutive patterns. In this section we assume, for simplicity, that X = X_{2} (this corresponds to considering only binary tree patterns).

Our first observation is that for |X| = 1 the set of all permutations is naturally embedded in LT (X) as the set of left combs: recall that a left comb has no conditions on where to put labels 2, 3 …, so left combs with n + 1 leaves are in one-to one correspondence with permutations of length n. If we denote by T(σ) the tree corresponding to the permutation σ, then subtrees of T(σ) are in one-to-one correspondence with subwords of σ, and the notion of a tree pattern for left combs corresponds precisely to the notion of a consecutive pattern for permutations. Moreover, if Π is a set of consecutive permutation patterns, and 𝒫_{Π} contains the left combs corresponding to elements of Π and the right comb with three leaves, then the number of trees with n + 1 leaves that avoid 𝒫_{Π} is equal to the number of permutations of length n that avoid Π. For |X| > 1, the same construction with left combs leads naturally to the notion of pattern avoidance in coloured permutations [29].

Moreover, the set of all words in a given alphabet A is naturally embedded in LT (X) with X = X_{2} = A as the set of right combs. Indeed, recall that for a right comb with n+1 leaves there is exactly one way to label its leaves to fulfil the local increasing condition; to obtain a planar X-labelled rooted tree, it remains to label its internal vertices by A, and the ways to do so are in one-to-one correspondence with A-words of length n. If we denote by T(w) the tree corresponding to the word w, then subtrees of T(w) are in one-to-one correspondence with subwords of w, and the notion of a tree pattern for right combs corresponds precisely to the notion of a divisor for words. Moreover, if W is a set of words, and 𝒫_{W} consists of the right combs corresponding to elements of W and all the left combs with three leaves, then the number of trees with n + 1 leaves that avoid 𝒫_{W} is equal to the number of words of length n without divisors from W.

It is also possible to go the other way round and replace trees by objects resembling permutations and words. Let us assume, as above, that |X| = 1 (ignoring this technical assumption will, as always, merely lead to coloured objects of the same sort). There is a very natural way to “straighten” the tree patterns and thus translate our questions into similar questions about patterns in sequences. Recall that the total number of planar labelled rooted tree patterns in our case is equal to \frac{(2n)!}{2^{n}n!} = (2n−1)!!, the double factorial number. This number is also equal [14] to the number of permutations of the multiset {1, 1, 2, 2, …, n, n} for which all the numbers appearing between the two occurrences of k are greater than k (for every k = 1, …, n). To a planar labelled rooted binary tree T, it is easy to assign recursively a permutation σ(T) of this kind. For that purpose, it is convenient to think of T as of a left comb with subtrees grafted in the places of right children of internal vertices. We denote those subtrees by T_{1}, …, T_{k}, in the order from the leftmost one to the rightmost one. Each subtree T_{i} has its leaf labels belonging to a subset of {1, 2, …, n}, so, strictly speaking, they are not trees of the kind we consider, but, as usual, we can identify them with planar labelled rooted trees via standardisation, so we may apply σ to them, obtaining permutations of appropriate multisets. We assume that σ takes the only one-vertex tree to the empty word, and put

(13)  σ(T) = \begin{cases}1σ(T_{1})1 for k = 1, \\ st(σ(T_{1})σ(T_{2}) ⋯ σ(T_{k})) for k ≥ 2. \end{cases}

For example, σ(^{^{1} ^{2}}) = 11, σ(^{^{1} ^{2} ^{3} ^{4}}) = 112332, σ(^{^{4}^{1} ^{2} ^{3}}) = 122133,

σ(^{^{1}^{2} ^{3} ^{4}}) = 122331; this leads to a meaningful notion of a generalised

permutation pattern. It would be interesting to investigate this notion properly, in particular, to explore the links with patterns in set partitions [19, 25, 37], and also to see if the constructions of [10] can be adapted here.

3. Asymptotic enumeration

In this section, we discuss results on the asymptotic enumeration of trees avoiding a given set of patterns, where the results turn out to, in a way, mimick the results on the asymptotic enumeration for consecutive patterns in permutations [9, 11]. Our main tool is the following result, an adaptation of the classical Golod–Shafarevich inequality [17]; it is closely related to a similar inequality for symmetric operads [34].

Theorem 1. For every (possibly infinite) pattern set 𝒫, we have the following coefficient-wise inequality of power series:

(14)  f_{𝒫} (f_{no-𝒫} (z)) − f_{X}(f_{no-𝒫} (z)) + f_{no-𝒫} (z) ≥ z.

Proof.Let us consider two series of finite sets: the set B_{n} is the subset of LT _{n}(X) consisting of trees T whose subtrees rooted at the children of the root of T avoid patterns from 𝒫, and the set C_{n} is the subset of the set of pairs 𝒫 × LT _{n}(X) consisting of all pairs (P, T) where there exists a subtree S of T rooted at the root of T for which st(S) = P, and all the trees rooted at the leaves of S avoid patterns from 𝒫. Proposition 2 implies that

∑_{n≥1} \frac{|B_{n}|}{n!}z^{n} = f_{X}(f_{no-𝒫} (z)), (15)

∑_{n≥1} \frac{|C_{n}|}{n!}z^{n} = f_{𝒫} (f_{no-𝒫} (z)). (16)

Therefore, our power series inequality translates into

(17)  |C_{n}| − |B_{n}| + |LT _{n,no-𝒫} (X)| ≥ 0, n ≥ 2.

This follows from the observation that there exists an obvious surjection from C_{n} ⊔ LT _{n,no-𝒫} (X) onto B_{n}: a tree from B_{n} either avoids 𝒫, or has a pattern from 𝒫 rooted at its root.

Corollary 1. Suppose that the power series h(z) = _{\frac{1}{1− \frac{f_{X}(z)}{z}+ \frac{f_{𝒫} (z)}{z}}} has non-

negative coefficients. Then we have

(18)  \frac{|LT _{n,no-𝒫} (X)|}{n!}≥ \frac{1}{n}[z^{n−1}]h(z)^{n}.

Proof.Let g(z) = z−f_{X}(z)+f_{𝒫} (z). According to the Lagrange inversion formula [39], for the coefficients of the compositional inverse g^{⟨−1⟩}(z) we have

(19)  [z^{n}]g^{⟨−1⟩}(z) = \frac{1}{n}[z^{n−1}] (\frac{z}{g(z)})^{n} = \frac{1}{n}[z^{n−1}]h(z)^{n},

so under our assumption on h(z) the power series g^{⟨−1⟩}(z) has nonnegative coefficients. According to Theorem 1, the power series

(20)  f_{𝒫} (f_{no-𝒫} (z)) − f_{X}(f_{no-𝒫} (z)) + f_{no-𝒫} (z) = g(f_{no-𝒫} (z))

has non-negative coefficients as well, so we see that

(21) f_{no-𝒫} (z) = g^{⟨−1⟩}(g(f_{no-𝒫} (z))) =

= ∑_{n≥1} (\frac{1}{n}[z^{n−1}]h(z)^{n})g(f_{no-𝒫} (z))^{n} ≥ ∑_{n≥1} (\frac{1}{n}[z^{n−1}]h(z)^{n})z^{n}.

This means that for every n ≥ 1 we have

(22)  \frac{|LT _{n,no-𝒫} (X)|}{n!}≥ \frac{1}{n}[z^{n−1}]h(z)^{n},

which is exactly what we want to prove.

We use this result to prove the following theorem, which gives a series of examples when the set of 𝒫-avoiding trees with n leaves grows rapidly, namely as C^{n} times the number of all trees with n leaves for some constant C. A part of the proof is parallel to the corresponding proof in [9].

Theorem 2. Suppose that X = X_{d} for some d ≥ 2, and that the power series

(23)  h(z) = 1 − \frac{|X_{d}|z^{d−1}}{d!} + \frac{f_{𝒫} (z)}{z}

has a root α > 0. Then we have

(24)  |LT _{n,no-𝒫} (X)| ≥ (\frac{(d!)^{\frac{1}{d−1}}}{|X_{d}|^{\frac{1}{d−1}}α})^{n−1} |LT _{n}(X)|.

Proof.Recall that if X = X_{d}, then the set LT _{n}(X) is non-empty only for n = kd − k + 1 = k(d − 1) + 1 for some k. Therefore, h(z) is a power series in z^{d−1}; we shall consider the series

(25)  ĥ(t) = 1 − t + ∑_{t≥2} a_{k}t^{k},

for which h(z) = ĥ(\frac{|X_{d}|}{d!}z^{d−1}); the only fact about the coefficients of that series that we use is that all the coefficients a_{k} are non-negative (a_{k} is a positive multiple of the number of certain labelled trees with k internal vertices). Under our assumption, this power series has a root β = \frac{|X_{d}|}{d!}α^{d−1}.

Let us consider the multiplicative inverse, ∑ _{l≥0} b_{l}t^{l} := (ĥ(t))^{−1}; clearly, b_{0} = 1 and b_{n} − b_{n−1} + ∑ _{k=2}^{n} a_{k}b_{n−k} = 0. Let us prove by induction that b_{n} ≥ β^{−1}b_{n−1}. Indeed, for n = 1 this statement is obvious (β ≥ 1 because otherwise ĥ(β) is evidently positive), and for n > 1 we note that by the induction hypothesis b_{n−1} ≥ β^{1−k}b_{n−k}, so

b_{n} = b_{n−1} − ∑_{k=2}^{n} a_{k}b_{n−k} ≥ b_{n−1} − ∑_{k=2}^{n} a_{k}β^{k−1}b_{n−1} ≥

≥ b_{n−1} − ∑_{k≥2} a_{k}β^{k−1}b_{n−1} = β^{−1}b_{n−1} (β − ∑_{k≥2} a_{k}β^{k}) = β^{−1}b_{n−1},

and the statement follows. Hence the k^{th} coefficient of (ĥ(t))^{−1} is greater than or equal to β^{−k}. Therefore, the (k(d − 1))^{th} coefficient

of h(z) is greater than or equal to (\frac{|X_{d}|}{d!}) · (\frac{|X_{d}|α^{d−1}}{d!})^{−k} = α^{−k(d−1)}. This means that

(26)  h(z) ≥ ∑_{k≥1} α^{−k(d−1)}z^{k(d−1)} = (1 − (\frac{z}{α})^{d−1})^{−1} ,

so, consequently,

(27)  h(z)^{n} ≥ (1 − (\frac{z}{α})^{d−1})^{−n} .

Since the coefficients of h(z) are non-negative, Corollary 1 applies, and we deduce that

(28) \frac{|LT _{kd−k+1,no-𝒫} (X)|}{(kd − k + 1)!}≥ \frac{1}{kd − k + 1} [z^{k(d−1)}]h(z)^{kd−k+1} ≥

≥ \frac{1}{kd − k + 1} α^{−k(d−1)} \binom{kd − k + 1 + k − 1}{k} = \frac{1}{kd − k + 1} α^{−k(d−1)} \binom{kd}{k}.

This, in view of Formula (4), simplifies to

(29) |LT _{kd−k+1,no-𝒫} (X)| ≥ (kd − k + 1)!\frac{1}{kd − k + 1} α^{−k(d−1)} \binom{kd}{k} =

= α^{−k(d−1)} \frac{(kd)!}{k!}= (\frac{d!}{α^{d−1}} )^{k} \frac{(kd)!}{k!d!^{k}}= (\frac{d!}{|X_{d}|α^{d−1}})^{k}|LT _{kd−k+1}(X)|,

which easily can be transformed into the inequality we want to prove.

This theorem, in particular, can be used to obtain estimates in the case of one tree patterns and |X| = 1, that is, for trees with all internal vertices of the same arity which carry the same label.

Theorem 3. Suppose that |X| = 1, so that X coincides with a one-element set X_{d} for some d ≥ 2, and that the set of forbidden patterns consists of one single pattern P with k ≥ 2 internal vertices. Then for every pair (d, k), except for (2, 2), (2, 3), (2, 4), and (3, 2) there exists a positive number C (depending only on d and k but not on the actual pattern) such that

(30)  |LT _{n,no-P}(X)| ≥ C^{n−1}|LT _{n}(X)|.

Proof.It is enough to show that for all pairs (d, k) except for (2, 2), (2, 3), (2, 4), and (3, 2), the polynomial h(z) = 1 − \frac{z^{d−1}}{d!} + \frac{z^{k(d−1)}}{(kd−k+1)!} has a

positive root. Denoting, as above, t = \frac{z^{d−1}}{d!}, we see that it is enough to prove that the polynomial ĥ(t) = 1 − t + \frac{d!^{k}t^{k}}{(kd−k+1)!} has a positive

root. For that purpose, we note that the derivative −1 + \frac{kd!^{k}t^{k−1}}{(kd−k+1)!} of

the polynomial ĥ(t) has the only positive root t_{0} = (\frac{(kd−k+1)!}{kd!^{k}})^{\frac{1}{k−1}}; thus, to prove that ĥ(t) has a positive root, it is enough to prove that its minimal value is attained at t_{0} and is negative. Using the formula t_{0}^{k−1} = \frac{(kd−k+1)!}{kd!^{k}}, we see that ĥ(t_{0}) = 1 − t_{0} + \frac{t_{0}}{k}, so it suffices to prove that t_{0} > \frac{k}{k−1}, or

(31)  \frac{(kd − k + 1)!(k − 1)^{k−1}}{d!^{k}k^{k}} > 1,

which is true in all cases we consider, since it is true for (d, k) = (2, 5), (d, k) = (3, 3), and (d, k) = (4, 2), and its left hand side increases if either d or k increases.

Our results suggest a new numerical invariant of a set of patterns:

Definition 3. The growth rate of a set of patterns 𝒫 ⊂ LT (X) is

(32)  lim sup_{n→∞} (\frac{|LT _{n,no-𝒫} (X)|}{|LT _{n}(X)|})^{\frac{1}{n−1}} .

We expect that the methods of this section can be easily generalised to prove that for every set of labels X (and for some k depending on X) every pattern in LT (X) with at least k internal vertices has positive growth. Moreover, computer experiments suggest that the following conjecture generalising Warlimont’s conjecture for consecutive patterns [41] (proved recently by Ehrenborg, Kitaev and Perry [10] via a beautiful link between consecutive pattern avoidance and the spectral theory for integral operators on the unit cube) holds for tree patterns.

Conjecture 1. For every set of labels X, there exists an integer d that for every pattern P in LT (X) with at least d internal vertices and some numbers c(P) > 0, λ(P) > 1 we have

(33)  \frac{|LT _{n,no-P}(X)|}{|LT _{n}(X)|}∼ c(P)λ(P)^{−n}.

It would be most interesting to adapt the approach of [10] for tree patterns; such an adaptation, in addition to its consequences for the asymptotic enumeration questions, may be of substantial interest for operad theory as well. Another natural question arising from asymptotic enumeration is to understand the “growth hierarchies” of tree patterns, using the strategy of [26] or otherwise.

4. Exact enumeration: cluster inversion formula

The following result on power series inversion is simultaneously a generalisation of the inversion formula for planar tree patterns [1, 28, 33] and of the cluster inversion formula of Goulden and Jackson for words and permutations [20, 32]. This result is proved in [7] by simple homological algebra; we formulate it here in a different way, so that an interested reader will easily prove it directly using the inclusion-exclusion formula, similarly to the usual cluster inversion.

Definition 4. Let 𝒫 be a set of patterns in LT (X). A tree T together with a collection of its subtrees T_{1}, …, T_{k} is said to be a k-cluster if the following two conditions hold:

(1) For every i, the subtree T_{i} is an occurrence of a pattern from 𝒫: st(T_{i}) ∈ 𝒫,

(2) every edge e of T that joins two internal vertices is an edge

between two internal vertices of some T_{i}. By definition, the set of 0-clusters is the set of labels X.

Informally, a k-cluster is a tree which is completely covered by k copies of patterns from 𝒫.

Let us write c_{n,k}(𝒫) for the number of k-clusters for which the tree T has n leaves.

Theorem 4 ([7]). The compositional inverse of f_{no-𝒫} (z) can be computed via clusters as follows:

(34)  f_{no-𝒫}^{⟨−1⟩} (z) = z − ∑_{n≥1,k≥0} \frac{(−1)^{k}c_{n,k}(𝒫)z^{n}}{n!} .

The following consequence of the general inversion formula is a direct analogue for planar labelled tree patterns of the inversion formula [1, 28, 33] for planar tree patterns.

Corollary 2. Suppose that X = X_{2}, and that 𝒫 and 𝒬 are two complementary sets of tree patterns with 3 leaves, 𝒫 ⊔ 𝒬 = LT _{3}(X). The corresponding generating functions for pattern avoidance are inverse to each other:

(35)  f_{no-𝒫} (−f_{no-𝒬} (−z)) = f_{no-𝒬} (−f_{no-𝒫} (−z)) = z.

Proof.It is easy to see that in this case k-clusters for 𝒫 are in one-to-one correspondence with trees that avoid 𝒬 (each such tree admits the unique covering by patterns from 𝒫), and that the signs in the inversion formula match those suggested by (35) (since in our case the underlying tree of every n-cluster has n + 2 leaves).

Note that for left (right) combs corresponding to some consecutive permutation patterns (words), clusters for left combs are the left (right) combs corresponding to the usual Goulden–Jackson clusters for these patterns (words). This instantly proves the following result.

Corollary 3. Suppose that two sets of consecutive permutation patterns (words) are Wilf equivalent. Then the two sets of tree patterns consisting of the left (right) combs corresponding to the given permutation patterns (words) are Wilf equivalent as tree patterns.

As in the case of permutations, we expect that at least in the case of a single pattern a careful study of its self-overlaps (“overlap sets” of [23], or equivalently “overlap maps” of [31]) would be very beneficial for studying Wilf equivalence. We shall discuss this in detail elsewhere, mentioning a particular case briefly in the next section.

Let us conclude this section with an open question. For consecutive patterns in permutations, Mendes and Remmel developed the symmetric functions method [30] for enumeration of permutations avoiding a given set of patterns. It is natural to expect that this method can be generalised to deal with the case of tree patterns, possibly making use of the plethysm for symmetric functions where our formulas compute compositions of power series. Some inversion formulas in the completion of the algebra of symmetric functions exist in the operadic context, being provided by homological algebra, in particular the operadic Koszul duality for symmetric operads [16], however, once we move from abstract trees to their representatives (that is, planar labelled rooted trees studied in this paper), there is no clear way to incorporate symmetric functions in the picture.

5. Examples

5.1. Case X = X_{2}, |X| = 1. In this section, we assume that X = X_{2}, |X| = 1, that is, we only work with binary trees, and do not use labels for internal vertices. To simplify the notation, we suppress X in the formulas, and write simply LT _{n}, etc.

We begin with classifying the Wilf classes of pattern sets with three leaves.

Theorem 5. There exist exactly four Wilf classes of sets of patterns with three leaves.

Proof.This theorem follows from Lemmas 5.1 and 5.2 below, which give a precise description of the five Wilf classes.

Lemma 5.1. The three patterns ^{^{1}  ^{3} ^{2}}, ^{^{1}  ^{2} ^{3}}, ^{3 2 1} are Wilf equivalent to

each other; the number of trees with n leaves avoiding either of them is equal to (n − 1)! for each n ≥ 3.

Proof.Let us write P_{1} = ^{^{1}  ^{3} ^{2}}, P_{2} = ^{^{1}  ^{2} ^{3}}, and P_{3} = ^{3 2 1}.

A correspondence ρ between the set of P_{1}-avoiding trees and the set of P_{2}-avoiding trees can be defined recursively as follows. By definition, ρ(^{^{1} ^{2}}) = ^{^{1} ^{2}}. Let us represent a tree T ∈ LT _{n,no-P_{1}} as a left comb with some subtrees T_{1}, …, T_{k} (listed along the way from the root) grafted at its “right-looking” leaves. To determine ρ(T), we apply ρ to the subtrees T_{i} and reverse the order of grafting. In other words, we graft ρ(T_{k}) in the place of T_{1}, ρ(T_{k−1}) in the place of T_{2}, etc. Clearly, ρ identifies LT _{n,no-P_{1}} with LT _{n,no-P_{2}}.

A correspondence κ between the set of P_{1}-avoiding trees and the set of P_{3}-avoiding trees can be defined recursively as well. By definition, ρ(^{^{1} ^{2}}) = ^{^{1} ^{2}}. Let us represent a tree T ∈ LT _{n,no-P_{1}} as a left comb with some subtrees T_{1}, …, T_{k} (listed along the way from the root) grafted at its right-looking leaves. We note that the set LT _{n,no-P_{3}} is the set of all left combs with n leaves; by induction we may assume that we already know the left combs κ(T_{1}), …, κ(T_{k}). Let κ(T) be the left comb whose right-looking leaves, listed along the way from the root, are the right-looking leaves of κ(T_{k}), the right-looking leaves of κ(T_{k−1}), …, the right-looking leaves of κ(T_{1}). The observation (which can easily be proved by induction) that the label of the right-looking leaf of κ(T) which is the farthest from the root is equal to the smallest leaf label of T_{1} shows how to construct the inverse of κ, so we identified LT _{n,no-P_{1}} with LT _{n,no-P_{3}}.

In addition, since the set LT _{n,no-P_{3}} is the set of all left combs with n leaves, it has cardinality (n − 1)!, so, for each of the three subsets 𝒫 ⊂ LT _{3} with |𝒫| = 1 and for each n, there are exactly (n − 1)! different 𝒫-avoiding tree with n leaves.

Lemma 5.2. The three two-pattern sets {^{^{1}  ^{2} ^{3}},^{^{1}  ^{3} ^{2}}}, {^{^{1}  ^{2} ^{3}},^{3 2 1}}, and

{^{^{1} ^{3} ^{2}},^{3 2 1}} are Wilf equivalent to each other; the number of trees with n

leaves avoiding either of these sets is equal to 1 for each n ≥ 3.

Proof.Indeed, for 𝒫 = {^{^{1}  ^{2} ^{3}},^{^{1}  ^{3} ^{2}}} the only 𝒫-avoiding tree with

n leaves is the only right comb, for 𝒫 = {^{^{1} ^{2} ^{3}},^{3 2 1}} the only 𝒫-

avoiding tree with n leaves is the only left comb with labels of rightlooking leaves increasing along the way from the root, and for 𝒫 =

{^{^{1} ^{3} ^{2}},^{3 2 1}} the only 𝒫-avoiding tree with n leaves is the only left

comb with labels of right-looking leaves decreasing along the way from the root. Therefore for each of the three subsets 𝒫 ⊂ LT _{3} with |𝒫| = 2 and for each n, there is exactly one 𝒫-avoiding tree with n leaves.

Alternatively, one can apply the inversion formula (35): from Lemma 5.1, we conclude that the exponential generating function for every one-pattern set is equal to − log(1 − z); computing its inverse and adjusting the signs instantly shows that the exponential generating function for every two-pattern set is exp(z) − 1, which is the exponential generating function for the sequence 1, 1, 1, . . ..

Since the empty pattern set and the pattern set containing all trees with three leaves form their own Wilf classes, the theorem follows.

For pattern sets with at least four leaves, we have only partial

results. Note that there are 15 patterns with four leaves: ^{^{1} ^{2} ^{3} ^{4}},

1  ^{2} ^{4} ^{3},^{^{1}  ^{3} ^{2} ^{4}},^{^{1}  ^{3} ^{4} ^{2}},^{^{1}  ^{4} ^{2} ^{3}},^{^{1}  ^{4} ^{3} ^{2}},^{^{4}^{1} ^{2}  ^{3}},^{^{3}^{1} ^{2}  ^{4}},^{^{2}^{1} ^{3}  ^{4}},^{^{1} ^{2} ^{3} ^{4}},^{^{1} ^{3} ^{2} ^{4}},

1 ^{4} ^{2} ^{3}, ^{^{1}^{2}  ^{3} ^{4}}, ^{^{1}^{2}  ^{4} ^{3}}, and ^{^{1} ^{2} ^{3}  ^{4}}. Therefore the number of sets of

tree patterns with 4 leaves is equal to 2^{15} = 32768, so a complete classification of Wilf classes is already a very heavy task. We shall present a very simple result on the classification of Wilf classes for sets consisting of a single pattern.

Theorem 6. There exist exactly five Wilf classes of sets of one pattern with four leaves.

Proof.This theorem follows from Lemmas 6.1– 6.3 below, which give a precise description of the five Wilf classes.

Lemma 6.1. The three patterns ^{^{1}  ^{2} ^{3} ^{4}}, ^{^{1}  ^{4} ^{3} ^{2}}, and ^{^{1} ^{2} ^{3}  ^{4}} are Wilf

equivalent to each other.

Proof.There is a bijective proof which is completely analogous to that of Lemma 5.1; we leave it to the reader to fill in the details.

Lemma 6.2. The six patterns^{^{1} ^{2} ^{3} ^{4}},^{^{1} ^{3} ^{2} ^{4}},^{^{1} ^{4} ^{2} ^{3}},^{^{2}^{1} ^{3}  ^{4}},^{^{1}^{2}  ^{3} ^{4}}, and^{^{1}^{2}  ^{4} ^{3}}

are Wilf equivalent to each other.

Proof.Let us write P_{1} = ^{^{1} ^{2} ^{3} ^{4}}, P_{2} = ^{^{1} ^{3} ^{2} ^{4}}, P_{3} = ^{^{1} ^{4} ^{2} ^{3}}, P_{4} = ^{^{2}^{1} ^{3} ^{4}},

P_{5} = ^{^{1}^{2}  ^{3} ^{4}}, and P_{6} = ^{^{1}^{2}  ^{4} ^{3}}.

We show that P_{1} ∼_{W} P_{2} by exhibiting a one-to-one correspondence α between the P_{1}-avoiding trees and the P_{2}-avoiding ones. If a tree T avoids both P_{1} and P_{2}, we put α(T) = T. If T avoids P_{1} but contains P_{2}, we may assume that there is an occurrence of P_{2} at the root of T (otherwise we find the internal vertices closest to the root that are roots of occurrences of P_{2}, and apply α recursively at these vertices). Let

T = ^{^{T_{1}}^{T_{2}}^{T_{3}}^{T_{4}}}, and write S_{i} = α(T_{i}), i = 1, …, 4. We put α(T) = ^{^{S_{1}} ^{S_{3}} ^{S_{2}} ^{S_{4}}}.

We constructed a bijection between P_{1}-avoiding trees containing P_{2} and P_{2}-avoiding trees containing P_{1}. The case of P_{1} and P_{3} is handled in a similar way.

We now show that P_{1} ∼_{W} P_{4} by exhibiting a one-to-one correspondence β between the P_{1}-avoiding trees and the P_{4}-avoiding ones. If a tree T avoids both P_{1} and P_{4}, we put β(T) = T. If T avoids P_{1} but contains P_{4}, we may assume that there is an occurrence of P_{4} at the root of T (otherwise we find the internal vertices closest to the root that are roots of occurrences of P_{4}, and apply β recursively at these

vertices). Let T = ^{^{T_{2}}^{T_{1}}^{T_{3}} ^{T_{4}}}, and write S_{1} = β(^{^{T_{1}} ^{T_{2}}}), S_{2} = β(^{^{T_{3}} ^{T_{4}}}). We put

β(T) = ^{^{S_{1}} ^{S_{2}}}. Note that the only vertex of this tree where an occurrence of P_{4} can be rooted is the root. However, if there is an occurrence of P_{4} there, it is easily seen to imply an occurrence of P_{1} in T, a contradiction. In this way, we constructed a bijection between P_{1}-avoiding trees containing P_{2} and P_{2}-avoiding trees containing P_{1}.

The equivalence P_{5} ∼_{W} P_{6} can be established inductively similarly to how this is done in Lemma 5.1.

Finally, the easiest way to see the equivalence P_{1} ∼_{W} P_{5} is via the inverse generating functions. Essentially, P_{1} and P_{5} have the same structure of self-overlaps: there are two self-overlaps, one of which is “rigid” (only one labelling of leaves is consistent with the local increasing condition), and the other one admits three different leaf labellings. This allows for an inductively constructed bijection between the clusters that control the coefficients of the inverse series. We leave the details to the reader.

Lemma 6.3. The four patterns ^{^{1}  ^{2} ^{4} ^{3}}, ^{^{1}  ^{3} ^{2} ^{4}}, ^{^{1}  ^{3} ^{4} ^{2}}, and ^{^{1}  ^{4} ^{2} ^{3}} are

Wilf equivalent to each other.

Proof.The corresponding permutation patterns are Wilf equivalent, so Corollary 3 applies.

Combining the lemmas above with a somewhat lengthy computation showing that

• for the class described in Lemma 6.1 the sequence counting the trees avoiding the patterns of that class begins with 1, 1, 3, 14, 91, 756, 7657,

• for the class described in Lemma 6.2 the sequence counting the trees avoiding the patterns of that class begins with 1, 1, 3, 14, 90, 739, 7392,

• for the class described in Lemma 6.3 the sequence counting the trees avoiding the patterns of that class begins with 1, 1, 3, 14, 90, 738, 7364,

• for the pattern^{^{3}^{1} ^{2} ^{4}} the sequence counting the trees avoiding

that pattern begins with 1, 1, 3, 14, 90, 740, 7420,

• for the pattern^{^{4}^{1} ^{2} ^{3}} the sequence counting the trees avoiding

that pattern begins with 1, 1, 3, 14, 90, 737, 7336, we conclude that there are exactly five different Wilf classes.

Of the five integer sequences we saw in the previous proof, only two seem to appear in the Online Encyclopedia of Integer Sequences [38]: the third one matches A088789, the sequence of coefficients in the compositional inverse of the power series \frac{2x}{1+exp(x)}, and the first one matches A183611, which, if we take care of the difference in numbering, is described as the sequence of coefficients of the power series f (z) satisfying the differential equation f′′(z) = f′(z)^{2} + zf′(z)^{3}. The first of these descriptions is not too surprising, as the inversion formula (34)suggests that the inverse series makes lots of sense combinatorially. The second description is related to the results of Khoroshkin and Piontkovski [22] who proved that in some cases the generating function does indeed satisfy a differential equation; however, the patterns of that Wilf class are not covered by their results, so the appearance of a differential equation in this enumeration problem would be another bit of evidence supporting their general conjecture that states that for every finite set of patterns the corresponding generating function satisfies an algebraic differential equation with polynomial coefficients.

It is natural to ask which tree patterns are “the hardest to avoid”, that have the fewest numbers of trees that avoid them, and which tree patterns are “the easiest to avoid”, that is have the largest numbers of trees that avoid them. After examining the proof of the previous theorem and performing some computer experiments, we arrived at the following conjecture which is closely related to the conjecture of Elizalde and Noy [12] that the permutation 12 …n (the identity permutation) is the easiest to avoid, and to the conjecture of Nakamura [31] that the permutation 12 …(n − 2)n(n − 1) (the transposition of its last two entries) is the hardest to avoid.

Conjecture 2. Let us denote by LC_{n}^{<}, LC_{n}^{>}, and RC_{n} the left comb with n leaves whose leaf labels increase along the way from the root, the left comb with n leaves whose leaf labels decrease along the way from the root, and the right comb with n leaves, respectively. The patterns LC_{n}^{<}, LC_{n}^{>}, and RC_{n} are

the easiest to avoid, and the pattern^{^{RC_{n−1}} ^{n}} is the hardest to avoid.

5.2. Case X = X_{2}, |X| = 2. Throughout this section we assume that we work with binary trees with two possible labels for internal vertices, in other words, X = X_{2} = {∘, •}.

The following result is still easy to obtain “by hand”.

Theorem 7. There exist exactly two Wilf classes of one pattern sets with three leaves, and exactly ten Wilf classes of sets of two patterns with three leaves.

Proof.First of all, let us note that because of the inversion formula (35), we can work with the trees avoiding 11 and 10 patterns, respectively. For the avoidance of 11 patterns, the only allowed pattern can either use only one internal vertex label (in which case Theorem 5 means that there exists only one allowed tree for each number of leaves) or use two different internal vertex labels (in which case there is no way to build an allowed tree with 4 or more leaves).

For the avoidance of 10 patterns, our theorem follows from a sequence of lemmas which give a precise description of the ten Wilf classes. Lemmas 7.1–7.7 are almost obvious, since the trees that are being counted admit very explicit descriptions; we omit their proofs. Note that we switch to complements again: instead of listing the tenelement sets, we list their complements in the set of all tree patterns with three leaves.

Lemma 7.1. The six sets whose complements in the set of all tree pat-

terns with three leaves are { _{•}^{•}  ^{3}^{1}  ^{2} , _{•}^{•}  ^{2}^{1}  ^{3} }, { _{•}^{•}  ^{2}^{1}  ^{3} ,  ^{3}_{•}^{2} ^{•}^{1}  }, { _{•}^{•}  ^{3}^{1}  ^{2} ,  ^{3}_{•}^{2} ^{•}^{1}  },

{ _{∘}^{∘}  ^{3}^{1}  ^{2} , _{∘}^{∘}  ^{2}^{1}  ^{3} }, { _{∘}^{∘}  ^{2}^{1}  ^{3} ,  ^{3}_{∘}^{2} ^{∘}^{1}  }, { _{∘}^{∘}  ^{3}^{1}  ^{2} ,  ^{3}_{∘}^{2} ^{∘}^{1}  } are Wilf equivalent to each

other; the number of trees with n leaves avoiding either of these sets is equal to (n − 1)! for each n ≥ 4.

Lemma 7.2. The two sets whose complements in the set of all tree patterns

with three leaves are { _{•}^{∘}  ^{3}^{1}  ^{2} ,  ^{3}_{∘}^{2} ^{•}^{1}  }, { _{∘}^{•}  ^{3}^{1}  ^{2} ,  ^{3}_{•}^{2} ^{∘}^{1}  } are Wilf equivalent to

each other; the number of trees with n leaves avoiding either of these sets is equal to \frac{3}{2} (\frac{n}{2})! for even n ≥ 4 and to (\frac{n−1}{2} )! + \frac{1}{2} (\frac{n+1}{2} )! for odd n ≥ 3.

Lemma 7.3. The ten sets whose complements in the set of all tree pat-

terns with three leaves are { _{•}^{•}  ^{3}^{1}  ^{2} , _{•}^{∘}  ^{2}^{1}  ^{3} }, { _{•}^{•}  ^{2}^{1}  ^{3} , _{•}^{∘}  ^{3}^{1}  ^{2} }, { _{•}^{•}  ^{3}^{1}  ^{2} , _{∘}^{•}  ^{2}^{1}  ^{3} },

{ _{•}^{•}  ^{2}^{1}  ^{3} , _{∘}^{•}  ^{3}^{1}  ^{2} }, { _{∘}^{∘}  ^{3}^{1}  ^{2} , _{•}^{∘}  ^{2}^{1}  ^{3} }, { _{∘}^{∘}  ^{2}^{1}  ^{3} , _{•}^{∘}  ^{3}^{1}  ^{2} }, { _{∘}^{∘}  ^{3}^{1}  ^{2} , _{∘}^{•}  ^{2}^{1}  ^{3} }, { _{∘}^{∘}  ^{2}^{1}  ^{3} , _{∘}^{•}  ^{3}^{1}  ^{2} },

{  ^{3}_{•}^{2} ^{•}^{1}  , _{∘}^{•}  ^{3}^{1}  ^{2} }, {  ^{3}_{∘}^{2} ^{∘}^{1}  , _{•}^{∘}  ^{3}^{1}  ^{2} } are Wilf equivalent to each other; the number

of trees with n leaves avoiding either of these sets is equal to n − 1 for each n ≥ 4.

Lemma 7.4. The 32 sets whose complements in the set of all tree pat-

terns with three leaves are { _{•}^{•}  ^{3}^{1}  ^{2} , _{∘}^{∘}  ^{3}^{1}  ^{2} }, { _{•}^{•}  ^{3}^{1}  ^{2} , _{∘}^{∘}  ^{2}^{1}  ^{3} }, { _{•}^{•}  ^{3}^{1}  ^{2} ,  ^{3}_{∘}^{2} ^{∘}^{1}  },

{ _{•}^{•}  ^{2}^{1}  ^{3} , _{∘}^{∘}  ^{3}^{1}  ^{2} }, { _{•}^{•}  ^{2}^{1}  ^{3} , _{∘}^{∘}  ^{2}^{1}  ^{3} }, { _{•}^{•}  ^{2}^{1}  ^{3} ,  ^{3}_{∘}^{2} ^{∘}^{1}  }, {  ^{3}_{•}^{2} ^{•}^{1}  , _{∘}^{∘}  ^{3}^{1}  ^{2} }, {  ^{3}_{•}^{2} ^{•}^{1}  , _{∘}^{∘}  ^{2}^{1}  ^{3} },

{  ^{3}_{•}^{2} ^{•}^{1}  ,  ^{3}_{∘}^{2} ^{∘}^{1}  }, { _{•}^{•}  ^{3}^{1}  ^{2} , _{∘}^{•}  ^{3}^{1}  ^{2} }, { _{•}^{•}  ^{2}^{1}  ^{3} , _{∘}^{•}  ^{2}^{1}  ^{3} }, { _{∘}^{∘}  ^{3}^{1}  ^{2} , _{•}^{∘}  ^{3}^{1}  ^{2} }, { _{∘}^{∘}  ^{2}^{1}  ^{3} , _{•}^{∘}  ^{2}^{1}  ^{3} },

{  ^{3}_{•}^{2} ^{•}^{1}  ,  ^{3}_{∘}^{2} ^{•}^{1}  }, {  ^{3}_{∘}^{2} ^{∘}^{1}  ,  ^{3}_{∘}^{2} ^{•}^{1}  }, {  ^{3}_{•}^{2} ^{•}^{1}  ,  ^{3}_{•}^{2} ^{∘}^{1}  }, { _{•}^{•}  ^{2}^{1}  ^{3} , _{•}^{∘}  ^{2}^{1}  ^{3} }, { _{∘}^{∘}  ^{3}^{1}  ^{2} , _{∘}^{•}  ^{3}^{1}  ^{2} },

{ _{∘}^{∘}  ^{2}^{1}  ^{3} , _{∘}^{•}  ^{2}^{1}  ^{3} }, {  ^{3}_{•}^{2} ^{•}^{1}  ,  ^{3}_{∘}^{2} ^{•}^{1}  }, {  ^{3}_{∘}^{2} ^{∘}^{1}  ,  ^{3}_{•}^{2} ^{∘}^{1}  }, { _{•}^{∘}  ^{3}^{1}  ^{2} , _{∘}^{•}  ^{3}^{1}  ^{2} }, { _{•}^{∘}  ^{2}^{1}  ^{3} , _{∘}^{•}  ^{2}^{1}  ^{3} },

{  ^{3}_{•}^{2} ^{∘}^{1}  ,  ^{3}_{∘}^{2} ^{•}^{1}  }, {  ^{3}_{•}^{2} ^{•}^{1}  , _{∘}^{•}  ^{2}^{1}  ^{3} }, {  ^{3}_{∘}^{2} ^{∘}^{1}  , _{•}^{∘}  ^{2}^{1}  ^{3} }, {  ^{3}_{∘}^{2} ^{•}^{1}  , _{•}^{•}  ^{3}^{1}  ^{2} }, {  ^{3}_{∘}^{2} ^{•}^{1}  , _{•}^{•}  ^{2}^{1}  ^{3} },

{ _{∘}^{∘}  ^{3}^{1}  ^{2} ,  ^{3}_{•}^{2} ^{∘}^{1}  }, _{∘}^{∘}  ^{2}^{1}  ^{3} ,  ^{3}_{•}^{2} ^{∘}^{1}  }, { _{•}^{∘}  ^{2}^{1}  ^{3} ,  ^{3}_{∘}^{2} ^{•}^{1}  }, { _{∘}^{•}  ^{2}^{1}  ^{3} ,  ^{3}_{•}^{2} ^{∘}^{1}  } are Wilf equiva-

lent to each other; the number of trees with n leaves avoiding either of these sets is equal to 2 for each n ≥ 4,.

Lemma 7.5. The two sets whose complements in the set of all tree patterns

with three leaves are { _{∘}^{•}  ^{3}^{1}  ^{2} ,  ^{3}_{∘}^{2} ^{•}^{1}  }, { _{•}^{∘}  ^{3}^{1}  ^{2} ,  ^{3}_{•}^{2} ^{∘}^{1}  } are Wilf equivalent to

each other; the number of trees with n leaves avoiding either of these sets is equal to 1 for n = 4, and equal to 0 for each n ≥ 5.

Lemma 7.6. The two sets whose complements in the set of all tree patterns

with three leaves are { _{∘}^{•}  ^{2}^{1}  ^{3} ,  ^{3}_{∘}^{2} ^{•}^{1}  }, { _{•}^{∘}  ^{2}^{1}  ^{3} ,  ^{3}_{•}^{2} ^{∘}^{1}  } are Wilf equivalent to

each other; the number of trees with n leaves avoiding either of these sets is equal to 2 for n = 4, and equal to 0 for each n ≥ 5.

Lemma 7.7. The two sets whose complements in the set of all tree patterns

with three leaves are { _{∘}^{•}  ^{3}^{1}  ^{2} , _{∘}^{•}  ^{2}^{1}  ^{3} }, { _{•}^{∘}  ^{3}^{1}  ^{2} , _{•}^{∘}  ^{2}^{1}  ^{3} } are Wilf equivalent to

each other; the number of trees with n leaves avoiding either of these sets is equal to 0 for each n ≥ 4.

Lemma 7.8. The six sets whose complements in the set of all tree pat-

terns with three leaves are { _{•}^{•}  ^{3}^{1}  ^{2} ,  ^{3}_{•}^{2} ^{∘}^{1}  }, { _{•}^{•}  ^{2}^{1}  ^{3} ,  ^{3}_{•}^{2} ^{∘}^{1}  }, { _{∘}^{∘}  ^{3}^{1}  ^{2} ,  ^{3}_{∘}^{2} ^{•}^{1}  },

{ _{∘}^{∘}  ^{2}^{1}  ^{3} ,  ^{3}_{∘}^{2} ^{•}^{1}  }, {  ^{3}_{•}^{2} ^{•}^{1}  , _{•}^{∘}  ^{2}^{1}  ^{3} }, {  ^{3}_{∘}^{2} ^{∘}^{1}  , _{∘}^{•}  ^{2}^{1}  ^{3} } are Wilf equivalent to each

other; the number of trees with n leaves avoiding either of these sets is equal to the number of involutions in S_{n−1} for each n ≥ 4.

Proof.Examining the structure of the allowed trees, we see that in each case we have a right comb or an increasing (decreasing) left comb, possibly with leaves replaced by pairs of leaves. Examining the leaf labels, one easily extracts a decomposition of an involution into its product of disjoint cycles, which gives a one-to-one correspondence.

Lemma 7.9. The two sets whose complements in the set of all tree patterns

with three leaves are {  ^{3}_{•}^{2} ^{•}^{1}  , _{•}^{∘}  ^{3}^{1}  ^{2} } and {  ^{3}_{∘}^{2} ^{∘}^{1}  , _{∘}^{•}  ^{3}^{1}  ^{2} } are Wilf equivalent

to each other; the number of trees with n leaves avoiding either of these sets is equal to the n^{th} Fibonacci number (f_{0} = 0, f_{1} = 1, f_{n+1} = f_{n} + f_{n−1}) for each n ≥ 3.

Proof.Examining the structure of the allowed trees, we see that in each case we have a right comb, possibly with leaves replaced by pairs of leaves, but with the leaf labels increasing globally along the path from the root. Therefore, the number of trees we are trying to compute is equal to the number of sequences of 1’s and 2’s that sum up to n − 1, which is known to be the Fibonacci number [39].

Lemma 7.10. The two sets whose complements in the set of all tree patterns

with three leaves are { _{•}^{∘}  ^{2}^{1}  ^{3} , _{∘}^{•}  ^{3}^{1}  ^{2} }, { _{∘}^{•}  ^{2}^{1}  ^{3} , _{•}^{∘}  ^{3}^{1}  ^{2} } are Wilf equivalent to

each other; the number of trees with n leaves avoiding either of these sets is twice the number of alternating permutations in S_{n−1} for each n ≥ 3.

Proof.Clearly, each allowed tree is a left comb, the labels ∘, • along the path from the root alternate, and so do the leaf labels. Therefore, the statement is obvious: alternating permutations come from the leaf labels, and “twice” reflects the fact that for each k there are two alternating sequences of ∘’s and •’s of length k.

Further (computer-aided) investigation shows that the following statement is true:

Theorem 8. For sets of patterns with 3 leaves, there are (1) 2 Wilf classes of 1-element sets,

(2) 10 Wilf classes of 2-element sets,

(3) 40 Wilf classes of 3-element sets,

(4) 99 Wilf classes of 4-element sets,

(5) 189 Wilf classes of 5-element sets,

(6) 202 Wilf classes of 6-element sets,

(7) 189 Wilf classes of 7-element sets,

(8) 99 Wilf classes of 8-element sets,

(9) 40 Wilf classes of 9-element sets,

(10) 10 Wilf classes of 10-element sets,

(11) 2 Wilf classes of 11-element sets.

To conclude this section, let us mention a promising direction towards new bijective proofs for enumeration of Wilf equivalence classes. In the case of unlabelled planar trees, many bijections have been constructed in [13], where “word notation” for trees was used. That “word notation” is a construction of crucial importance for operad theory was discovered by Hoffbeck [18], who defined a partial ordering compatible with the operad structure on the set of “tree monomials,” which was then used to formulate and prove a PBW criterion for Koszul operads. Later, this partial ordering was extended to a total ordering (still compatible with the operad structure) in [8]; that ordering is one of the key ingredients of the Gröbner bases machinery in the case of operads. The latter total ordering is coming from replacing a tree T ∈ LT (X) by a pair (path(T), perm(T)) consisting of a “path sequence” path(T) (a sequence of words in the alphabet X) and a permutation perm(T) of the set of leaves of T. All questions of pattern avoidance for trees can be translated into questions of pattern avoidance for this type of data; the corresponding notion of a pattern is a certain mixture of the classical notion of a divisor of a word and the notion of a generalised pattern in permutations [2, 5] (different from the naïve notion of a generalised pattern in coloured permutations). This way of thinking of patterns in trees should be useful for bijective proofs; we hope to address this in more detail elsewhere.

Appendix A. Shuffle operads and patterns in trees

In this appendix, we recall some relevant definitions of operad theory, and explain how the notion of pattern avoidance in trees arises naturally in this context.

Let us denote by Ord the category whose objects are non-empty finite ordered sets (with order-preserving bijections as morphisms). Also, we denote by Vect the category of vector spaces (with linear operators as morphisms). It is usually enough to assume vector spaces to be finite-dimensional, though sometimes more generality is needed, and one assumes, for instance, that they are graded with finite-dimensional homogeneous components.

Definition 5. (1) A (non-symmetric) collection is a contravariant functor from the category Ord to the category Vect. We shall refer to images of individual sets as components of our collection.

(2) Let 𝒫 and 𝒬 be two non-symmetric collections. The shuffle composition product of 𝒫 and 𝒬 is the non-symmetric collection 𝒫 ∘_{sh} 𝒬 defined by the formula

(𝒫 ∘_{sh} 𝒬)(I) := ⨁_{k} 𝒫(k) ⊗ ( ⨁_{f: I [k]} 𝒬(f^{−1}(1)) ⊗ …⊗ 𝒬(f^{−1}(k))) ,

where the sum is taken over all shuffling surjections f, that is surjections for which min f^{−1}(i) < min f^{−1}(j) whenever i < j.

(3) A shuffle operad is a monoid in the category of non-symmetric collections equipped with the shuffle composition product.

This definition is a counterpart of a more classical one, where one deals with finite sets without a specified order, and all surjections are allowed to define the composition. The corresponding monoids are called (symmetric) operads, and these are monoids widely used in algebra and topology, since they capture the algebraic properties of compositions of operations with several arguments. In particular, algebras of a certain type, like all associative algebras, or all Lie algebras, can be viewed as modules over a monoid of this kind (formed by all operations that can be defined on algebras of the given type), and this point of view proves to be useful. However, for computational purposes, the fact that finite sets have symmetries gets in the way, and it turns out that shuffle operads allow one to deal with some of the troubles arising because of that. (Every symmetric operad can be viewed as a shuffle operad, since every ordered set can be viewed as an unordered set.)

Monoids in the monoidal category of vector spaces (with the usual tensor product) are associative algebras. One can present associative algebras via generators and relations; if all relations are monomials in generators, the corresponding algebra admits a straightforward basis consisting of all monomials avoiding the monomials from the set of relations. In general, there is no such elegant description; to obtain one, one uses the machinery of Gröbner bases. A Gröbner basis is a special choice of a set of relations that allows one to find a “monomial replacement” for the given algebra A, that is, an algebra with the same generators and with monomial relations for which the natural monomial basis is also a basis for A. Such a set of monomial relations is provided by the “leading terms” of the relations forming a Gröbner basis.

It is very natural to try and find an appropriate Gröbner bases theory for operads. For operads with symmetries, this turns out to be impossible: not every symmetric operad has a monomial replacement. However, for shuffle operads it turns out to be possible. Let us be a little bit more precise. Similarly to the case of associative algebras, a shuffle operad can be presented via generators and relations, that is, as a quotient of the free operad ℱ (V), where V is the space of generators (which itself is a non-symmetric collection). If X is the collection of ordered bases for components of V, that is, a functor from Ord to Ord, then the free shuffle operad generated by V admits a basis of “tree monomials” which can be defined combinatorially; they are precisely planar X-labelled rooted trees studied throughout this paper. Any shuffle composition of tree monomials is again a tree monomial. The crucial feature of shuffle operads is that they admit good monomial orderings (and therefore one can talk about leading terms of relations). More precisely, there exist several ways to introduce a total ordering of tree monomials in such a way that all the shuffle compositions respect that total ordering: increasing one of the monomials we compose increases the result. Furthermore, the algebraic statement that a tree monomial T is obtained from another tree monomial S by shuffle compositions (that is, T is divisible by S in our monoid) means, in combinatorial language, that S occurs in T as a pattern.

We now have all the ingredients to relate questions about shuffle operads to pattern avoidance in trees. A Gröbner basis of an ideal I in the free shuffle operad is a system G of generators of I for which the leading monomial of every element of I is divisible by one of the leading terms of elements of G. Such a system of generators allows one to perform “long division” modulo I, computing for every element its canonical representative. Tree monomials avoiding the leading terms of elements of G (“normal monomials”) form a basis in the quotient by the ideal I; in other words, shuffle operads do admit monomial replacements. Thus, it is clear that enumerating trees avoiding the given set of patterns literally corresponds to computing dimensions of components of operads presented by generators and relations. (Of course, the first step is to compute a Gröbner basis; see [8] for an algorithmic approach to this problem.) From this point of view, asymptotic enumeration is also very meaningful: in fact, the area of operad theory primarily concerned with quotients of the operad describing associative algebras (better known as “theory of varieties of associative algebras”) has asymptotic questions (“codimension growth”) among its core questions [15, 21]. There were even some attempts to use the Gröbner bases formalism in that context, see for example [27]. We expect that our approach will prove useful in that context.

References

1. Roland Bacher and Gilles Schaeffer, On generating series of coloured planar trees, Sém. Lothar. Combin. 55 (2005/07), Art. B55e, 20 pp.

2. Eric Babson and Einar Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. 44 (2000), Art. B44b, 18 pp.

3. Jason P. Bell and Teow Goh, Exponential lower bounds for the number of words of uniform length avoiding a pattern, Inform. and Comput. 205 (2007), no. 9, 1295–1306.

4. Jason P. Bell and Lance W. Small, A question of Kaplansky, J. Algebra 258 (2002), no. 1, 386–388.

5. Anders Claesson, Generalized pattern avoidance, European J. Combin. 22 (2001), no. 7, 961–971.

6. Vladimir Dotsenko, Freeness theorems for operads via Gröbner bases, Séminaires et Congrès, 26 (2011), 61–76.

7. Vladimir Dotsenko and Anton Khoroshkin, Free resolutions via Gröbner bases,

   preprint arχiv:0912:4895.

8. Vladimir Dotsenko and Anton Khoroshkin, Gröbner bases for operads, Duke Math. J., 153 (2010), no. 2, 363–396.

9. Vladimir Dotsenko and Anton Khoroshkin, Shuffle algebras, homology, and consecutive pattern avoidance, preprint arχiv:1109.2690.

10. Richard Ehrenborg, Sergey Kitaev and Peter Perry, A spectral approach to consecutive pattern-avoiding permutations, Ann. Combin. (to appear); preprint

arχiv:1009.2119.

11. Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math. 36 (2006), no. 2, 138–155.

12. Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. in Appl. Math. 30 (2003), no. 1-2, 110–125, Formal power series and algebraic combinatorics (Scottsdale, AZ, 2001).

13. Nathan Gabriel, Katherine Peske, Lara Pudwell and Samuel Tay, Pattern Avoidance in Ternary Trees, preprint arχiv:1110:2225.

14. Ira Gessel and Richard P. Stanley, Stirling polynomials, J. Combinatorial Theory Ser. A 24 (1978), no. 1, 24–33.

15. Antonio Giambruno and Mikhail Zaicev, Polynomial identities and asymptotic methods, Mathematical Surveys and Monographs 122, American Mathematical Society, Providence, RI, 2005. xiv+352 pp.

16. Victor Ginzburg and Mikhail Kapranov, Koszul duality for operads, Duke Math. J. 76 (1994), no. 1, 203–272.

17. Evgeny S. Golod and Igor R. Shafarevich, On the class field tower, Izv. Akad. Nauk SSSR Ser. Mat. 28 (1964), 261–272.

18. Eric Hoffbeck, A Poincaré–Birkhoff–Witt criterion for Koszul operads, Manuscripta Math. 131 (2010), no. 1-2, 87–110.

19. Vít Jelínek and Toufik Mansour, On pattern-avoiding partitions, Electron. J. Combin. 15 (2008), no. 1, Art. R39, 52 pp.

20. Ian P. Goulden and David M. Jackson, An inversion theorem for cluster decompositions of sequences with distinguished subsequences, J. London Math. Soc. (2) 20 (1979), no. 3, 567–576.

21. Alexei Kanel-Belov and Louis Halle Rowen, Computational aspects of polynomial identities, Research Notes in Mathematics 9, A K Peters, Ltd., Wellesley, MA, 2005. xxii+378 pp.

22. Anton Khoroshkin and Dmitri Piontkovski, On generating series of finitely presented operads, in preparation.

23. Anton Khoroshkin and Boris Shapiro, Using homological duality in consecutive pattern avoidance, Electron. J. Combin. 18 (2011), vol. 2, Art. P9, 17 pp.

24. Sergey Kitaev, Patterns in permutations and words, Monographs in Theoretical Computer Science, Springer, 2011.

25. Martin Klazar, Counting pattern-free set partitions. I. A generalization of Stirling numbers of the second kind, European J. Combin. 21 (2000), no. 3, 367–378.

26. Martin Klazar, On growth rates of permutations, set partitions, ordered graphs and other objects, Electron. J. Combin. 15 (2008), no. 1, Art. R75, 22 pp.

27. Victor N. Latyshev, Combinatorial generators of multilinear polynomial identities, J. Math. Sci. (N. Y.) 149 (2008), no. 2, 1107–1112.

28. Jean-Louis Loday, Inversion of integral series enumerating planar trees, Sém. Lothar. Combin. 53 (2005), Art. B53d, 16 pp.

29. Toufik Mansour, Pattern avoidance in coloured permutations, Sém. Lothar. Combin. 46 (2001/02), Art. B46g, 12 pp. (electronic).

30. Anthony Mendes and Jeffrey Remmel, Permutations and words counted by consecutive patterns, Adv. in Appl. Math. 37 (2006), no. 4, 443–480.

31. Brian Nakamura, Computational approaches to consecutive pattern avoidance in permutations, Pure Math. Appl. (to appear); preprint arχiv:1102.2480.

32. John Noonan and Doron Zeilberger, The Goulden-Jackson cluster method: extensions, applications and implementations, J. Differ. Equations Appl. 5 (1999), no. 4-5, 355–377.

33. Susan F. Parker, The combinatorics of functional composition and inversion, Ph.D. thesis, Brandeis (1993).

34. Dmitri Piontkovski, On the Kurosh problem in varieties of algebras, Fundam. Prikl. Mat. 14 (2008), no. 5, 171–184.

35. Narad Rampersad, Further applications of a power series method for pattern avoidance, Electronic J. Comb. 18(1), 2011, article P134, 8 pp.

36. Eric Rowland, Pattern avoidance in binary trees, J. Combin. Theory Ser. A 117 (2010), no. 6, 741–758.

37. Bruce Sagan, Pattern avoidance in set partitions, Ars Combin. 94 (2010), 79–96.

38. Neil J. A. Sloane, On-line encyclopedia of integer sequences, Available via the URL

   http://www.research.att.com/∼njas/sequences/.

39. Richard Stanley, Enumerative combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999. xii+581 pp.

40. Victor A. Ufnarovskij, Combinatorial and asymptotic methods in algebra, Algebra, VI, Encyclopaedia Math. Sci., vol. 57, Springer, Berlin, 1995, pp. 1–196.

41. Richard Warlimont, Permutations avoiding consecutive patterns, Ann. Univ. Sci. Budapest. Sect. Comput. 22 (2003), 373–393.

42. Herbert S. Wilf, The patterns of permutations, Discrete Math. 257 (2002), no. 2-3, 575–583.

Mathematics Research Unit, University of Luxembourg, Campus Kirchberg, 6, Rue Richard Coudenhove-Kalergi, L-1359 Luxembourg, Grand Duchy of Luxembourg

  E-mail address: vladimir.dotsenko@uni.lu