{'fraction_non_alphanumeric': 0.05783249033025885, 'fraction_numerical': 0.021347813150847963, 'mean_word_length': 3.6585239085239087, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Finitely labeled generating trees and restricted permutations

Generating trees are a useful technique in the enumeration of various combinatorial objects, particularly restricted permutations. Quite often the generating tree for the set of permutations avoiding a set of patterns requires infinitely many labels. Sometimes, however, this generating tree needs only finitely many labels. We characterize the finite sets of patterns for which this phenomenon occurs. We also present an algorithm - in fact, a special case of an algorithm of Zeilberger - that is guaranteed to find such a generating tree if it exists.


Introduction
The standardization of a word w consisting of k distinct integers is the permutation st(w) of length k obtained by replacing the smallest entry of w by 1, the second smallest entry by 2, and so on. If β ∈ S k , we say that the length n word of distinct integers w contains a β-pattern if and only if it contains a (not necessarily contiguous) subword whose standardization is β. Otherwise we say that w is β-avoiding. For example, the permutation 239145678 contains a 312-pattern (for example, the subword 916 standardizes to 312) but avoids 321. If B is a set of permutations, we say that the word w avoids B if it avoids every member of B. Such a set B is often referred to as a set of forbidden patterns. Although we have allowed w to be a word in our definition, we are most interested in the case where w is a permutation. Let Av n (B) denote the set of B-avoiding permutations of length n and let Av(B) denote the set of all finite B-avoiding permutations. We refer to n | Av n (B)|x n as the generating function for Av(B).
The problem of enumerating restricted permutations has received considerable attention over the last two decades. Bóna's book [8] provides an overview of these efforts. A common technique is that of generating trees, introduced by Chung, Graham, Hoggatt, and Kleiman [12] and used extensively by many others 1 since. The recently introduced ECO (enumerating combinatorial objects) method 2 extends the notion of generating trees to other combinatorial contexts. There has also been some interest in the algebraic properties of generating trees and ECO systems 3 .
Precisely, a generating tree is a rooted, labeled, and typically infinite tree such that the label of a node determines the labels of its children. Sometimes the labels of the tree are taken to be natural numbers, but this is not necessary, and the algorithm we will describe labels nodes by The connection to restricted permutations comes through pattern-avoidance trees. We say that the permutation σ of length n is a child of π ∈ S n−1 if σ can be obtained by inserting n into π. This defines a rooted tree T on the set of all permutations. For a set of patterns B, we define the pattern-avoidance tree T (B) to be the subtree of T whose nodes are the B-avoiding permutations Av(B). For example, the first four levels of T (132, 3241) are shown in Figure 1. The active sites (relative to B) of π ∈ Av n−1 (B) are the positions i for which inserting n right before the ith entry of π produces a B-avoiding permutation. By convention, n + 1 is an active site of π if appending n to the end of π produces a B-avoiding permutation. An inactive site is any site that is not active. For example, the active sites of 213 relative to B = {132, 3241} are 1 and 4, whereas the inactive sites are 2 and 3.
Given a pattern-avoidance tree T (B), we would like to find an isomorphic (in the category of rooted trees) generating tree. For example, take a permutation π ∈ Av n (132, 3241). There are at most three sites in which we may insert n + 1 to form a {132, 3241}-avoiding child: the beginning, the end, and the site directly to the right of n. Indeed, if we insert n + 1 to the left of n but not at the beginning we form a 132-pattern, while if we insert n + 1 further than one site to the right of n but not at the end we get a subsequence n, x, (n + 1), y and either x < y, giving a 132-pattern, or x > y, giving a 3241-pattern. We can therefore constuct an isomorphic generating tree with just two labels, label (2) for the nodes where n is the last entry and label (3) for the nodes where n is not the last entry. The generating tree is then Root: (2) Rules: (2) ( On the other hand, the pattern-avoidance tree T (123) requires infinitely many labels; by considering the lexicographically first ascent in a 123-avoiding permutation one can show that T (123) is isomorphic to the generating tree given by Root: (2) Rules: (j) (2)(3) · · · (j + 1).
Upon finding a generating tree isomorphic to T (B), one often wishes to get the generating function for Av(B). In general, as witnessed by Bousquet-Mélou [9] and Banderier, Bousquet-Mélou, Denise, Flajolet, Gardy, and Gouyou-Beauchamps [3], this process can be quite intricate. However, if the generating tree has only finitely many labels then the generating function for Av(B), which must be rational, can be computed using the transfer matrix method (see Stanley's text [32,Section 4.7] for details).
Herein we characterize the finite sets B for which T (B) is isomorphic to a finitely labeled generating tree, answering a question raised earlier [34]. One requirement for T (B) to be isomorphic to a finitely labeled generating tree is that there must be a bound on the number of children a node of T (B) may have. For this to occur, B must contain both a child of an increasing permutation (such as 132, 4123, or 12345) and a child of a decreasing permutation (such as 231, 3241, or 54321), because otherwise either 12 · · · n or n · · · 21 will have n + 1 children for all n. In fact, Kremer and Shiu [22] showed that this is enough. We include a short proof below. First recall the following famous theorem of Erdős and Szekeres.
Theorem 2 (Kremer and Shiu [22]). The pattern-avoidance tree T (B) has bounded degrees if and only if B contains both a child of an increasing permutation and a child of a decreasing permutation.
Proof. We have already noted that the condition on B is necessary, so it suffices to show that it is sufficient. Assume not, so that although B contains a child of 12 · · · k and a child of ℓ · · · 21, T (B) does not have bounded degrees. Set n = (k − 1)(ℓ − 1) + 1.
By construction, σ is a permutation of length n with n + 1 children in T (B), proving the claim. However, by our choice of n, the Erdős-Szekeres theorem shows that σ contains either an increasing subsequence of length at least k or a decreasing subsequence of length at least ℓ. Thus we have reached a contradiction because our assumptions on B imply that at least one of the children of σ most contain a pattern from B and thus cannot be a node of T (B).
In general, trees with bounded degrees need not be isomorphic to finitely labeled generating trees. For example, consider the generating tree (pictured in Figure 2) given by where nodes labeled by (0) do not produce children. This tree is clearly not isomorphic to a finitely labeled generating tree since the distance between two nodes of degree 2 is unbounded, but each of its nodes has at most two children. Our main result, Theorem 7, says that if B is finite and T (B) has bounded degrees then T (B) is isomorphic to a finitely labeled generating tree, so this example shows that our proof will need to make use of the special properties of pattern-avoidance trees.
In the next section we introduce lemmas and notation for pattern-avoidance trees. Section 3 describes our labeling algorithm, while the proof that this algorithm works is contained in Section 4.

Removable & GT-reducible entries
In order to motivate our technique we begin by returning to the example of T (132, 3241). Since our approach in the last section was rather ad hoc, we now attempt to analyze this tree (5,5) (4, 1) . . .

Figure 2.
A tree with bounded degrees that is not isomorphic to a finitely labeled generating tree (or rather, two of its nodes) in a more systematic manner. Consider 213. In this permutation we can insert new maximal entries at the beginning or the end, but we will never be able to insert a new maximal entry between the 2 and the 3. Now let π denote a descendant of 213. From our previous comments, 213 appears as a contiguous block in π. Observe that for any possible 132 or 3142-pattern in π involving the 1 there is another pattern which uses the 2 instead. Therefore it does not matter whether or not the 1 is stuck between the 2 and the 3, and we can assign the same label to 213 as we assign to 12. In fact, a similar argument shows that 12 can be labeled by the same label as 1 receives. It is notions like these that we aim to formalize in this section.
First, we say that an entry x in the permutation π is removable (relative to a set of patterns B) if it is adjacent to at most one active site. For example, every entry of 213 is removable when B = {132, 3241}, although no entry of 21 is removable. When more detail is needed, we say that the entry π(i) is left-removable if i is an inactive site of π and right-removable if i + 1 is inactive, so every removable entry is either left-removable, right-removable, or both.
If x is an entry of the word w and w contains distinct integers then we write w − x to denote the word formed from w by removing x. For example, 461523 − 2 = 46153. If X is a set of entries of w, we similarly write w − X to denote the word formed by removing each entry in X.
When π is a node of T (B) we let T (B; π) denote the subtree consisting of π and its descendants. In order to avoid the shifting of indices and values caused by standardization we will also make use of the similar but less natural tree W (B; n, u), which we define whenever u is a B-avoiding word containing distinct integers all at most n. The root of W (B; n, u) is u, and it contains all B-avoiding words w that can be formed by shuffling u with a permutation on [n + 1, n + |w| − |u|]. If v and w are nodes of W (B; n, u) and w has greatest entry m, then w is a child of v if w can be obtained by inserting m into v, that is, if v = w − m. An example is shown in Figure 3. For a word w ∈ W (B; n, u) we define active sites, inactive sites, removability, left-removability, and right-removability as we did for the permutations of T (B).
Once these definitions are unraveled, it is evident that W (B; n, u) ∼ = T (B; st(u)) for all allowed values of n, and if π is a permutation then W (B; |π|, π) and T (B; π) are not merely isomorphic, but they are the same tree.
If u is a word of length at least two containing the entry x we define the map by ∂ x (w) = w − x. Our upcoming Proposition 3 shows that ∂ x is one-to-one if x is a removable entry in u. There are several different cases in the definition of the inverse map. First suppose that x = u(i) for some i > 2. In this case we define the map u,x (w) will contain at least one pattern from B. There are three more cases for us to define this operation. If x = u(1) then we simply let Otherwise we let ι + u,x (w) denote the word formed from w by inserting x to the immediate left of u(i + 1). Proposition 3. Let u be a B-avoiding word of length at least two containing distinct integers all at most n and suppose that x ∈ u is removable.
is the identity, and if x is right-removable then is the identity.
Proof. As the various cases are quite similar, let us assume that x = u(i) for some i > 2 and that x is left-removable. Take w ∈ W (B; n, u). Since x is left-removable, w cannot contain an entry between u(i − 1) and x. Thus applying ∂ x removes x, but then ι − u,x inserts x immediately to the right of u(i − 1), restoring w.
One of the implications of Proposition 3 is that W (B; n, u) embeds into W (B; n, u − x) by the map ∂ x whenever x is a removable entry of u. It sometimes happens that these two trees are isomorphic. If W (B; n, u) ∼ = W (B; n, u − x), and x is removable, then we say that x is generating-tree-reducible relative to B, or for short, GT-reducible. This is a strengthening of Zeilberger's definition of reversely deleteable entries from [37]. In this language, our observation at the beginning of the section was that the entry 1 in 213 is GT-reducible for B = {132, 3241}. If the permutation π contains a GT-reducible entry, we also refer to π as being GT-reducible.
Before ending our discussion of ι, let us note that in many cases these maps commute: Remark 4. Let u be a word containing distinct integers all at most n, let x and y be nonadjacent entries of u, and let δ, ǫ ∈ {+, −}. Then as maps from W (∅; n, u − x − y) to W (∅; n, u).
We would now like to show that it is possible to decide whether a removable entry is GTreducible. For this we need two more definitions. Given a tree T , let ℓ i (T ) denote the number of nodes of T of height i, so ℓ 0 (T ) = 1 unless T is the empty tree, ℓ 1 (T ) is the number of children of the root node, and ℓ 2 (T ) is the number of grandchildren of the root node. Also, if B is a finite set of patterns, let B ∞ denote the length of the longest pattern in B.
Proposition 5. Let u be a B-avoiding word of length at least two containing distinct integers all at most n. The removable entry x ∈ u is GT-reducible if and only if Proof. If x ∈ u is GT-reducible then W (B; n, u) ∼ = W (B; n, u−x) by definition, so ℓ r (W (B; n, u)) = ℓ r (W (B; n, u − x)) for all r ∈ N. Suppose now that ℓ r (W (B; n, u)) = ℓ r (W (B; n, u − x)) for all 1 ≤ r ≤ B ∞ − 1. Since x is removable, Proposition 3 shows that W (B; n, u) embeds into W (B; n, u − x) by the map ∂ x . Thus we would like to show that this map is onto.
Suppose not and choose w ∈ W (B; n, u − x) that is not in the image of ∂ x . Let ǫ = − if x is left-removable in u. Otherwise x must be right-removable in u, and here we let ǫ = +. Since w / ∈ ∂ x (W (B; n, u)), ι ǫ u,x (w) contains a permutation from B. Choose a subword of ι ǫ u,x (w) that standardizes to a member of B and label it v. Because w avoids B, x must be an entry of v.
Now consider the subword w ′ of ι ǫ u,x (w) containing all entries that are either in u or in v. Because w ′ contains v, it contains a pattern from B. However, w ′ − x is a subword of w, so it avoids B. We would like to find a word in ι ǫ u,x (W (B; n, u − x)) with these properties. We do this by "partially standardizing" w ′ : replace the smallest entry of w ′ that is not in u by n + 1, the next smallest entry of w ′ that is not in u by n + 2, and so on. Label the resulting word w ′′ . Notice that w ′′ ∈ ι ǫ u,x (W (B; n, u − x)), w ′′ contains a pattern from B, and w ′′ − x is B-avoiding. These observations and Proposition 3 show that ℓ |w ′′ |−|u| (W (B; n, u)) < ℓ |w ′′ |−|u| (W (B; n, u − x)).

The algorithm
Our work in the previous section suggests the following approach for finding a generating tree isomorphic to T (B). If 1 / ∈ Av(B) then our task is quite easily accomplished, so let us assume that 1 avoids B. We start with a root node (1), a set P = {1} of permutations that we have not checked for GT-reducible entries, and a set R = ∅ of succession rules. Now we pick a permutation π ∈ P of minimum length and check it for GT-reducible entries (we make the convention that the permutation 1 never has a GT-reducible entry).
If instead π has a GT-reducible entry x then we again remove π from P , but now we search through our set of succession rules R and replace each instance of (π) by the label we have given to the node st(π − x) (this label might not be (st(π − x)) because st(π − x) may also have a GT-reducible entry). In other words, whenever a node labeled by (π) would have been produced, now a node labeled by the same label as st(π − x) will be produced. This does not change the isomorphism type of the tree because T (B; π) = W (B; |π|, π) ∼ = W (B; |π|, π − x) ∼ = T (B; st(π − x)).
We repeat this process until P = ∅. If we ever reach this state then we know that the generating tree we have produced is isomorphic to T (B). We will prove shortly (Theorem 7) that we do reach this state when B contains both a child of an increasing permutation and a child of a decreasing permutation.
Before that, let us illustrate the process with the tree T (132, 3241). We start with P = {1} and R = ∅. Then we choose 1 from P and note that it does not have a GT-reducible entry (by our convention), so we remove 1 from P and add 12 and 21 to P , giving us P = {12, 21}. We also add the rule (1) (12) (21) to our set of rules R. Now choose 12 from P . First we check to see if 1 is a GT-reducible entry. Since B ∞ = 4, Proposition 5 shows that we only need to test whether ℓ r (W ({132, 3241}; 2, 2)) and ℓ r (T ({132, 3241}; 12)) agree for r = 1, 2, 3. The number are shown in the following chart. r ℓ r (W ({132, 3241}; 2, 2)) ℓ r (T ({132, 3241}; 12)) 1 2 2 2 5 5 3 13 13 From this chart we may conclude that 1 is a GT-reducible entry, so we remove 12 from P and we replace (12) by (1) in all of our rules. After this we have P = {21} and R contains the single rule (1) (1)(21).
We must now choose 21 from P . However, 21 does not have any removable entries, so it is not GT-reducible. We therefore remove 21 from P , add its children (321, 231, and 213) to P , and add the rule (21) (321)(231)(213) to R. Using the same process as with 12 we can find that both 321 and 231 have GT-reducible entries (the entry 2 is GT-reducible for both permutations), so we replace (321) and (231) in all our rules by (21).
At this point we have P = {213}. This permutation also has a GT-reducible entry (again, 2) so if we were to follow the pattern of the previous cases we would simply replace all instances of (213) in our set of rules by (12). However, since 12 is GT-reducible itself we instead replace instances of (213) by (1).
We are now done because P = ∅, and we have found the generating tree Up to relabeling, this is the same tree we found in Section 1. Via the transfer matrix method, one can use these rules to compute the generating function for Av(132, 3241): and thus the sequence | Av n (132, 3241)| contains every second Fibonacci number.

Proof of the main result
It remains to show that this procedure terminates. In fact, if the nodes of T (B) have arbitrarily large degrees, then we will never reach a state where P = ∅, because in that case either 12 · · · n or n · · · 21 will never have a removable entry, let alone a GT-reducible entry. Our central result, Theorem 7 below, shows that if B is finite and T (B) has bounded degrees then this procedure will terminate.
We begin with a technical lemma that will be used to construct large sets of entries satisfying a condition stronger than removability.
Lemma 6. Suppose that B is a finite set of patterns containing both a child of an increasing permutation and a child of a decreasing permutation and fix a positive integer r. Every sufficiently long B-avoiding permutation π contains a set X = {x 1 , . . . , x r } of r distinct pairwise nonadjacent entries so that each x j is removable in the word π − (X \ {x j }).
Proof. We prove the lemma by induction on r. The base case r = 1 is immediate because Theorem 2 implies that all sufficiently long permutations contain removable entries, and we may take x 1 to be any removable entry in π.
Let π be a B-avoiding permutation of length n. The r = 2 case provides a nice illustration of our argument, so we examine it before moving on to the general case. Let y 1 , . . . , y s denote the removable entries in π − x 1 that are not adjacent to x 1 in π, and assume to the contrary that x 1 is not removable in π − y i for any i ∈ [s]. Because x 1 is removable in π, at least one of the sites adjacent to x 1 in π is inactive. Now form the B-containing permutation σ by inserting n + 1 into π in an inactive site adjacent to x 1 . Because x 1 is not removable in π − y i , σ − y i is B-avoiding. But this means that every copy of a pattern from B in σ must contain the entry y i and the entry n + 1, so s ≤ B ∞ − 1. On the other hand, Theorem 2 shows that we may take s to be as large as we like so long as n is sufficiently large, a contradiction. Now suppose that r is any integer at least 2, and that we have found a set of entries {x 1 , . . . , x r−1 } satisfying the desired conditions. We wish to find an entry x r , not adjacent to any of the entries x 1 , . . . , x r−1 , so that {x 1 , . . . , x r } satisfies the desired conditions. As in the r = 2 case before, we begin by letting y 1 , . . . , y s denote the removable entries of π−x 1 −· · ·−x r−1 that are not adjacent (in π) to any x i . Assume to the contrary that none of the y i 's will function adequately as x r , so for each i ∈ [s] there is at least one j ∈ [r −1] such that x j is not removable in π − x 1 − · · · − x j−1 − x j+1 − · · · − x r−1 − y i . Choose one of these values to be denoted j(i).
When we were trying to find an entry to serve as x 2 we built a single permutation σ. This time we need to consider the r − 1 permutations σ 1 , . . . , σ r−1 where σ j is formed by inserting n + 1 into π in an inactive site adjacent to x j and then removing x 1 , . . . , x j−1 , x j+1 , . . . , x r−1 . Each of these permtuations contains a pattern from B and by our assumptions, σ j(i) −y i avoids B for each i ∈ [s]. As before, we now ask how many different values of i can share the same value j(i). The answer is the same: every copy of a pattern from B in σ j(i) must contain both y i and n + 1, so at most B ∞ − 1 values of i may share the same j(i). Therefore we need only have s > (r − 1)( B ∞ − 1), which we get if n is sufficiently large, to guarantee that at least one of the y i 's can serve as x r , completing the proof of the claim.
Theorem 7. Let B be a finite set of patterns. The pattern-avoidance tree T (B) is isomorphic to a finitely labeled generating tree if and only if B contains both a child of an increasing permutation and a child of a decreasing permutation. Furthermore, if T (B) satisfies these conditions then the algorithm presented in Section 3 will find a finitely labeled generating tree isomorphic to T (B).
Proof. These conditions on B are necessary by Theorem 2. To prove the other direction, it suffices to show that every sufficiently long permutation is GT-reducible. Take π to be a Bavoiding permutation of length n. We prove the theorem by showing that if r is sufficiently large then at least one of the removable entries x 1 , . . . , x r guaranteed by Lemma 6 must be GT-reducible.
If x j is left-removable in π − (X \ {x j }), set ǫ j = −. Otherwise x j must be right-removable in π − (X \ {x j }) and we set ǫ j = +. Suppose to the contrary that no x j is GT-reducible, and thus for every j ∈ [r] there is some v j ∈ W (B; n, π − x j ) so that w j = ι ǫ j π,x j (v j ) contains a pattern from B. In fact, Propositions 3 and 5 show that we may assume |w j | ≤ n + B ∞ − 1.
Each copy of a pattern from B in w j must use the entry x j since ∂ x j (w j ) = v j is B-avoiding. Hence at most B ∞ different x j 's may share the same w j . Therefore it would suffice to show that the number of w j 's is bounded by some constant depending only on the set B. To accomplish this we will show that each w j lies in the set • ∂ x 1 as maps from W (B; n, π − x j ) to W (∅; n, π). Proposition 3 implies that this would follow from π−x 1 −···−x j ,x j+1 • · · · • ι ǫr π−x 1 −···−x r−1 ,xr , and this follows from Remark 4 because the x i 's are pairwise nonadjacent.
Theorem 7 only applies when the set of forbidden patterns B is finite. It can be shown that this hypothesis is necessary. First note that if β 1 , β 2 ∈ B where β 2 contains a β 1 pattern then T (B) = T (B \ {β 2 }), or in other words, the β 2 restriction is superfluous. Thus we may always assume that B = min(B), where here min(B) denotes the minimal elements of B with respect to the pattern containment ordering. It is not immediately obvious that there are sets of permutations B such that min(B) is not finite. Equivalently: are there infinite antichains of permutations? Indeed, as has been rediscovered numerous times during the past thirty-five years, there are. The reader is referred to Atkinson, Murphy, and Ruškuc [2] for constructions and references to earlier work.
In particular, Av(321, 4123) contains an infinite antichain. Following the argument given in Murphy's thesis [26] one can show that there is a set of the form Av(B) where 321, 4123 ∈ B that does not have a rational generating function. In more detail, there is an infinite antichain U ⊆ Av(321, 4123) with at most one member of each length. If U 1 and U 2 are two different subsets of U then Av(321, 4123, U 1 ) and Av(321, 4123, U 2 ) have different generating functions. Because U is infinite, this gives uncountably many distinct generating functions, and thus they cannot all be rational. In particular, these trees cannot all be finitely labeled.

Conclusion
The algorithm presented here is implemented in the Maple package FinLabel available at http://math.rutgers.edu/~vatter/. This algorithm is -up to symmetry -only a special case of the algorithm of Zeilberger [37]. More precisely, if FinLabel can find a generating tree isomorphic to T (B) then Zeilberger's package Wilf can enumerate B −1 -avoiding permutations. Our algorithm has the advantage that, in the cases that it can handle, it returns both a generating tree and generating function, whereas Zeilberger's algorithm only returns a polynomial time algorithm for computing | Av n (B)|. On the other hand, Zeilberger's algorithm is applicable in many other situations. For example, it can enumerate the 1234-avoiding permutations, which are known to have a non-algebraic generating function (Gessel [19]). Zeilberger's algorithm is extended in Vatter [33].
Since the writing of this paper, the enumerative implication of Theorem 7 has been generalized by Albert, Linton, and Ruškuc [1]. They introduce a correspondence between permutations and words called the insertion encoding and prove that if B satisfies the hypotheses of Theorem 7 (in fact, weaker hypotheses suffice for their theorem) then the set of insertion encodings of permutations from Av(B) forms a regular language. It then follows from the theory of formal languages that Av(B) has a rational generating function.
We conclude with several results that can now be proved completely automatically using the FinLabel package. First we have results from the classical paper of Simion and Schmidt [28]: generating function for Av(B)

{132, 213, 231}
x (x−1) 2 West [36] undertook a systematic study of permutations that avoid one pattern of length three and another of length four. The generating functions that our algorithm can rederive are listed in the chart below.

B
generating function for Av(B) Finally we have permutations that avoid two patterns of length four. The following generating functions, recently computed by Kremer and Shiu [22], can also be found using FinLabel.