David Callan
email: callan@stat.wisc.edu

Toufik Mansour
email: tmansour@univ.haifa.ac.il

Mark Shattuck
email: shattuck@math.utk.edu

ENUMERATION OF PERMUTATIONS AVOIDING A TRIPLE OF 4-LETTER PATTERNS IS ALL DONE

Keywords: pattern avoidance, Wilf-equivalence, generating function, INSENC algorithm 2. Preliminaries

published or not. The documents may come

Introduction

This paper is the last in a series whose goal is to enumerate the permutations avoiding the patterns in T for each of the 24 3 triples T of 4-letter patterns. There are 317 symmetry classes of these triples and 242 Wilf classes; hence, 242 distinct counting sequences. A Wilf class is said to be small or large depending on whether it contains one or more symmetry classes. The symmetry classes in large Wilf classes were enumerated in [START_REF] Callan | Wilf classification of triples of 4-letter patterns I[END_REF][START_REF] Callan | Wilf classification of triples of 4-letter patterns II[END_REF] (combined in [START_REF] Callan | Wilf classification of triples of 4-letter patterns[END_REF]). The small Wilf classes that can be enumerated by the insertion encoding algorithm (INSENC) [START_REF] Vatter | Finding regular insertion encodings for permutation classes[END_REF] are listed in Table 2 in the appendix. The small Wilf classes not amenable to INSENC are listed in Table 1 below along with a reference to either a published paper or to a result in the present paper. The numbering in both tables follows that of Table 2 in [START_REF] Callan | Wilf classification of triples of 4-letter patterns[END_REF], where representative triples for all 317 symmetry classes are listed in lex order of counting sequence. The generating function for Case 237, the only one not enumerated, is conjectured not to be differentially algebraic (see, e.g., [14, Seq. A257562]).

Our work extends earlier results concerning the enumeration of permutations avoiding one or two 4-letter patterns. Permutations avoiding a single 4-letter pattern have been well studied (see, e.g., [START_REF] Stankova | Forbidden subsequences[END_REF][START_REF] Stankova | Classification of forbidden subsequences of length four[END_REF][START_REF] West | Generating trees and the Catalan and Schröder numbers[END_REF]), and there are 56 symmetry classes of pairs of 4-letter patterns, all but 8 of which have been enumerated. Le [START_REF] Le | Wilf classes of pairs of permutations of length 4[END_REF] established that these 56 symmetry classes form 38 distinct Wilf classes, and of these 38, 12 can be enumerated with regular insertion encodings (see [START_REF] Vatter | Finding regular insertion encodings for permutation classes[END_REF]). Some of these generating functions were computed by hand by Kremer and Shiu [START_REF] Kremer | Finite transition matrices for permutations avoiding pairs of length four patterns[END_REF]. In [START_REF] Simion | Restricted permutations[END_REF], Simion and Schmidt enumerated permutations avoiding any subset of S 3 , in particular, any subset of S 3 of size three. Our results here then address the analogous problem on S 4 and complete the enumeration in the case of three patterns.

The organization of this paper is as follows. In the next section, we recall some previous terminology and notation. In the third section, we provide proofs of generating function formulas corresponding to the final thirteen symmetry classes for three patterns of length four. In the appendix, the generating functions for all small Wilf classes that can be done using INSENC are listed. with m left-right maxima i 1 , i 2 , . . . , i m = n; thus F T (x) = m≥0 G m (x). Note that G 1 (x) = xF T (x) if no pattern in T starts with 4, with G 0 (x) = 1. For several of the triples T , our efforts are directed toward finding an expression for G m (x), usually distinguishing the case m = 2, and sometimes also m = 3, from larger values of m. In cases such as these where we make use of the method of generating functions, we examine the structure of an avoider by splitting the class of avoiders into subclasses according to a judicious choice of parameters. This choice is made so that each member of a subclass can be decomposed into independent parts. The generating function (g.f) for a subclass (a summand in the full g.f.) is then the product of the g.f.'s for each of the individual parts, and we speak of the "contribution" of the various parts to the g.f. for the subclass. By contrast, in cases 74, 125 and 185, prior to computing the g.f., we determine an explicit formula that directly enumerates the class of avoiders in question. To do so, we consider appropriate combinatorial parameters related to the class, which involve here the position of and/or the actual letters contained within the leftmost ascent. The g.f. then follows from the explicit formula and a calculation, one that often involves multiple sums and is computer-assisted. In the last three cases, we make use of (and modify in one case) the method of generating forests [START_REF] West | Generating trees and the Catalan and Schröder numbers[END_REF] to determine a system of functional equations satisfied by the related g.f.'s, which we then solve by the kernel method (see, e.g., [START_REF] Hou | Kernel method and linear recurrence system[END_REF]).

Throughout, C(x) = 1- √ 1-4x 2x
denotes the g.f. for the Catalan numbers

C n := 1 n+1 2n n = 2n n - 2n n-1 .
As is well known [START_REF] Knuth | The Art of Computer Programming[END_REF][START_REF] Wikipedia | Permutation pattern[END_REF], C(x) is the g.f. for (|S n (π)|) n≥0 where π is any one of the six 3-letter patterns. The identity C(x) = 1 1-xC(x) or, equivalently, xC(x) 2 = C(x) -1, is used to simplify some of the results. Occasionally, we need the g.f. for avoiders of a 3-letter and a 4-letter pattern; see [START_REF] Wikipedia | Enumerations of specific permutation classes[END_REF] for a comprehensive list.

3. Proofs 3.1. Case 74: {1234, 1243, 3412}. Recall within a permutation π = π 1 π 2 • • • π n that an index i for which π i < π i+1 is called an ascent. The letters π i and π i+1 are referred to as the ascent bottom and ascent top, respectively. The leftmost ascent is the smallest j such that π j < π j+1 and the leftmost ascent bottom and top are the corresponding letters π j and π j+1 , respectively. For example, if π = 87436512, then π has ascents at indices 4 and 7 and the leftmost ascent top and bottom are 6 and 3, respectively. Similar terminology applies when discussing the rightmost ascent.

Suppose that a permutation π = π 1 • • • π n has its leftmost ascent at index i. Then we will refer to the prefix π 1 • • • π i as the initial descent sequence (IDS). For example, if π = 64325178, then the leftmost ascent occurs at index 4 and the IDS is 6432. Let T = {1234, 1243, 3412}. To enumerate members of S n (T ), we will classify them according to the value of the leftmost ascent bottom and the nature of the IDS. We first enumerate the following restricted class of T -avoiders.

Lemma 1. The number of T -avoiding permutations of length n whose first letter is ≤ n -2, whose leftmost ascent top is n, and whose IDS does not comprise a set of consecutive integers is given by On the other hand, if (iii) holds, then x (and hence all elements of [b -1] in π ′ ) must follow b + 1, for otherwise there would be a 3412 of the form (s -1)sx(b + 1) if x came between s and b + 1 or a 1243 of the form axs(b + 1) if x occurred prior to s. Thus, there are

b n = n-4 a=1 n-2 b=a+2 b-a m=2 b -a -1 m -2 (b -m + 1)(n -b -1) + n -b -2 2 , n ≥ 5.
n-1 s=b+3 s-1 t=b+2 1 = n-1 s=b+3 (s -b -2) = n -b -2 2
possibilities for π ′ satisfying (iii). In all cases, there are b-a-1 m-2 choices for the letters a 1 > • • • > a m-2 . Note that for each choice of the a i , the number of possibilities for π ′ is the same. Furthermore, any permutation π of the form (*) above, where π ′ satisfies (i), (ii) or (iii), is seen to avoid T . Considering all possible a, b and m then yields b n members of B n altogether. Hence,

b n = 1 12 (n -2)(3 • 2 n -(n -1)(n 2 -3n + 12)),
which completes the proof.

We now consider a class of T -avoiding permutations where the IDS consists of consecutive integers.

Lemma 2. The number of T -avoiding permutations of length n whose first letter is ≤ n -2, whose leftmost ascent top is n, and whose IDS comprises a set of consecutive integers is given by

(n -5)2 n-1 + n + 1 2 + 3, n ≥ 3.
Proof. Suppose π = π 1 • • • π n is of the form under consideration where n ≥ 3 and that π has leftmost ascent at index m with π m = a. Then the first m letters of π are a + m -1, a + m -2, . . . , a, where 1 ≤ a ≤ n -2 and 1 ≤ m ≤ na -1. Elements of [a -1] must decrease within π in order to avoid 3412. On the other hand, elements of [a + m, n] satisfy conditions (i), (ii) or (iii) as described in the proof of the previous lemma (where b is taken there to be a + m -1). If (i) holds, then it is seen that members of [a -1] may be placed (in decreasing order) following any of the elements of [a + m, n] within π without introducing an occurrence of T . Thus, there are in this case n-m-1 a-1 possible π given a and m. This implies that there are a total of

n-2 a=1 n-a-1 m=1 n -m -1 a -1 = n-2 a=1 n -1 a -1 = 2 n-1 -n
permutations in this case. If (ii) holds, then letters in [a -1] again may be inserted following any members of [a + m, n], whereas if (iii) holds, then one cannot place letters in [a -1] directly after s or members of [a + m + 1, t -1] in order to avoid 3412. Thus in (ii), there as nam + 1 possible places to insert letters in [a -1], while in (iii), there are nt + 1 such places.

For each a and m, considering all s and t yields

n-2 t=a+m n-1 s=t+1 n -t + a -1 a -1 = n-1 t=a+m n -t + a -1 a -1 (n -t -1) = n t=a+m n -t + a -1 a -1 (n -t -1) + 1 = n t=a+m n -t + a -1 a -1 (n -t + a) -(a + 1) n -m a + 1 = a n -m + 1 a + 1 -(a + 1) n -m a + 1 = f (a, m)
possible permutations for (ii) and (iii) combined. Summing over all possible a and m then gives

n-2 a=1 n-a-1 m=1 f (a, m) = n-2 a=1 n-a m=1 f (a, m) = n-2 a=1 a n + 1 a + 2 -(a + 1) n a + 1 + n -a = n-1 a=0 (a + 2) n + 1 a + 2 -(a + 1) n a + 1 -2 n + 1 a + 2 + n -a = (n + 1)(2 n -1) -n2 n-1 -2(2 n+1 -n -2) + n + 1 2 = (n -6)2 n-1 + n + 3 + n + 1 2 .
Combining this with the prior case (i) completes the proof.

Lemma 3. The number of T -avoiding permutations of length n whose leftmost ascent top is n -1 is given by Combining the two preceding cases implies that the number of permutations under consideration for which S does not consist of consecutive integers is given by ways in which to arrange the members of [a -1], which must decrease. One can verify that permutations π obtained in this manner are T -avoiding. Considering all a, m and t gives

d n = (n + 8)2 n-3 + 1 - n + 2 2 - (n -1)(n -2)(2n -3) 6 , n ≥ 3.
n-4 a=1 n-2 b=2 b-a m=2 b -a -1 m -2 (n -m -1) = n-3 m=2 (n -m -1) n-2 b=m+1 b-m a=1 b -a -1 m -2 = n-3 m=2 (n -m -1) n-2 b=m+1 b -1 m -1 -1 = n-3 m=2 (n -m -1) n -2 m -(n -m -1) = 2 n-2 -n + n-3 m=2 (n -2) n -3 n -m -3 - n-3 m=2 (n -m -1) 2 = n2 n-3 -n + 1 - n-2 m=1 m 2 = n2 n-3 -n + 1 - (n -1)(n -2)(2n -3) 6 , n ≥ 4. Now assume S = {a, a + 1, . . . , a + m -1} for some 1 ≤ a ≤ n -2 and 1 ≤ m ≤ n -a -1.
n-2 a=1 n-a-1 m=1 n-1 t=a+m n -t + a -1 a -1 = n-2 a=1 n-a-1 m=1 n -m a -1 = n-2 a=1 n a + 1 -(n -a) = 2 n - n + 1 2 -1
possibilities. Combining this case with the previous yields d n permutations in all.

Let a n = |S n (T )|. We may express a n in terms of the b n and d n sequences as follows, where we take b n = 0 if n ≤ 4.

Lemma 4. If n ≥ 2, then (1)
a n = a n-1 + (2n -9)2 n-2 + 3 + n + 1 2 + b n + n-3 m=0 d n-m ,
with a 1 = 1, where b n and d n are as defined above.

Proof. We enumerate the remaining cases of S n (T ). Let π ∈ S n (T ) and not of a form described in Lemmas 1-3, where n ≥ 3. If π starts with n, then there are clearly a n-1 possibilities. Since members of S n (T ) starting with a letter ≤ n -2 must have leftmost ascent top either equal to n -1 or n, the only remaining case is if π starts with n -1, which we now assume. If the leftmost ascent top of π is n, then π = (n -1)ρ ′ nρ ′′ , where ρ ′ and ρ ′′ are possibly empty and decreasing. This gives 2 n-2 possible π. So assume π has leftmost ascent top nm -1 for some 1 ≤ m ≤ n -3. Since any ascent top of π is either the largest or second largest letter yet to appear (otherwise 1234 or 1243 would be present), it follows that π must start n -1, n -2, . . . , nm. These letters are seen to be extraneous concerning the avoidance of T and thus may be deleted (note that they impose no restrictions when considering 3412 since nm -1 is the first ascent top). This leaves a permutation of the form enumerated by d n-m . Considering all possible m then yields n-3 m=1 d n-m possibilities. Combining the additional cases discussed here with those from Lemmas 1-3 completes the proof.

By Lemmas 1, 3 and 4, we have

a n = a n-1 + (2n -9)2 n-2 + 3 + n + 1 2 + 1 12 (n -2)(3 • 2 n -(n -1)(n 2 -3n + 12)) + n-3 m=0 (n -m + 8)2 n-m-3 + 1 - n -m + 2 2 - (n -m -1)(n -m -2)(2n -m -3) 6 ,
which is equivalent to

a n = a n-1 + (n -1)2 n - 1 6 (n -1)(n 3 -3n 2 + 14n -6), n ≥ 2,
with a 1 = a 0 = 1. Hence, we can state the following result.

Theorem 5. Let T = {1234, 1243, 3412}. Then

F T (x) = 1 -9x + 35x 2 -75x 3 + 98x 4 -78x 5 + 36x 6 -12x 7 (1 -x) 6 (1 -2x) 2 .

3.2.

Case 121: {1243, 2341, 3412}. We need the following lemmas.

(x) = d≥1 N d (x) (1-x) d . Then N (x) = x 3 (1 -6x + 15x 2 -21x 3 + 15x 4 -3x 5 ) (1 -x) 4 (1 -2x) 2 (1 -3x + 1 + x 2 ) .
Proof. Refine N d (x) to N d,e counting avoiders where π ′ has e letters. Since π avoids 1243 and d ≥ 1, we see that π ′ is decreasing.

Let π = (n -d -1)π ′ nπ ′′ ∈ S n (T ) such that π ′′ contains the subsequence (n -1)(n -2) • • • (n -d) and π ′ contains e letters, say π ′ = j e j e-1 • • • j 1 . To find N 1 (x), write π ′′ as α(n-1)β. If α = ∅, then β is decreasing and the contribution is x e+3 (1-x) e+1 .
Otherwise, the maximal letter of α is between j s-1 and j s for some s ∈ [e + 1] where j 0 = 0 and j e+1 = n -2. Since π avoids 1243 and 2341, j s-1 < β < j s . The letters in π ′′ smaller than n -2 are decreasing. Thus, by considering whether β is empty or not, we obtain a contribution of x e+4

(1-x) s + x e+5 (1-x) 2 for 2 ≤ s ≤ e + 1, and of x e+4 (1-x) 2 for s = 1. Hence,

N 1,e (x) = x e+3 (1 -x) e+1 + e+1 s=2 x e+4 (1 -x) s + x e+5 (1 -x) 2 + x e+4 (1 -x) 2 , which leads to N 1 (x) = e≥0 N 1,e (x) = x 3 (1 -3x + 4x 2 -3x 3 ) (1 -x) 4 (1 -2x) . (2)
For d ≥ 2, by a decomposition similar to the case d = 1, we see that

N d,e (x) = xN d-1,e (x) + x d+e+3 (1 -x) d+1 .
Summing over e ≥ 0, we obtain for d ≥ 2,

N d (x) = xN d-1 (x) + x d+3 (1 -x) d+2 .
Multiplying by 1 (1-x) d and summing over d ≥ 2, we have

N (x) - N 1 (x) 1 -x = x 1 -x N (x) + d≥2 x d+3 (1 -x) 2d+2 .
Now use [START_REF] Callan | On permutations avoiding 1243, 2134, and another 4-letter pattern[END_REF] and solve for N (x) to complete the proof. Lemma 7. Define M (x) to be the generating function for permutations

π = iπ ′ nπ ′′ ∈ S n (T ) with 2 left-right maxima such that i ≤ n -2. Then M (x) = x 3 (1 -6x + 16x 2 -25x 3 + 20x 4 -5x 5 ) (1 -x) 4 (1 -2x) 2 (1 -3x + x 2 ) .
Proof. Let M d (x) denote the generating function for permutations π = iπ ′ nπ ′′ ∈ S n (T ) with 2 left-right maxima such that π ′′ contains the subsequence (n -1)

• • • (n -d) and i ≤ n -d -1.
Clearly, M 1 (x) = M (x). Since π avoids 1243, there is no letter greater than i between n and nd + 1. Thus, all letters greater than i in π ′′ must occur to the right of nd + 1. We denote the subsequence comprising these letters by γ.

To find M d (x), write γ as α(nd)β. In cases (i) α = β = ∅, (ii) α = ∅ and β = ∅, (iii) α = ∅ and β = ∅, we have the contributions (i) N d (x), (ii) xM d (x), (iii) M d+1 (x), respectively. Thus, we may assume that α, β = ∅. Note first that i + 1 must occur in β, for otherwise i(i + 1) is a 12 within a 1243, and by similar reasoning β < α. Thus, α and β form decreasing subsequences since π avoids 2341 and 3412, which implies αβ is decreasing. Furthermore, no letter in [i -1] can occur to the right of nd, for otherwise there would be an occurrence of 2341 of the form i(n

-d -1)(n -d)i ′ for some i ′ ∈ [i -1].
From the preceding observations, we see that π can be expressed as follows:

π = i(i -1) • • • i ′ nγ (1) (n -1)γ (2) • • • γ (d-1) (n -d + 1)γ (d) (n -d -1) • • • γ (e-1) (n -e) γ (e) (n -d)(n -e -1) • • • (i + 1)
,

where e ≥ d + 1, i ≥ i ′ > γ (1) • • • γ (e) and γ (1) • • • γ (e)
is decreasing (for otherwise, 1243 would be present). Thus, we have a contribution of e≥d+1

x e+3

(1-x) e+2 =

x d+4

(1-x) d+2 (1-2x) . Hence

M d (x) = N d (x) + xM d (x) + M d+1 (x) + x d+4 (1 -x) d+2 (1 -2x) , which implies M d (x) = 1 1 -x N d (x) + 1 1 -x M d+1 (x) + x d+4 (1 -x) d+3 (1 -2x) .
Multiplying by

M d (x) (1 -x) d-1 = N (x) + d≥1 M d+1 (x) (1 -x) d + d≥1 x d+4 (1 -x) 2d+2 (1 -2x) ,
which is equivalent to

M 1 (x) = N (x) + d≥1 x d+4 (1 -x) 2d+2 (1 -2x) ,
and the result follows from Lemma 6.

Lemma 8.

G 2 (x) = x 2 F T (x) + x 3 (2 -14x + 42x 2 -70x 3 + 64x 4 -27x 5 + 4x 6 ) (1 -x) 4 (1 -2x) 2 (1 -3x + x 2 ) . Proof. Clearly, G 2 (x) = M (x) + H(x)
, where H(x) is the generating function for permutations

π = (n -1)π ′ nπ ′′ ∈ S n (T ). Since (n -1)π ′ n avoids T if and only if π ′ avoids T , G 2 (x) = M (x) + x 2 F T (x)+H ′ (x)
, where H ′ (x) is the generating function for permutations π = (n-1)π ′ nπ ′′ ∈ S n (T ) where π ′′ is nonempty. By similar arguments as in the proofs of Lemmas 6 and 7, one can show that

H ′ (x) = x 3 (1-2x+2x 2 ) (1-x) 3 (1-2x
) and the result follows using Lemma 7.

Theorem 9. Let T = {1243, 2341, 3412}. Then

F T (x) = 1 1 -3x + x 2 + 1 1 -x + 1 -x + x 2 (1 -x) 4 - 2(1 -x)(1 -2x -x 2 ) (1 -2x) 3 .
Proof. To find G m (x) with m ≥ 3, let π = i 1 π (1) • • • i m π (m) ∈ S n (T ) with m ≥ 3 left-right maxima.

Since π avoids T , we see that π (s) = ∅ for all s ≥ 4, with i 1 < π (3) < i 2 . If π (3) = ∅, then we have a contribution of x m-2 G 2 (x). Otherwise, the letters in π (1) π (2) smaller than i 1 are decreasing and the letters of π (2) π (3) between i 1 and i 2 are decreasing. Thus, we have a contribution of

x m+1 (1-x) 2 (1-2x) . Hence, G m (x) = x m-2 G 2 (x) + x m+1 (1 -x) 2 (1 -2x)
.

Summing over m ≥ 3, we obtain

F T (x) -1 -xF T (x) -G 2 (x) = x 1 -x G 2 (x) + x 4 (1 -x) 3 (1 -2x) ,
and the result follows by substituting for G 2 (x) and solving for F T (x).

3.3. Case 125: {1243, 2341, 4123}. We treat this case in 4 subsections. If 1 ≤ i ≤ n -1, then let C ′ n,i denote the number of 123-avoiding permutations of length n whose leftmost ascent occurs at index i, with C ′ n,n = 1. The numbers u n may be expressed explicitly in terms of C ′ n,i as follows.

Lemma 10. We have

(3) u n = C n-2 + n-2 a=2 n-2-a t=0 n -2 -a t u ′ (n -t, a), n ≥ 3,
where

u ′ (m, a) = a-1 i=1 i + m -2 -a i C ′ a-1,i , 2 ≤ a ≤ m -2.
Proof. Clearly, there are C n-2 permutations avoiding T that start n -1, n. So let π ∈ S n (T ) be a permutation enumerated by u n having leftmost ascent bottom a ≤ n -2. Then π is either of the form π = (n -1)a 1 a 2 To complete the proof of (3), we need to establish the formula above for u ′ (m, a). To do so, let ρ ∈ S m (T ) be of the form enumerated by u ′ (m, a). Then ρ = (m -1)amρ ′ for some permutation

ρ ′ of [a -1] ∪ [a + 1, m -2].
Note that ρ ′ is 123-avoiding with all letters in [a + 1, m -2] descending since ρ avoids 4123. Thus, ρ ′ may be obtained by inserting letters from

[a + 1, m -2] within a 123-avoiding permutation λ of [a -1]. Suppose λ = λ 1 λ 2 • • • λ a-1 , with the first ascent of λ occurring at index i (where i = a -1 if λ = (a -1) • • • 21). Since ρ ′ avoids 123, no letter from [a + 1, m -2]
may be inserted beyond the (i + 1)-st letter of λ. Also, letters are to be inserted in decreasing order, with letters preceding λ allowed. Since there are i + 1 positions in which to insert the letters from [a + 1, m -2], it follows that there are i+m-2-a i possible ρ for each λ whose first ascent occurs at index i. One may verify that permutations ρ so obtained avoid T . Considering all 1 ≤ i ≤ a -1 yields the desired formula for u ′ (m, a) and completes the proof.

Let C n,i denote the number of 123-avoiding permutations of length n having first letter i. Let q(x, y) = n≥1 n i=1 C n,i x n y i and ℓ(x, y) = n≥1 n i=1 C ′ n,i x n y i . Then the latter may be expressed in terms of the former as follows.

Lemma 11. We have

(4) ℓ(x, y) = xy (1 -xy) 2 q x 1 -xy , 1 -xy + xy 1 -xy .
Proof. We refine C ′ a,i according to the leftmost ascent bottom. That is, let C ′ a,i,j denote the number of 123-avoiding permutations π of length a with leftmost ascent at index i and leftmost ascent bottom j. Note that C ′ a,i,j can only be non-zero when 1 ≤ j ≤ ai. Furthermore, any letters of π coming prior to j are extraneous concerning avoidance of the patterns in T and thus may be deleted, as can the leftmost ascent top. This leaves a permutation of the form enumerated by C a-i,j . Upon selecting the first i -1 letters of π, which must belong to [j + 1, a], yields the formula

C ′ a,i = a-i j=1 C ′ a,i,j = a-i j=1 a -j i -1 C a-i,j , 1 ≤ i ≤ a -1, with C ′ a,a = 1. Thus we have ℓ(x, y) = a≥1 C ′ a,a (xy) a + a≥2 a-1 i=1   a-i j=1 a -j i -1 C a-i,j   x a y i = xy 1 -xy + a≥2 a-1 i=1   i j=1 a -j i -j + 1 C i,j   x a y a-i = xy 1 -xy + i≥1 i j=1 C i,j a≥i+1 a -j i -j + 1 x a y a-i = xy 1 -xy + xy (1 -xy) 2 i≥1 i j=1 C i,j x 1 -xy i (1 -xy) j ,
which implies (4).

Note that from [START_REF] Firro | Three-letter-pattern avoiding permutations and functional equations[END_REF], we have

q(x, y) = xy(1 -yC(xy)) 1 -x -y . (5)
We now calculate the generating function u(x) = n≥3 u n x n , which will be needed later.

Lemma 12. We have

(6) u(x) = x 2 (C(x) -1) + (1 -x)r x 1 -x , 1 -x , where r(x, y) = x 4 y 2 (1 -x -xy) 2 q xy(1 -x) 1 -x -xy , 1 -x -xy 1 -x + x 4 y 2 (1 -x)(1 -x -xy) . Proof. First note that n≥4 n-2 a=2 u ′ (n, a)x n y a = n≥4 n-2 a=2 a-1 i=1 C ′ a-1,i i + n -2 -a i x n y a = a≥2 a-1 i=1 C ′ a-1,i y a n≥a+2 i + n -2 -a i x n = a≥2 a-1 i=1 C ′ a-1,i x a+2 y a (1 -x) i+1 = x 3 y 1 -x a≥1 a i=1 C ′ a,i (xy) a (1 -x) i = x 3 y 1 -x ℓ xy, 1 1 -x = x 4 y 2 (1 -x -xy) 2 q xy(1 -x) 1 -x -xy , 1 -x -xy 1 -x + x 4 y 2 (1 -x)(1 -x -xy) ,
where we have used (4) in the final equality. Next observe that

n≥4 n-2 a=2 n-2-a t=0 n -2 -a t u ′ (n -t, a)x n y a = a≥2 n≥a+2 n t=a+2 n -2 -a n -t u ′ (t, a)x n y a = a≥2 t≥a+2 u ′ (t, a)y a n≥t n -2 -a t -2 -a x n = a≥2 t≥a+2 u ′ (t, a) x t y a (1 -x) t-a-1 = (1 -x) t≥4 t-2 a=2 u ′ (t, a) x 1 -x t ((1 -x)y) a = (1 -x)r x 1 -x , (1 -x)y .
Multiplying both sides of (3) by x n , and summing over n ≥ 3, then gives

u(x) = x 2 (C(x) -1) + n≥4 n-2 a=2 n-2-a t=0 n -2 -a t u ′ (n -t, a) x n = x 2 (C(x) -1) + (1 -x)r x 1 -x , (1 -x)y | y=1 ,
which implies [START_REF] Callan | Wilf classification of triples of 4-letter patterns II[END_REF].

Now let b n denote the number of T -avoiding permutations of length n whose leftmost ascent is of the form a, n for some 2 ≤ a ≤ n -1. For example, b 3 = 1 (for 231) and b 4 = 5 (for 2413, 2431, 3241, 3412 and 3421). Then we have the following recurrence formula.

Lemma 13. We have

(7) b n = b n-1 + u n + 2 n-3 -n + 2 + n -2 4 + n-4 j=0 n-3-j i=1 n -i -2 j + 1 C n-2-j,i , n ≥ 3,
with b 2 = 0, where u n is given by (3) above.

Proof. Let π be a member of S n (T ) enumerated by b n . If the first letter of π is n -1, then there are u n possibilities by definition, so assume n ≥ 4 and that the first letter of π is less than n -1.

Then π = a 1 a 2 • • • a j anπ ′ , where j ≥ 0 and 2 ≤ a < a j < • • • < a 1 ≤ n -2. Let S = {a 1 , . . . , a j }, where S is possibly empty. Note that π ′ is nonempty and let x denote the first letter of π ′ . If x = n -1, then it is seen that x may be deleted and there are b n-1 possibilities. Now suppose x ∈ [a -1]. Note that π ′ is 123-avoiding due to 4123. Furthermore, this is the only restriction on π ′ since n, x implies all letters in [a + 1, n -1] in π ′ must decrease, and thus no letter to the left of n can serve as a "2" within an occurrence of 2341 or as a "4" within a 4123. Also, x < a implies all elements of S ∪ {a} are extraneous concerning the avoidance of 1243 as well. Thus, these letters may all be deleted in addition to n, leaving a permutation of the form enumerated by

C n-2-j,i for some i ∈ [a -1]. Considering all 2 ≤ a ≤ n -2, 0 ≤ j ≤ n -2 -a and 1 ≤ i ≤ a -1 gives n-2 a=2 n-2-a j=0 a-1 i=1 n -2 -a j C n-2-j,i = n-4 j=0 n-3-j i=1 C n-2-j,i n-2-j a=i+1 n -2 -a j = n-4 j=0 n-3-j i=1 n -2 -i j + 1 C n-2-j,i
possibilities in this case.

Next let a + 1 ≤ x ≤ n -2. Here, we consider two cases on S. Note that S cannot comprise all of [a + 1, n -2] due to our assumption on x. First suppose S = [a + 1, s] ∪ [t, n -2] for some a ≤ s < t -1 ≤ n -2, where S = ∅ is possible. Then π ′ is of the form

π ′ = b 1 b 2 • • • b p (n -1)d 1 d 2 • • • d q ,
where p ≥ 1, q ≥ 0 and b 1 ∈ [a + 1, n -2]. Note that no elements of [a -1] can occur to the right of n-1, for otherwise there would be an occurrence of 2341 of the form ab 1 (n-1)z for some z ∈ [a-1].

Since letters occurring between n and n -1 within π are decreasing due to 4123, the final a -

1 letters b i must comprise [a -1]; that is, we have b p-a+2 = a -1, b p-a+2 = a -2, . . . , b p = 1.
Since a ≥ 2, the d i letters must also decrease in order to avoid 4123. Furthermore, all of the d i letters are less than all of the letters in [a + 1, n -2] occurring between n and n -1, for otherwise, there would be an occurrence of 1243 (with a and n -1 corresponding to the "1" and "4", respectively). Thus, the subsequence b

1 b 2 • • • b p-a+1 d 1 d 2 • • • d q comprises all elements of [a + 1, n -2]
occurring to the right of n within π in decreasing order, where p ≥ a and q is possibly zero. One may verify that the corresponding π of the stated form is T -avoiding. Considering all a and S implies that there are

n-3 a=2 n-3-a i=0 n-3-a-i j=0 (n -2 -a -i -j) = n-3 a=2 n-3-a i=0 n -1 -a -i 2 = n-3 a=2 n -a 3 = n -1 4 possibilities in this case. If S is not of the form [a + 1, s] ∪ [t, n + 2], then there must exist some v 1 < u < v 2 all belonging to [a + 1, n -2] such that u ∈ S and v 1 , v 2 / ∈ S. If π ′ = b 1 • • • b p (n -1)d 1 • • • d q is as before, with q > 0, then b 1 ≥ v 2 > u and d q ≤ v 1 < u implies ub 1 (n -1)d q is a
2341, which is impossible. Thus q = 0 and there is only one way in which to arrange the letters within π to the right of n, i.e., letters in [n -2] -S in decreasing order followed by a -1, . . . , 1, n -1. By subtraction, there are for n ≥ 4,

n-3 a=2   2 n-2-a -1 - n-3-a i=0 n-3-a-i j=0 1   = 2 n-3 -(n -2) - n-3 a=2 n -1 -a 2 = 2 n-3 -(n -2) - n -2 3
possible members of S n (T ) in this case. Combining all of the previous cases gives (7).

3.3.2.

Case II. Let d n denote the number of T -avoiding permutations of length n not starting with n whose leftmost ascent is of the form a, n -1 for some 2 ≤ a ≤ n -2. Note, for example, d 5 = 6, the enumerated permutations being {24135, 24153, 24315, 32415, 34125, 34215}. Then d n may be expressed in terms of b n as follows.

Lemma 14. We have We now consider the various cases considered in the proof of recurrence [START_REF] Callan | Wilf classification of triples of 4-letter patterns[END_REF] above in an effort to determine any further members of

(8) d n = d n-1 + b n-1 -b n-2 + n -3 2 + n-3 a=3 n-3-a ℓ=0 n-2-a-ℓ m=1 n -5 -ℓ -m a -3 m, n ≥
D n . Let π ∈ B ′ n-1 .
If the first letter of π is n -2, then n must be added as the final letter (in order to avoid 2341), and hence there are no additional members of D n coming from this case (beyond those already accounted for by b n-1b n-2 above). So assume henceforth that the first letter of π is less than n -2, and write π = π ′ a(n -1)π ′′ , where a ≥ 2 is the leftmost ascent bottom. Let y be the first letter of π ′′ . First assume a + 1 ≤ y ≤ n -3. Then the element 1 must (directly) precede n -2 within π ′′ , or π would contain 2341. Thus, the letter n cannot be inserted between n -1 and y, for otherwise there is an occurrence of 2341, and it cannot be inserted anywhere between y and n -2 either due to 1243 occurring in that case. If n were to be inserted to the right of n -2, but not at the very end of π, then there would be a 2341 in which the roles of "2" and "3" are played by the letters y and n -2, respectively. Thus, no additional members of

D n arise if y ∈ [a + 1, n -3]. Now assume y ∈ [a -2]
and let z denote the last letter of π ′′ . Note that z = y since π ′′ has length at least two. Then z must belong to [a -3] ∪ {a -1} since π ′′ is 123-avoiding, which again implies one must add n to the very end of π to create a member of D n (in order to avoid an occurrence of 2341 as witnessed by the subsequence a(n -1)nz). So assume henceforth y = a -1. Still, no additional members of D n are possible if z ∈ [a -2], so assume henceforth z > a. We now consider cases on π ′ . First suppose that π ′ does not comprise [a + 1, a + ℓ] for some 0 ≤ ℓ ≤ n -3a. The there exist a + 1 ≤ u < v ≤ n -3 with u / ∈ π ′ and v ∈ π ′ . Then u ≥ z since z is seen to be the smallest element of [a + 1, n -3] in π ′′ . Thus, adding n anywhere except at the very end of π produces an occurrence of 2341, as witnessed by v(n -1)nz.

So assume π ′ comprises [a + 1, a + ℓ] for some ℓ. If a ≥ 3, then π may be written as

π = (a + ℓ) • • • (a + 1)a(n -1)(a -1)ρ1(a + ℓ + m) • • • (a + ℓ + 2)(a + ℓ + 1), n ≥ 6,
for some 1 ≤ m ≤ n -2aℓ, where ρ consists of the remaining letters of [n -1]. Since the set of letters to the right of n -1 within π form a 123-avoiding permutation, with the last letter greater than the first, the subsequence ρ consists of alternating runs of letters from the disjoint sets [2, a -2] and [a + ℓ + m + 1, n -2], where the subsequences of π comprising the letters from these sets are decreasing (in order to avoid 4123). Thus, selecting the positions of the elements of [2, a -2] uniquely determines ρ, which can be done in n-5-ℓ-m a-3

ways. In this case, n may be inserted directly prior to any of the elements of [a + ℓ + 1, a + ℓ + m] and the resulting permutation is seen to always belong to S n (T ). Considering all possible a, ℓ and m gives

n-3 a=3 n-3-a ℓ=0 n-2-a-ℓ m=1 n -5 -ℓ -m a -3 m
members of D n that have not been enumerated already. If a = 2, then we have Lemma 15. We have [START_REF] Hou | Kernel method and linear recurrence system[END_REF] e n = e n-1

π = (ℓ + 2) • • • 32(n -1)1(n -2)(n -3) • • • (ℓ + 3), n ≥
+ d n-1 + C n-2 -2 n-3 + n-2 i=3 (d i+1 -b i ), n ≥ 4,
with e 3 = 0, where b n and d n are determined by [START_REF] Callan | Wilf classification of triples of 4-letter patterns[END_REF] and (8).

Proof. Let π be a permutation enumerated by e n , where n ≥ 5. To show ( 9

, one gets C b -C b-1 -2 b-2 possibilities for each b. Summing over 3 ≤ b ≤ n -2 gives n-2 b=3 C b -C b-1 -2 b-2 = C n-2 -2 n-3
possible π in this case. Finally, assume y = n. Then π must start n -1, n -2, . . . , b + 1. To show this, suppose it is not the case and let q ∈ [b + 1, n -1] lie to the right of b. Note that any letter to the right of n within π must be less than b so as to avoid 1243. In particular, q must lie between b and n. Since y = n, there exists a letter r to the right of n. But then bqnr is a 2341, which is impossible. Furthermore, one may verify, without using any letters to the left of a, that any elements of [a + 1, b -1] to the right of b within π must decrease. Thus, it is seen that the letters n -1, n -2, . . . , b + 1 impose no restriction on the subsequent letters of π when considering the pattern 4123. The same can be said for the patterns 1243 and 2341, which implies that these letters are extraneous concerning the avoidance of T and thus may be deleted. Doing so leaves a permutation of length b + 1, not starting or ending with b + 1, whose leftmost ascent is of the form a ≤ b, where a ≥ 2. Considering all possible b gives n-2 i=3 (d i+1b i ) possibilities in this case, by subtraction, which completes the proof.

3.3.4. Case IV. Let g n denote the number of T -avoiding permutations of length n not starting with n whose leftmost ascent is of the form 1, a for some a > 1.

Lemma 16. We have [START_REF] Knuth | The Art of Computer Programming[END_REF] g

n = g n-1 + 5 • 2 n-3 + n -1 4 -n + n-1 m=3 n -m + 1 2 2 m-3 , n ≥ 3, with g 2 = 1. Proof. Recurrence (10) is clear if n = 3, so assume n ≥ 4. Let π = a 1 a 2 • • • a s 1π ′ be of the form enumerated by g n , where 1 < a s < a s-1 < • • • < a 1 ≤ n -1
, and let S = {a 1 , a 2 , . . . , a s }. We consider several cases on S. If S = ∅, then π = 1π ′ where π ′ avoids {132, 2341, 4123}, and hence there are 2 n-1n + 1 possibilities. So assume S = ∅. If a s = 2, then deleting 2 gives g n-1 possibilities. Henceforth assume a s ≥ 3. We will refer to letters in [a 1 + 1, n] as large and those belonging to [2, a 1 ] -S as small. Note that π ′ contains both large and small letters.

Large letters to the left of any small letters within π ′ must decrease (due to 2341), while large letters to the right of any small letters must increase (1243). The small letters themselves must decrease, for otherwise there would be a 4123 starting with a 1 , 1. It is not possible for there to exist two or more large letters occurring between the greatest and the least of the small letters, for otherwise π would contain 1243 or 2341. Assume now that there is exactly one such large letter. In order for this to occur, the set S must be an interval of the form [ℓ, ℓ + s -1], where 4 ≤ ℓ ≤ n -1 and 1 ≤ s ≤ nℓ. For if not, then the largest small letter y would exceed the smallest member x of S, which would introduce an occurrence of 2341 of the form xyz2 for some large letter z. Furthermore, any large letters occurring to the left of the first small letter must be less than any large letters occurring to the right of the last large letter in this case, for otherwise there would be an 4123 where the "1" and "2" correspond to the largest small and the smallest large letter, respectively. One may verify that a permutation satisfying all of the requirements above with respect to the large and small letters and to the set S is T -avoiding. Note that given ℓ there are ℓ -3 possible positions in which to place the smallest large letter since it must go between two small letters. If the leftmost large letter within π ′ is denoted by nt, where 0 ≤ t ≤ nℓs, then considering all possible ℓ, s and t yields

n-1 ℓ=4 n-ℓ s=1 n-ℓ-s t=0 (ℓ -3) = n-4 s=1 n-4-s t=0 n-s-t ℓ=4 (ℓ -3) = n-4 s=1 n-4-s t=0 n -2 -s -t 2 = n-4 s=1 n -1 -s 3 = n -1 4
permutations in this case.

So assume that there is not a large letter between the greatest and the least of the small letters. We consider further cases on π ′ , which we write as π ′ = α 1 βα 2 , where β comprises the set of small letters. First assume that one of α 1 , α 2 is empty or that both are nonempty with min(α 2 ) > max(α 1 ). Let a 1 = m, where s + 2 ≤ m ≤ n -1. For each S with a 1 = m, there are nm + 1 possible π ′ upon choosing the length of (the interval) α 2 , which can be anywhere from 0 to nm (note that once S is specified, π ′ is uniquely determined in this case by |α 2 |). Also a s ≥ 3 implies that there are m-3 s-1 choices for the remaining elements of S. Since all permutations formed in this manner are seen to be T -avoiding, we get

n-3 s=1 n-1 m=s+2 (n -m + 1) m -3 s -1 = n-1 m=3 (n -m + 1) m-2 s=1 m -3 s -1 = n-1 m=3 (n -m + 1)2 m-3
possibilities in this case. Now assume that α 1 and α 2 are both nonempty, with min(α 2 ) < max(α 1 ). Then it must be the case that min(α 2 ) is the only letter in α 2 that is less than max(α 1 ), for if not, then there would be an occurrence of 4123. If max(α

1 ) = n -t, then 0 ≤ t ≤ n -m -2 where a 1 = m, with s + 2 ≤ m ≤ n -2.
The first letter of α 2 must then belong to [m + 1, nt -1], and thus there are nmt -1 choices for it. Considering all possible s, m and t yields

n-4 s=1 n-2 m=s+2 n-m-2 t=0 (n -m -t -1) m -3 s -1 = n-4 s=1 n-2 m=s+2 m -3 s -1 n -m 2 = n-2 m=3 n -m 2 2 m-3
additional permutations. Thus, the last two cases combined give

n-1 m=3 n -m + 1 2 + 1 2 m-3 = 2 n-3 -1 + n-1 m=3 n -m + 1 2 2 m-3
possibilities in all. Putting this together with the prior cases above implies [START_REF] Knuth | The Art of Computer Programming[END_REF].

For any of the sequence above, put zero if n is such that the corresponding set of permutations is empty. For example, we have d n = 0 for n ≤ 3. Combining cases I through IV above, and including permutations that start with the letter n, implies that the number of T -avoiding permutations of length n is given by ( 11)

a n = b n + d n + e n + g n + C n-1 , n ≥ 2,
with a 0 = a 1 = 1.

We now find a formula for the generating function

A(x) = n≥0 a n x n . Define B(x) = n≥2 b n x n , D(x) = n≥4 d n x n , E(x) = n≥3 e n x n and G(x) = n≥2 g n x n
. First we rewrite the recurrences in the preceding lemmas in terms of generating functions, by multiplying both sides by x n and summing over all possible n. By Lemmas 13-16, we obtain

B(x) = 1 1 -x u(x) + x 3 1 -2x - x 3 (1 -x) 2 + x 5 (1 -x) 5 - x 5 (1 -x) 4 + xq x 1 -x , 1 -x -xq(x, 1) , (12)
D(x) = xB(x) + x 5 (1 -x) 3 (1 -2x) , ( 13
) (1 -x)E(x) = xD(x) + x 2 C(x) -x 2 + x 3 + 2x 4 1 -2x + x 1 -x D(x) - x 2 1 -x B(x), (14)
G(x) = x 2 (1 -5x + 13x 2 -18x 3 + 13x 4 -6x 5 + x 6 ) (1 -x) 6 (1 -2x) , (15)
respectively. By solving ( 12)-( 14), along with use of (5) and Lemma 12, we obtain

B(x) = (1 -x)(C(x) -1) + x(3x 5 -8x 4 + 13x 3 -11x 2 + 5x -1) (1 -x) 6 , D(x) = x(1 -x)(C(x) -1) - x 2 (7x 6 -22x 5 + 37x 4 -36x 3 + 21x 2 -7x + 1) (1 -x) 6 (1 -2x) , E(x) = x 2 (2 -x) 1 -x (C(x) -1) - x 3 (8x 6 -29x 5 + 54x 4 -57x 3 + 36x 2 -13x + 2) (1 -x) 7 (1 -2x) .
By [START_REF] Kremer | Finite transition matrices for permutations avoiding pairs of length four patterns[END_REF], we have

A(x) = 1 + x + B(x) + D(x) + E(x) + G(x) + x(C(x) -1),
which, upon substituting the expressions just found for the generating functions B(x), D(x), E(x) and G(x), implies the following result.

Theorem 17. Let T = {1243, 2341, 4123}. Then

F T (x) = 1 -9x + 34x 2 -70x 3 + 87x 4 -65x 5 + 26x 6 -5x 7 (1 -x) 7 (1 -2x) + 1 1 -x C(x) -1 .
3.4. Case 149: {1234, 3412, 4123}. We enumerate directly T -avoiding permutations that have exactly two or three left-right maxima. Note that all members of E * n-ℓ in which the leftmost ascent top is not the final letter arise uniquely in this manner. If b = 1, then λ consists of two decreasing runs, the second of which is of length ℓ. To obtain λ ′ in this case, we delete the final ℓ -1 letters of λ, together with the first letter of λ if it exceeds the first letter of the second decreasing run; otherwise, we simply delete the final ℓ letters of λ prior to standardizing. Note that one obtains in this manner all members of E * n-ℓ that consist of two decreasing runs in which the second run is of length one, together with the decreasing permutation (nℓ)

g n = (3 -n)2 n-3 -1 + n-2 a=1 2 a-1 e n-1-a + n-1 a=2 2 n-1-a -1 - n -a 2 (a -1)2 a-2 + n-2 i=0 n -1 + i 2i + 1 + n-3 a=2 n-2-a ℓ=1 a-1 i=0 2 n-2-a-ℓ a -1 i ℓ + i i , n ≥ 3. ( 16
= 2 n-ℓ-1 for 1 ≤ ℓ ≤ n -1.
We now count members of S n (T ) that have two left-right maxima and are of the form π = aπ ′ nπ ′′ for some a ≥ 1 where π ′ is decreasing. There are clearly e n-2 possibilities if a = 1 and 2 n-2 possibilities if a = n -1, so assume n ≥ 4 and 2 ≤ a ≤ n -2. Let L denote the subsequence of π comprising the elements of [a + 1, n -1]. Then L is {123, 3412}-avoiding, with no letters in [a -1] occurring between n and the rightmost ascent bottom of L, for otherwise there is a 4123 of the form na ′ ℓ 1 ℓ 2 , where a ′ ∈ [a -1] and ℓ 1 , ℓ 2 comprise the rightmost ascent of L (viewed as a permutation in its own respect when discussing ascents). We consider cases on L. First suppose L (when standardized) belongs to E * n-1-a,ℓ for some ℓ. Let i denote the number of elements of [a -1] in π ′′ . Since π ′ is decreasing, there is no restriction on the choice of these elements. There are e * n-1-a,ℓ possibilities for L and ℓ+i i ways in which to arrange the elements of [a -1] occurring in π ′′ once π ′ and L are specified, since they must decrease (due to 3412) and occur to the right of the rightmost ascent bottom of L. Considering all possible a, ℓ and i, and treating separately the case when

ℓ = n -1 -a, gives n-2 a=2 n-1-a ℓ=1 a-1 i=0 a -1 i ℓ + i i e * n-1-a,ℓ = n -3 + n-3 i=1 n-2 a=i+1 a -1 i n -1 -a + i i + n-3 a=2 n-2-a ℓ=1 a-1 i=0 2 n-2-a-ℓ a -1 i ℓ + i i = n-2 i=0 n -1 + i 2i + 1 -2 n-2 -1 + n-3 a=2 n-2-a ℓ=1 a-1 i=0 2 n-2-a-ℓ a -1 i ℓ + i i
possible permutations and each is seen to be T -avoiding. On the other hand, if L does not belong to E * n-1-a , then the letters from [a -1] in π ′′ can always occur at the end (in descending order), which yields

n-2 a=2 2 a-1 (e n-1-a -e * n-1-a ) = n-2 a=2 2 a-1 e n-1-a -(n -3)2 n-3
permutations in this case.

We now entertain the possibility of x ∈ [a -1] occurring in a position of π ′′ other than beyond the rightmost letter of L when L does not belong to E * n-1-a . Note first that if the final letter q of a {123, 3412}-avoiding permutation ρ is part of an occurrence of 231, then one can always take the letter corresponding to the "3" within the occurrence to be the leftmost ascent top r of ρ. This is clear if the leftmost ascent bottom s of ρ exceeds q. On the other hand, if s < q, then since all letters greater than s and to the right of r decrease, the only possibility for the "2" in this case is some letter to the left of r, whence one may take r to be the "3" (since all letters to the left of r decrease). Thus if L contains more than one ascent, inserting x anywhere to the right of the rightmost ascent bottom of L other than beyond the rightmost letter of L is seen to introduce an occurrence of 3412, where the "4" and the "2" correspond to the leftmost ascent top and rightmost letter of L, respectively. Therefore, L must contain exactly one ascent in order for x to occur in a position prior to some letter in L. In this case, x can go either between the two letters comprising the ascent of L or beyond the last letter of L. Since at least one letter in [a -1] must be positioned prior to some letter in L (in order to distinguish permutations arising in this case from those of previous cases), there are a-1 i i ways in which to select and arrange the letters from [a -1] in π ′′ where i ≥ 1. Furthermore, there are

n-2-a j=2 n-1-a j
-(naj) possibilities for L, since the second (and final) decreasing run of L cannot comprise an interval (for otherwise, L would belong to E * n-1-a ). Considering all possible a, i and j yields

n-2 a=2 a-1 i=1 a -1 i i n-2-a j=2 n -1 -a j -(n -a -j) = n-1 a=2 2 n-1-a -1 - n -a 2 (a-1)2 a-2
additional permutations. Combining this case with the other cases gives [START_REF] Stankova | Classification of forbidden subsequences of length four[END_REF].

Let E n,ℓ ⊆ E n consist of those members whose final decreasing run (i.e., the letters to the right of and including the rightmost ascent top) is of length

ℓ for 1 ≤ ℓ ≤ n-1, with E n,n = {n(n-1) • • • 1}.
For example, we have E 4,2 = {2143, 3142, 3241, 4132, 4231} and E 4,3 = {1432, 2431, 3421}. We will need the following explicit formula for e n,ℓ = |E n,ℓ |.

Lemma 19. If n ≥ 2, then (17)
e n,ℓ = n-1-ℓ m=0 e ′ n-m,ℓ , 1 ≤ ℓ ≤ n -1,
where

e ′ n,ℓ = n -1 ℓ -1 + ℓ b=2 b-1 i=1 n-1-b r=ℓ+1-i r -2 -ℓ + b b -1 -i + n-1 b=ℓ+1 ℓ i=1 n-1-b r=ℓ+1-i r -2 -ℓ + b b -1 -i for 1 ≤ ℓ ≤ n -2, with e ′ n,n-1 = n -1 if n ≥ 2.
Proof. Let E ′ n,ℓ ⊆ E n,ℓ consist of those members whose leftmost ascent top is n, with e ′ n,ℓ = |E ′ n,ℓ |. Since the leftmost ascent top q of any π ∈ E n is the largest letter yet to be used, all elements of [q + 1, n] must appear as part of the initial decreasing run of π. Since these letters are seen to be extraneous concerning the avoidance of 123 and 3412, they may be deleted which implies e n,ℓ = n-ℓ-1 m=0 e ′ n-m,ℓ . To complete the proof, we establish the formula stated above for e ′ n,ℓ where 1 ≤ ℓ ≤ n -2, the ℓ = n -1 case being clear from the definitions. = n-1 ℓ-1 permutations π. So assume that there is at least one ascent to the right of n within π. Then π = π ′ bnπ ′′ , where π ′ is decreasing and π ′′ can be expressed as

π ′′ = ρ b (b -1)ρ b-1 (b -2) • • • ρ 2 1ρ 1 ,
where ρ i denotes a possibly empty sequence of letters. Let K denote the subsequence of π comprising the letters in

ρ b ∪ ρ b-1 ∪ • • • ∪ ρ 1 .
Then K is decreasing so as to avoid 123 and nonempty, by the assumption on π. First suppose 2 ≤ b ≤ ℓ and let i be the smallest index j such that ρ j = ∅. Note that 1 ≤ i ≤ b -1 since i = b is disallowed, for otherwise π ′′ would be decreasing contrary to our assumption. Also, ρ i contains exactly ℓ + 1i letters since the final decreasing run of π is to be of length ℓ. If r denotes the number of letters in K, then ℓ + 1i ≤ r ≤ n -1b, with K comprising the interval [nr, n -1] and the remaining elements of [b + 1, n -1] going in π ′ . For if not, then there would be would an occurrence of 3412 of the form xn(b -1)y for some

x, y ∈ [b + 1, n -1] with x > y. Note that the largest r -(ℓ + 1 -i) letters of K may be distributed amongst ρ b , ρ b-1 , . . . , ρ i+1 in r-2-ℓ+b b-1-i
ways. Considering all possible b, i and r yields Lemma 20. We have

ℓ b=2 b-1 i=1 n-1-b r=ℓ+1-i r -2 -ℓ + b b -1 -i permutations π and each is seen to belong to E ′ n,ℓ . If ℓ + 1 ≤ b ≤ n -1, then the index i satisfies 1 ≤ i ≤ ℓ,
b n = (7 -n)2 n-3 -2 + n-2 a=1 2 a-1 e n-1-a + n-3 a=2 n-2-a ℓ=1 a-1 i=0 2 n-2-a-ℓ a -1 i ℓ + i i + n-1 a=2 2 n-1-a -1 - n -a 2 (a -1)2 a-2 + n-1 a=3 a-2 ℓ=1 ℓ j=0 n -1 -a + j j e a-1,ℓ , n ≥ 3, ( 18
)
where e n-1-a and e a-1,ℓ are as defined above.

Proof. We count permutations π = aπ ′ nπ ′′ having two left-right maxima where π ′ is not decreasing, whence a ≥ 3. Then letters in [a + 1, n -1] must decrease, so as to avoid an occurrence of 1234. Let α denote the subsequence of π comprising the letters in [a -1]. Then α avoids {123, 3412}, and if α ∈ E a-1,ℓ for some ℓ where 1 ≤ ℓ ≤ a -2, then at most ℓ letters of α can lie within π ′′ (or else there would be an occurrence of 3412 starting with a, n). Suppose exactly j letters of α lie within π ′′ . If 0 ≤ j ≤ ℓ -1, then there are e a-1,ℓ possibilities for π ′ and n-1-a+j j ways to arrange the letters in π ′′ once π ′ is known since letters from both [a -1] and [a + 1, n -1] are decreasing in π ′′ , which uniquely determines π. This yields

n-1 a=3 a-2 ℓ=1 ℓ-1 j=0 n -1 -a + j j e a-1,ℓ
possible π and one may verify that each such π is T -avoiding. If j = ℓ, then the same reasoning applies except that now α must contain at least two ascents, for otherwise π ′ would be decreasing contrary to our assumption. Thus, there are e a-1,ℓ -a-1 ℓ + 1 possibilities for α in this case, which yields

n-1 a=3 a-2 ℓ=1 n -1 -a + ℓ ℓ e a-1,ℓ - a -1 ℓ + 1 additional permutations. Note that n-1 a=3 a-2 ℓ=1 n -1 -a + ℓ ℓ a -1 ℓ -1 = n-3 ℓ=1 n-1 a=ℓ+1 n -1 -a + ℓ ℓ a -1 ℓ -1 = n-3 ℓ=1 n -1 + ℓ 2ℓ + 1 - n -1 ℓ + 1 = n-2 ℓ=0 n -1 + ℓ 2ℓ + 1 -(2 n-1 -1).
The two previous cases taken together then imply that there are

2 n-1 -1 - n-2 ℓ=0 n -1 + ℓ 2ℓ + 1 + n-1 a=3 a-2 ℓ=1 ℓ j=0 n -1 -a + j j e a-1,ℓ
permutations π of the stated form above where π ′ is not decreasing. Combining this expression with the one for g n in Lemma 18 above gives (18).

3.4.2. Three l-r maxima. Let d n denote the number of T -avoiding permutations of length n having three left-right maxima. The sequence d n may be expressed explicitly as follows.

Lemma 21. We have

(19) d n = n-2 a=1 n-1 b=a+1 d n (a, b), n ≥ 3,
where -1 ways in which to select these elements as β is to contain an ascent. Since the positions of the elements of [a -1] within π are determined by the prior observations once i and j are specified in this case, we get

d n (a, b) = 2 a-1 + a 2 2 b-1-a -b + a + (a -1)2 a-2 - a 2 2 b-1-a -1 + a-1 j=0 a -1 j -1 n -b + j j + a-1 j=0 b-2-a r=0 a -1 j -1 n -3 -r -j n -1 -b + a-1 j=0 j i=0 b-1-a r=0 i + r i n -2 + j -i -a -r n -1 -b , 1 ≤ a < b ≤ n -1.
a-1 j=0 j i=0 b-1-a r=0 b -1 -a r -1 = (2 b-1-a -b + a) a-1 j=0 j i=0 1 = a + 1 2 (2 b-1-a -b + a)
possible permutations. One may verify (and also in the subsequent cases) that the permutations so obtained are T -avoiding. On the other hand, if β is decreasing, then we get i+r i possibilities for π ′′ since letters from [a -1] and [a + 1, b -1] within π ′′ are decreasing, and

(n -1 -b) + (j -i) + (b -1 -a -r) n -1 -b = n -2 + j -i -a -r n -1 -b
possibilities for π ′′′ since letters from [b -1] and [b + 1, n -1] within π ′′′ are decreasing, where i, j and r are as before. Considering all i, j and r gives the triple sum found in the expression for d n (a, b) above. Now assume that α contains an ascent. Note that since the letters of [a -1] within π occurring to the left and to the right of b form decreasing subsequences, there is exactly one ascent in α and it involves the last letter of π ′ and either the leftmost letter of [a -1] within π ′′ if π ′′ is nonempty or the leftmost letter of [a -1] within π ′′′ if π ′′ is empty. Any elements of [a -1] within π ′′ must occur at the end of π ′′ in this case so as to avoid 1234. Also, if π ′′ contains at least one member of [a -1] and π ′′′ at least one member of So assume

π ′′′ ∩ [a + 1, b -1] = ∅. If π ′′ ∩ [a -1] = ∅, then members of [a -1
] in π ′′ must occur at the end and the same holds for members of [b -1] in π ′′′ . Thus, we get

a-1 j=0 a -1 j -1 j i=1 b-2-a r=0 b -1 -a r = 2 b-1-a -1 a-1 j=0 a -1 j -1 j = 2 b-1-a -1 (a -1)2 a-2 - a 2 members of D n (a, b) in this case. If π ′′ ∩ [a -1] = ∅,
then consider whether or not β contains an ascent. If it does, then all members of [b -1] in π ′′′ must occur at the end (due to 1234), which gives

a-1 j=0 a -1 j -1 b-1-a r=0 b -1 -a r -1 = 2 a-1 -a 2 b-1-a -b + a
possibilities. If it does not, then there are Upon including permutations that start with n, we have

(n -1 -b) + (b -1 -a -r) + (a -1 -j) n -1 -b = n -3 -r -j n -
a n = b n + d n + e n-1 for n ≥ 2, with a 0 = a 1 = 1.
To obtain an explicit formula for the generating function for the number of T -avoiders of length n, we define

A(x) = n≥0 a n x n , B(x) = n≥2 b n x n , D(x) = n≥2 d n x n and E(x) = n≥0 e n x n .
It is well known that the generating function for the number of {123, 3412}-avoiders of length n is given by

E(x) = 1 + x(1 -4x + 7x 2 -5x 3 + 2x 4 ) (1 -x) 4 (1 -2x) .
Let E(x, y) = 1 + n≥1 n ℓ=1 e n,ℓ x n y ℓ . Using Lemma 19, one can show

E(x, y) = 1 + n≥1 n ℓ=1 e n,ℓ x n y ℓ = 1 + xy((2x 5 -5x 4 + 4x 3 -x 2 )y 2 + (2x 5 -6x 4 + 11x 3 -8x 2 + 2x)y -x 4 + 4x 3 -6x 2 + 4x -1) (1 -x) 2 (1 -2x)(1 -xy) 2 (xy + x -1) .
Note that E(x, 1) = E(x). Multiplying both sides of ( 18) by x n , and summing over all n ≥ 3, yields

B(x) = x 2 + n≥3 ((7 -n)2 n-3 -2)x n + n≥3 n-2 a=1 2 a-1 e n-1-a x n + n≥3 n-3 a=2 n-2-a ℓ=1 a-1 i=0 2 n-2-a-ℓ a -1 i ℓ + i i x n + n≥3 n-1 a=2 2 n-1-a -1 - n -a 2 (a -1)2 a-2 x n + n≥3 n-1 a=3 a-2 ℓ=1 ℓ j=0 n -1 -a + j j e a-1,ℓ x n = x 2 + 2x 3 (1 -3x + x 2 ) (1 -x)(1 -2x) 2 + x 3 (1 -4x + 7x 2 -5x 3 + 2x 4 ) (1 -x) 4 (1 -2x) 2 + x 5 (3 -6x + 2x 2 ) (1 -x)(1 -2x) 2 (1 -3x + x 2 ) + x 6 (1 -x) 3 (1 -2x) + x 4 (2 -13x + 34x 2 -46x 3 + 31x 4 -7x 5 ) (1 -x) 4 (1 -2x) 3 (1 -3x + x 2 ) = x 2 (1 -10x + 44x 2 -108x 3 + 159x 4 -144x 5 + 74x 6 -14x 7 ) (1 -x) 4 (1 -2x) 3 (1 -3x + x 2 ) .
Multiplying both sides of ( 19) by x n , and summing over all n ≥ 3, yields

D(x) = n≥3 n-2 a=1 n-1 b=a+1 2 a-1 + a 2 2 b-1-a -b + a x n + n≥3 n-2 a=1 n-1 b=a+1 (a -1)2 a-2 - a 2 2 b-1-a -1 x n + n≥3 n-2 a=1 n-1 b=a+1 a-1 j=0 a -1 j -1 n -b + j j x n + n≥3 n-2 a=1 n-1 b=a+1 a-1 j=0 b-2-a r=0 a -1 j -1 n -3 -r -j n -1 -b x n + n≥3 n-2 a=1 n-1 b=a+1 a-1 j=0 j i=0 b-1-a r=0 i + r i n -2 + j -i -a -r n -1 -b x n = x 5 (1 -2x + x 2 -x 3 ) (1 -x) 6 (1 -2x) 2 + x 6 (1 -x -x 2 ) (1 -x) 5 (1 -2x) 3 + x 5 (2 -x) (1 -x) 3 (1 -2x)(1 -3x + x 2 ) + x 6 (1 -x) 2 (1 -2x) 2 (1 -3x + x 2 ) + x 3 (1 -2x) 3 = x 3 (1 -9x + 37x 2 -91x 3 + 142x 4 -141x 5 + 90x 6 -36x 7 + 6x 8 ) (1 -x) 6 (1 -2x) 3 (1 -3x + x 2 ) .
By the fact a n = b n + d n + e n-1 for n ≥ 2, with a 0 = a 1 = 1, we have

A(x) = 1 + B(x) + D(x) + xE(x),
which leads to the following result.

Theorem 22. Let T = {1234, 3412, 4123}. Then

F T (x) = 1 -14x + 87x 2 -315x 3 + 736x 4 -1161x 5 + 1253x 6 -918x 7 + 446x 8 -134x 9 + 18x 10 (1 -x) 6 (1 -2x) 3 (1 -3x + x 2 ) .
3.5. Case 185: {1234, 2341, 4123}. We follow a similar pattern of proof as in Case 149 above and use the same notation, letting u n , b n , d n , e n and g n denote the same subsets as in that case, but with 1234 in place of 1243. From the proof of Lemma 10 above, we see that the sequence u n is the same as before since avoiding 1234 is logically equivalent to avoiding 1243 in this case. We now proceed with the various cases.

20) b n = b n-1 + u n + (n -3)2 n-4 + n -2 5 - n -2 2 + n-4 j=0 n-3-j i=1 n -i -2 j + 1 C n-2-j,i , (
with b 2 = 0, where u n given by (3) above.

Proof. The recurrence is clear for n = 3, so assume n ≥ 4. Let π ∈ S n (T ) be of the form enumerated by b n have leftmost ascent bottom a ≥ 2. If the first letter of π is n -1, then there are u n possibilities, by definition, so assume henceforth that the first letter is ≤ n -2. Let x denote the letter that directly follows n within π. If x = n -1, then there are b n-1 possibilities. If x ∈ [a -1], then reasoning in this case as in the proof of Lemma 13 above again gives

n-4 j=0 n-3-j i=1 n-i-2 j+1 C n-2-j,i possibilities. Now assume a + 1 ≤ x ≤ n -2.
Note first that all letters between n and n -1 must decrease in order to avoid 4123. Also, no letter in [a -1] can occur to the right of n -1, for otherwise there is a 2341 of the form ax(n -1)a ′ for some a ′ ∈ [a -1], whence letters in [a -1] form a decreasing subsequence. Thus a ≥ 2 implies all letters to the right of n -1 must decrease in order to avoid 4123. Hence, we have

π = αanβ(a -1) • • • 1(n -1)γ,
where α, β and γ are decreasing with α and γ possibly empty. We now consider cases on α. If α = ∅, then it is seen that there are no further restrictions on β and γ and we get n-2 a=2 (2 n-2-a -1) = 2 n-3n + 2 possible permutations in this case.

So assume α = ∅ and we consider first the case when some letter of γ is less than d = max(α). Let c denote the largest such letter of γ. First observe that all letters in [a + 1, c -1] must belong to α or γ, for if not, then there exists a 4123 of the form dauc for some u ∈ [a + 1, c -1] in β. Also, all letters in [d + 1, n -2] must belong to γ, for otherwise there is a 2341 of the form dd ′ (n -1)c for some

d ′ ∈ [d + 1, n -2] in β.
[a + 1, t -1] ∪ [s + 1, d], [c + 1, s] and [t, c] ∪ [d + 1, n -2]
, respectively. One may verify that the corresponding π indeed avoids T . Given a, c and d, note that such π are uniquely determined by s and t and that there are dc -1 choices for s and ca choices for t. Summing over all a, c and d then gives

n-5 a=2 n-4 c=a+1 n-2 d=c+2 (c -a)(d -c -1) = n-5 a=2 n-4 c=a+1 (c -a) n -2 -c 2 = n-4 c=3 n -2 -c 2 c-1 a=2 (c -a) = n-4 c=3 n -2 -c 2 c -1 2 = n -2 5
possible permutations.

Finally, assume α = ∅ and that all letters in γ are greater than d. Then all elements of [a + 1, d -1] must belong to α or β and all elements of [d + 1, n -2] belong to β or γ. Since β = ∅, it follows that there are 2 n-3-a -1 ways in which to arrange the members of [a + 1, n -2] once a and d are specified. Furthermore, each is seen to give rise to a permutation that avoids T . Considering all possible a and d then yields

n-3 a=2 n-2 d=a+1 (2 n-3-a -1) = n-3 a=2 (2 n-3-a -1)(n -2 -a) = n-4 a=1 a2 a-1 - n -3 2 = (n -5)2 n-4 + 1 - n -3 2
additional permutations. Combining this case with the prior gives (20).

3.5.2. Case II. We have the following formula for d n in terms of b n .

Lemma 24. If n ≥ 5, then

(21) d n = d n-1 + b n-1 -b n-2 + n -3 2 - n -3 5 + n-3 a=3 n-3-a ℓ=0 n-2-a-ℓ m=1 n -5 -ℓ -m a -3 m, with d 4 = 1
, where b n is given by (20) above.

Proof. We proceed as in the proof of Lemma 14 above and let B m , B ′ m and D m have the same meaning as before but with the pattern 1234 in place of 1243. We form members of D n by inserting n somewhere to the right of n -1 within a member of B n-1 , where n ≥ 5. First note that there are d n-1 possibilities if the letter n -2 is to directly follow n -1 within a member of B n-1 . So consider inserting n into members π ∈ B ′ n-1 without introducing an occurrence of a pattern in T .

We show in every case except one that this is possible. Note that if n -2 is the first letter of π, then n can only be added as the final letter due to 2341, so assume henceforth that π does not start with n -2. Write π = π ′ a(n -1)π ′′ , where a ≥ 2 is the leftmost ascent bottom and let y be the first letter of π ′′ . If 1 ≤ y ≤ a -1, then it is seen that n can always be added to the end of π.

Now assume a + 1 ≤ y ≤ n -3. In this case, then it is only possible to insert n in the position between 1 and n -2. For if n is inserted somewhere between n -1 and 1, then there is a 2341 as seen with a(n -1)n1, while if n is inserted to the right of n -1 (including at the very end), then ay(n -2)n is a 1234. If π ′ is empty or if π ′ is nonempty and there are no letters in [a + 1, d -1] to the right of n -2 where d = max(π ′ ), then it is seen from the proof of Lemma 23 that inserting n between 1 and n -2 within π does not introduce an occurrence of a pattern in T . On the other hand, if π ′ is nonempty and some member of At times V will also refer to the corresponding subsequence of π comprising the elements of this set. Let v n denote the number of π ∈ E n in which members of V form a decreasing subsequence with at least one member of V to the right of n. For example, if n = 6, then v n = 3, the enumerated permutations being 241635, 241653 and 524163. Note that v n = 0 if n ≤ 5 since a < b -1 is required. We have the following explicit formula for v n .

Lemma 25. If n ≥ 6, then

(22) v n = 2 n-2 - n -1 3 -n + 1 + n-4 a=2 n-3-a ℓ=1 n a + ℓ + 2 - n -1 -ℓ a + 1 . Proof. Let V n denote the subset of E n enumerated by v n . Let π ∈ V n have leftmost
v n = n-4 a=2 n-2 b=a+2 n-1-b ℓ=0 b-1-a m=1 a + ℓ + m m - a -1 + m m , n ≥ 6.
Interchanging summation, and treating separately the ℓ = 0 case, gives

v n = n-4 a=2 n-2 b=a+2 n-1-b ℓ=0 b + ℓ a + ℓ + 1 - b -1 a = n-4 a=2 n-2 b=a+2 b a + 1 - b -1 a + n-4 a=2 n-3-a ℓ=1 n-1-ℓ b=a+2 b + ℓ a + ℓ + 1 - b -1 a = n-4 a=2 n-2 b=a+2 b -1 a + 1 + n-4 a=2 n-3-a ℓ=1 n a + ℓ + 2 - n -1 -ℓ a + 1 = n-4 a=2 n -2 a + 2 + n-4 a=2 n-3-a ℓ=1 n a + ℓ + 2 - n -1 -ℓ a + 1 , which implies (22).
We now count the remaining members of E n for which some letter in V lies to the right of n.

Note that if V is not decreasing, then there must be at least one letter in V to the right of n, for otherwise there is a 1234 of the form ab

1 b 2 n for some b 1 , b 2 ∈ [a + 1, b -1]
. Let w n denote the number of members of E n in which the subsequence V is not decreasing. For example, if n = 7, then w 7 = 1, the enumerated permutation being 2531764. Note that w n = 0 if n < 7 since |V | ≥ 2 implies a < b -2. We have the following formula for w n .

Lemma 26. If n ≥ 7, then

w n = 2 n-2 -1 - n -1 2 - n -1 4 + 4 n -6 2 + n -5 3 + n-6 a=2 n-2 b=a+4 (b -5 -a)2 b-2-a . (23)
Proof. Let W n denote the subset of E n enumerated by w n . Suppose π ∈ W n has leftmost ascent a, b, where 2 ≤ a ≤ n -5 and a + 3 ≤ b ≤ n -2. First observe that since V is not decreasing, all of the letters in [b + 1, n -1] must occur to the right of n (and decrease), for otherwise there would be a 4123 of the form cau 1 u 2 , where c Then all letters in V to the right of z must decrease, for otherwise there is a 4123 of the form bzv 1 v 2 for some v 1 , v 2 ∈ V . In particular, all letters in V to the right of b + 1 must decrease, which implies y directly follows b + 1. Also, x cannot occur anywhere to the right of z since x < y, which means that x must occur between b and z. Finally, the subsequence of π comprising [a -1] must itself decrease (and hence z = a -1), for otherwise there is a 4123 of the form ba 1 a 2 y for some

∈ [b + 1, n -1] and u 1 , u 2 ∈ V with u 1 < u 2 . Denote the V subsequence of π = π 1 π 2 • • • π n by π i1 π i2 • • • π im ,
a 1 , a 2 ∈ [a -1]
. Thus, we have shown that π must have the form

π = αabβ(a -1) • • • 1n(n -1) • • • (b + 1)γ,
where α, β and γ denote subsequences whose union is [a + 1, b -1] and α is possibly empty.

Note that α, β and γ must all decrease, α since it precedes a, β since π avoids 1234, and γ since π avoids 4123. Furthermore, we have min(β) = x < y = max(γ) and thus V consists of two decreasing runs. To enumerate members of W n , we now consider cases on V . ). Since the letters to the left of b within π comprise an interval in this case, one may verify that there are no further restrictions on β and γ and that each corresponding permutation π obtained in this manner is T -avoiding. Considering all possible a, b, m and j implies that the number of permutations in W n for which V is of the stated form is given by

n-5 a=2 n-2 b=a+3 b-1-a m=2 m-1 j=1 m j -1 = n-5 a=2 n-2 b=a+3 b-1-a m=0 (2 m -m -1) = n-5 a=2 n-2 b=a 2 b-a -1 - b -a + 1 2 = n-1 n=2 2 n-1-a -(n -a) - n -a 3 = 2 n-2 -1 - n -1 2 - n -1 4 . Now assume V does not comprise an interval of the form [b -m, b -1].
Let q be the largest letter in α. Then all v ∈ V with v < q must occur in β, for otherwise there is a 2341 of the form qb(b + 1)v.

In order for there to be an increase in the subsequence V , we must have q ≤ b -2. Then the elements of [q + 1, b -1] can go in either β or γ, with at least one element going in γ, for otherwise

V would be decreasing. Also, members of [a + 1, q -1] can go in either α or β with at least one going in β since α is not an interval of the form [a + 1, a + r] for some r ≥ 1. Note that at least one element of [a + 1, q -1] belonging to β ensures that V does not decrease. Given a, b and q, there are thus 2 q-1-a -1 possibilities for the placement of elements of [a + 1, q -1] and 2 b-1-q -1 possibilities for the placement of elements of [q + 1, b -1]. Since these positions may be chosen independently, there are (2 q-1-a -1)(2 b-1-q -1) possibilities in all and one can check that all permutations π so obtained are T -avoiding. Note that q ≥ a + 2 implies a + 4 ≤ b ≤ n -2 and 2 ≤ a ≤ n -6. Considering all possible a, b and q gives

n-6 a=2 n-2 b=a+4 b-2 q=a+2 (2 q-1-a -1)(2 b-1-q -1) = n-6 a=2 n-2 b=a+4 (b -3 -a)2 b-2-a -2(2 b-2-a -2) + (b -3 -a) = n-6 a=2 n-2 b=a+4 (b -5 -a)2 b-2-a + n-6 a=2 4(n -5 -a) + n -4 -a 2 = n-6 a=2 n-2 b=a+4 (b -5 -a)2 b-2-a + 4 n -6 2 + n -5 3
additional members of W n . Combining this case with the previous completes the proof.

We have the following formula for e n in terms of the prior sequences.

Lemma 27. If n ≥ 6, then (24)
e n = v n + w n + C n-2 -3 • 2 n-3 + 1 + n-2 ℓ=1 C ℓ ,
with e 5 = 2, where v n and w n are as defined above.

Proof. To show this, we need only enumerate the members of E n in which no element of [a+1, b-1] occurs to the right of n. Let π ∈ E n be of this form. Then π may be written as

π = (n -ℓ -1) • • • (b + 1)π ′ n(n -1) • • • (n -ℓ), 0 ≤ ℓ ≤ n -1 -b,
where π ′ is a permutation of length b whose leftmost ascent is a, b with a ≥ 2. Note that π ′ is 123-avoiding, but that there are no further restrictions on π ′ imposed by the letters in [b + 1, n], which implies that they may be deleted. Upon subtracting 123-avoiding permutations starting with b or having leftmost ascent 1, b, we get

C b -C b-1 -2 b-2 possibilities for π ′ . Considering all b and ℓ gives n-2 b=3 n-1-b ℓ=0 (C b -C b-1 -2 b-2 ) = C n-2 -2 n-3 + n-4 ℓ=1 n-1-ℓ b=3 (C b -C b-1 -2 b-2 ) = C n-2 -2 n-3 + n-2 ℓ=1 (C n-1-ℓ -2 n-2-ℓ ) = C n-2 -3 • 2 n-3 + 1 + n-2 ℓ=1
C ℓ additional members of E n , which completes the proof.

3.5.4. Case IV. In this section, we complete our enumeration of S n (T ) by finding g n , which is given as follows.

Lemma 28.

If n ≥ 3, then (25)
g n = g n-1 + C n-1 + (n + 1)2 n-3 - n 3 -n,
where g 2 = 1.

Proof. We proceed as in the proof of Lemma 16 above and use the same terminology and notation, but with respect to the new pattern set T . Let π = a 1 • • • a s 1π ′ be of the form enumerated by g n , where n ≥ 4 and 1 < a s < • • • < a 1 ≤ n -1 and let S = {a 1 , . . . , a s }. If S = ∅, then π = 1π ′ , where π ′ avoids 123, and thus there are C n-1 possibilities. So assume S = ∅. If a s = 2, then deleting 2 gives g n-1 possibilities, so assume a s ≥ 3 henceforth. We consider the relative positions of large and small letter within π, where large and small are defined as before.

First observe that large letters occurring to the left of any small letters must decrease in order to avoid 2341, as do large letters occurring to the right due to 1234. Small letters must decrease, for otherwise there would be a 4123 starting with a 1 , 1. First suppose that at least one large letter occurs between the first and the last of the small letters. If x denotes the rightmost such large letter, then all large letters to the left of x must decrease and are greater than x, while all large letters to the right of x must decrease and are less than x. Thus, the full subsequence comprising the large letters is decreasing. Furthermore, the set S in this case must comprise an interval of the form [ℓ, ℓ + s -1] for some 4 ≤ ℓ ≤ n -1 and 1 ≤ s ≤ nℓ, for otherwise there would be a 2341. Note that there is no restriction on the number of large letters lying between the first and the last small letters. Since there are ℓ -2 small letters and nℓs + 1 large letters, at least one of which occurs between small letters, there are n-s-1 ℓ-2

-(nℓs + 2) possible arrangements of these letters, by subtraction. It is seen that all permutations arising in this manner are T -avoiding. Considering all ℓ and s gives

n-1 ℓ=4 n-ℓ s=1 n -s -1 ℓ -2 -(n -ℓ -s + 2) = n-1 ℓ=4 n -1 ℓ -1 - n -ℓ + 2 2 = n ℓ=3 n -1 ℓ -1 - n -ℓ + 2 2 = 2 n-1 -n - n 3
permutations in this case. Now suppose that no large letter occurs between the first and the last of the small letters. Then π in this case consists of three runs of descending letters: (i) the initial decreasing run of length s + 1 (including 1), (ii) a decreasing run which includes all of the small letters, and (iii) a possibly empty decreasing run of large letters. From this, one need only select the elements comprising (i) and any large letters in (ii), which uniquely determines π. If m = a 1 , then there are m-3 s-1 choices for the additional letters in (i) and 2 n-m choices for the large letters in (ii). Note that since 2 is a small letter, we have m ≥ s + 2. Considering all possible s and m then yields

n-3 s=1 n-1 m=s+2 2 n-m m -3 s -1 = n-1 m=3 2 n-m m-2 s=1 m -3 s -1 = n-1 m=3 2 n-3 = (n -3)2 n-3
additional permutations. Combining this case with the others gives (25).

For any of the sequence above, put zero if n is such that the corresponding set of permutations is empty. For example, put e n = 0 if n ≤ 4. Combining cases I through IV above, and including permutations that start with the letter n, implies that the number of T -avoiding permutations of length n is given by ( 26)

a n = b n + d n + e n + g n + C n-1 , n ≥ 2,
with a 0 = a 1 = 1. Now we are ready to find a formula for the generating function

A(x) = n≥0 a n x n . Define B(x) = n≥3 b n x n , D(x) = n≥4 d n x n , E(x) = n≥5 e n
x n and G(x) = n≥2 g n x n . First we rewrite the recurrences from the preceding lemmas in terms of generating functions by multiplying both sides by x n and summing over all possible n. By Lemmas 23-28, we obtain

B(x) = 1 1 -x u(x) + x 4 (1 -2x) 2 + x 7 (1 -x) 6 - x 4 (1 -x) 3 + xq x 1 -x , 1 -x -xq(x, 1) , (27)
D(x) = xB(x) + x (3x 4 -5x 3 + 6x 2 -4x + 1) (1 -x) 7 (1 -2x) , (28)
E(x) = 2x 5 - x 6 (2x -3) (1 -x) 4 (1 -2x) 2 - x 7 (x 2 + x -1) (1 -x) 5 (1 -2x) 2 + x 2 (C(x) -5x 3 -2x 2 -x -1) (29) - 24x 6 1 -2x + x 6 1 -x + 8x 6 1 -x + x 2 1 -x (C(x) -5x 3 -2x 2 -x -1), G(x) = x 1 -x (C(x) -1) + x 4 (2x 4 -8x 3 + 10x 2 -7x + 2) (1 -x) 5 (1 -2x) 2 . ( 30
)
By solving (27)-(30), along with use of (5) and Lemma 12, we obtain

B(x) = x(1 -x)C 2 (x) + x(3x 9 -15x 8 + 59x 7 -134x 6 + 192x 5 -181x 4 + 112x 3 -44x 2 + 10x -1) (1 -x) 7 (1 -2x) 2 , D(x) = x 2 (1 -x)C 2 (x) - x 2 (3x 6 -12x 5 + 27x 4 -31x 3 + 20x 2 -7x + 1) (1 -x) 4 (1 -2x) 2 , E(x) = x 3 (2 -x) 1 -x C 2 (x) - x 3 (3x 6 -14x 5 + 38x 4 -49x 3 + 34x 2 -13x + 2) (1 -x) 5 (1 -2x) 2 , G(x) = x 2 1 -x C 2 (x) + x 4 (2x 4 -8x 3 + 10x 2 -7x + 2) (1 -x) 5 (1 -2x) 2 .
By (26), we have

A(x) = 1 + x + B(x) + D(x) + E(x) + G(x) + x(C(x) -1),
which, upon substituting the expressions just found for the generating functions B(x), D(x), E(x) and G(x), implies the following result.

Theorem 29. Let T = {1234, 2341, 4123}. Then

F T (x) = 1 -11x + 51x 2 -130x 3 + 199x 4 -183x 5 + 91x 6 -15x 7 -6x 8 + 4x 9 (1 -x) 7 (1 -2x) 2 + 1 + x 1 -x (C(x) -1) .
3.6. Case 209: {3142, 1432, 1243}. This is one of the shortest cases.

Theorem 30. Let T = {3142, 1432, 1243}. Then the generating function F = F T (x) satisfies

F = 1 -xF + x 2 + x 2 (1 -x) 2 F 2 -x 2 F 3 . Proof. To find G m (x) for m ≥ 2, let π = i 1 π (1) i 2 π (2) • • • i m π (m) ∈ S n (T ) with m ≥ 2 left-right maxima.
Since π avoids 1243, we see that π (2) • • • π (m) < i 2 . We consider two cases:

• There is no letter in π (2) • • • π (m) between i 1 and i 2 , that is, π (2) • • • π (m) < i 1 . Since π avoids 3142, we see that π (1) > π (2) > • • • > π (m)
. Therefore, we have a contribution of x m F m . • There is some p ∈ [2, m] minimal such that π (p) has a letter between i 1 and i 2 . Then

π (2) π (3) • • • π (p-1)
< i 1 by the minimality of p and also π (p+1) • • • π (m) < i 1 since π avoids 1243 and 1432. Furthermore, since π avoids 3142, π (2) , π (3) , . . . , π (p-1) are all empty. Hence, i 1 + 1, i 1 + 2, . . . , i 2 -1 all lie in π (p) and furthermore occur in that order (or i 1 i 2 is the 14 of a 1432). So, with d = i 2i 1 , we have d ≥ 2 and can write π (p) as

α 1 (i 1 + 1)α 2 (i 1 + 2) • • • α d-1 (i 2 -1)α d .
We also have π

(1) > α 1 > α 2 > • • • > α d > π (p+1) > • • • > π (m)
(a violator of any of these inequalities would be the 12 of a 3142), and π (1) is decreasing (u < v in π (1) would make uvi 2 (i 1 + 1) a 1243). Hence, the contribution in this case is

m p=2 x m 1-x F m-p d≥2 x d-1 F d .
Adding the two contributions, we have for m ≥ 2,

G m (x) = x m F m + x m+1 m p=2 F m+2-p (1 -x)(1 -xF ) .
Summing over m yields the stated expression for F .

3.7.

Case 216: {2143, 3142, 3412}. Let H m = H m (x) be the generating function for permutations Adding the contributions in the two cases for n -1 gives

π = π 1 π 2 • • • π n ∈ S n (T ) such that π 1 < π 2 < • • • < π m = n. Clearly, H 1 = xF T (x). Lemma 31. For m ≥ 2, (1 -2x)H m = x(1 -x)H m-1 + x j≥m (1 -x)H j -xH j-1 . Proof. Consider a T -avoider π = π 1 π 2 • • • π n ∈ S n (T ) counted by H m , where m ≥ 2. If π 1 = 1, the contribution is xH m-1 . Otherwise, π has the form π = π 1 π 2 • • • π m α1β, where β > π m-1 (or π m-1 π m 1 is
J m = x(H m -xH m-1 ) + x t≥0 J m+t . Since J m = (1 -x)H m -xH m-1 , this implies (1 -x)H m -xH m-1 = x(H m -xH m-1 ) + x j≥m (1 -x)H j -xH j-1 ,
and the result follows.

Lemma 32. We have m≥1 H m (x) = xC(x)F T (x) .

Proof. Define H(x, v) = m≥1 H m (x)v m-1 . By Lemma 31, we have

(1 -2x)H(x, v) -x(1 -2x)F T (x) = xv(1 -x)H(x, v) + xv(1 -x) 1 -v H(x, 1) -H(x, v) - x 2 v 1 -v H(x, 1) -vH(x, v) , which implies 1 -2x -xv(1 -x) + xv(1 -x -xv) 1 -v H(x, v) = x(1 -2x)F T (x) + xv(1 -2x) 1 -v H(x, 1)
.

By taking v = C(x), we find that H(x, 1) = xC(x)F T (x).

Theorem 33. Let T = {2143, 3142, 3412}. Then

F T (x) = (1 -3x)C(x) 1 -2x -x(1 -x)C(x) .
Proof. To write an equation for G m (x) where m ≥ 2, suppose π = i 1 π (1) • • • i m π (m) ∈ S n (T ) has m ≥ 2 left-right maxima. If π (m) = ∅, the contribution is xG m-1 (x). Otherwise, there exists j maximal, 1 ≤ j ≤ m, such that π (m) has a letter between i j-1 and i j (where i 0 = 0). Since π avoids 2143, π (1) • • • π (j-1) = ∅ and π (j) • • • π (m-1) > i j-1 . Since π avoids 3142 and j is maximal, we have π (j) • • • π (m-1) > π (m) . There are two cases:

• j = m. If π (m) < i m-1 , then π (m)
is decreasing because we avoid 3412. So the contribution is H m -

x m

(1-x) m-1 , where

x m

(1-x) m-1 counts all the permutations π with i m-1 = n -1. • 1 ≤ j ≤ m -1. Again, π (m) is decreasing, and we have a contribution of x j+1

(1-x) j G m-j (x).

Adding all the contributions gives

G m (x) = xG m-1 (x) + H m - x m (1 -x) m-1 + m-1 j=1 x j+1 (1 -x) j G m-j (x) .
Sum over m ≥ 2 using Lemma 32 to obtain

F T (x) -xF T (x) -1 = x F T (x) -1 + xC(x)F T (x) -xF T (x) - x 2 1 -2x + x 2 1 -2x F T (x) -1 .
Solving for F T (x) completes the proof.

3.8. Case 225: {1243, 2413, 3142}.

Theorem 34. Let T = {1243, 2413, 3142}. Then

F T (x) = 1 -x(1 -x)C(x) -1 -5x + 10x 2 -5x 3 -x(1 -x)(1 + x)C(x) 2x(1 -x) .
Proof. To find G m (x) for m ≥ 2, let π = i 1 π (1) i 2 π (2) • • • i m π (m) ∈ S n (T ) with m ≥ 2 left-right maxima. Then π (j) < i 2 for j = 1, 2, . . . , m (a violator v makes i 1 i 2 i j v a 1243) and π has the form shown in Figure 2 below, where, for each j ∈ [2, m], one has α j > i 1 > β j as shown (or i 1 i j is the 24 of a 2413), with α j avoiding 132 (or i 1 is the 1 of a 1243). Also, for each j ∈ [2, m -1 ], α j > α j+1 (or i j i j+1 is the 34 of a 3142) and the same holds for the β j .

β 1 β 2 β 3 β 4 β m α 2 α 3 α 4 α m i 1 i 2 i 3 i 4 i m . . . . . . . . .
There are two cases:

• α 1 • • • α m = ∅.
In this case, π avoids T if and only if β i avoids T for all i = 1, 2, . . . , m, giving a contribution of

x m F T (x) m . • α 1 • • • α m = ∅.
Let j be the maximal index such that α j = ∅ and say a is a letter in α j .

Then

β 2 = • • • = β j-1 = ∅ (or b in β i with 2 ≤ i ≤ j -1 makes i 1 i 2 ba a 2413
) and β 1 is decreasing (or i 2 a is the 43 of a 1243). So π avoids T if and only if β i avoids T for i = j, j + 1, . . . , m and α i avoids 132 for i = 2, 3, . . . , j, giving a contribution of

m j=2 x m 1 -x C(x) j-2 C(x) -1 F T (x) m-j+1 .
Hence,

G m (x) = x m F T (x) m + m j=2 x m 1 -x C(x) j-2 C(x) -1 F T (x) m-j+1 .
Summing over m ≥ 2, we obtain

F T (x) = 1 + xF T (x) + (1 -x) 1 -xC(x) F T (x) + C(x) -1 x 2 F T (x) (1 -x) 1 -xC(x) 1 -xF T (x) ,
and solving for F T (x) completes the proof.

3.9. Case 228: {2341, 2413, 3412}. In this case, we find a cubic equation for F T .

Theorem 35. Let T = {2341, 2413, 3412}. Then the generating function F = F T (x) satisfies

F = (1 -x) 2 + xF + x(2 -3x + 2x 2 )F 2 -x 2 (1 -x)F 3 .
Proof. First, we write an equation for G m (x) with m ≥ 3. Suppose π = i 1 π (1)

i 2 π (2) • • • i m π (m) ∈
S n (T ) with m ≥ 3 left-right maxima. Since π avoids 2341, we see that π (j) > i j-2 for all j = 2, 3, . . . , m (with i 0 = 0). If π (2) > i 1 , then π avoids T if and only if π (1) avoids T and i 2 π (2) • • • i m π (m) avoids T , which gives a contribution of xF G m-1 (x). Otherwise, π (2) has a letter smaller than i 1 , which implies π (3) > i 2 (π avoids 2413), and π avoids T if and only if i 1 π (1) i 2 π (2) and i 3 π

(3) • • • i m π (m) both avoid T , which gives a contribution of G 2 (x) -x 2 F 2 G m-2 (x). Hence, for m ≥ 3, (31) G m (x) = xF G m-1 (x) + G 2 (x) -x 2 F 2 G m-2 (x) .
Next, to find G 2 (x), suppose π = iπ ′ nπ ′′ ∈ S n (T ) has 2 left-right maxima. Let k be the number of letters smaller than i in π ′′ . If k = 0, the contribution is x 2 F 2 . Otherwise, k ≥ 1 and these k letters, say i 1 , i 2 , . . . , i k , are decreasing (to avoid 3412) and occur at the end of π ′′ (or in is the 24 of a 2413). Also, the letters n -1, n -2, . . . , i + 1 in π ′′ occur in that order (to avoid 2341). So π has the form iπ ′ n(n -1)

• • • (i + 1)i 1 i 2 • • • i k .
Set i 0 = i. Then the letters in [i k , i 0 ]\{i 1 , i 2 , . . . , i k } are decreasing (or ni k is the 41 of a 2341) and they split iπ ′ = i 0 π ′ into segments as follows:

i 0 π ′ = i 0 α 0,0 (i 0 -1)α 0,1 (i 0 -2)α 0,2 • • • (i 1 + 1)α 0,i0-i1-1 (i 1 -1)α 1,1 (i 1 -2)α 1,2 • • • (i 2 + 1)α 1,i1-i2-1
. . .

(i k-1 -1)α k-1,1 (i k-1 -2)α k-1,2 • • • (i k + 1)α k-1,i k-1 -i k -1 , where α 0,0 < α 0,1 < • • • < α 1,1 < α 1,2 < • • • , i.e.
, each α is less than its successor (to avoid 2413). Now π avoids T if and only if each α i,j avoids T . Hence, for each k ≥ 1, we have a contribution of

x k+1 1 -x × xF (1 -xF ) k .
Adding the contributions gives

G 2 (x) = x 2 F 2 + k≥1 x k+2 F (1 -x)(1 -xF ) k = x 2 F 2 + x 3 F (1 -x)(1 -x -xF )
.

Summing (31) over m ≥ 3, we obtain

F = 1 + xF + G 2 (x) + xF (F -1 -xF ) + (F -1) G 2 (x) -x 2 F 2 .
Now substitute for G 2 (x) and solve for F to complete the proof. Lemma 36. We have

D m = A m + xD m-1 if m ≥ 2, A 1 + x(F T -1) if m = 1.
Proof. Split T -avoiders counted by D m into those with π 1 ≤ n -2, counted by A m , and those for which π 1 = n -1. Deleting n -1 from the latter avoiders gives the result.

Corollary 37. For m ≥ 1, (32)

A m = A m+1 + B m + xA m + x 2 A m-1 + • • • + x m A 1 + x m+1 A 0 ,
where

A 0 := F T -1.
Proof. For π counted by A m , consider π m+1 . Note that π m+1 cannot lie in the interval [π m +1, n-2] for then π m π m+1 would be the 12 of either a 1234 or a 1243 involving {n -1, n}. So, if π m+1 < π m , the contribution is A m+1 , if π m+1 = n-1, the contribution is B m , and if π m+1 = n, then by deleting n, the contribution is xD m . The result follows by applying Lemma 36 repeatedly to D m .

Since a(n; n) = a(n; n -1) = a(n -1) for n ≥ 2, we have a

(n) = n i=1 a(n; i) = a(n; n) + a(n; n - 1) + n-2 i=1 a(n; i) = 2a(n -1) + [x n ]A 1 , which implies F T -1 -x = 2x(F T -1) + A 1 . (33)
To obtain a recurrence for B m , define B n,m;j = {π

1 π 2 • • • π n ∈ S n (T ) : n -2 ≥ π 1 > π 2 > • • • > π m , π m+1 = n -1, π m+2 = n -j}. Lemma 38. For all 3 ≤ j ≤ m + 1, n≥0 |B n,m;j |x n = x m+3 C m+3-j (x). Proof. Let π = π 1 π 2 • • • π n ∈ S n (T ) such that n -2 ≥ π 1 > π 2 > • • • > π m , π m+1 = n -1 and π m+2 = n-j.
Since π m < π m+2 and n lies to the right of π m+2 , the letters n-2, n-3, . . . , n-j +1 all lie to the left of π m+2 (otherwise π contains 1234 or 1243). Thus, π = (n -2)(n -3)

• • • (n -j + 1)π j-1 • • • π n-1 π n ∈ S n (T ) with π j-1 > π j > • • • > π m , π m+1 = n -1,
and π m+2 = nj. Since π avoids 2341 and π 1 = n -2 < π m+1 = n -1, we have that π n = n. Therefore, π avoids T if and only if

π ′ = π j-1 • • • π m π m+3 • • • π n-1 avoids 123 and π j-1 > • • • > π m .
Hence, B n,m;j equals the number of permutations in S n-1-j (123) with initial descent sequence (IDS) of length at least m + 2j. Using Lemma 11, one can show that the generating for permutations in S n (123) having IDS of length at least m ′ is given by x m ′ C m ′ +1 (x). Thus, for j = 3, 4, . . . , m + 1, n≥0 |B n,m;j |x n = x m+3 C m+3-j (x), as required.

Lemma 39. For all m ≥ 1,

B m (x) = B m+1 (x) + x m+3 m i=2 C i (x) + xB m (x) + x m+2 1 -x 1 -2x .
Proof. By Lemma 38,

B m (x) = n≥0   n-1>i1>i2>•••>im+1≥1 a(n; i 1 i 2 • • • i m (n -1)i m+1 )   x n + n≥0   n-1>i1>i2>•••>im≥1 m+1 j=3 a(n; i 1 i 2 • • • i m (n -1)(n -j))   x n = B m+1 (x) + m+1 j=3 n≥0 |B n,m;j |x n + n≥0   n-1>i1>i2>•••>im≥1 a(n; i 1 i 2 • • • i m (n -1)(n -2))   x n + n≥0   n-1>i1>i2>•••>im≥1 a(n; i 1 i 2 • • • i m (n -1)n)   x n = B m+1 (x) + x m+3 m i=2 C i (x) + xB m (x) + x m+2 1 -x 1 -2x ,
which completes the proof.

Define B(x, u) = m≥1 B m (x)u m and A(x, u) = m≥1 A m (x)u m . Rewriting the recurrence relations from Lemmas 38 and 39 in terms of A(x, y) and B(x, u) using (33), we obtain

(1 -x)B(x, u) = 1 u (B(x, u) -B 1 (x)u) + x 5 u 2 C 2 (x) (1 -xu)(1 -xuC(x)) + x 3 (1 -x)u (1 -2x)(1 -xu) , A(x, u) = 1 u(1 -xu) A(x, u) + x 2 u 1 -xu (F T (x) -1) -((1 -2x)F T (x) -1 + x) + B(x, u).
Taking u = 1/(1x), we obtain

B 1 (x) = x 5 C 4 (x) 1 -2x + x 3 (1 -x) (1 -2x) 2 , which leads to (1 -x -1/u)B(x, u) = x 5 u 2 C 2 (x) (1 -xu)(1 -xuC(x)) - x 5 C 4 (x) 1 -2x + x 3 (1 -x)u (1 -2x)(1 -xu) - x 3 (1 -x) (1 -2x) 2 .
Thus, letting u = C(x), we have

B(x, C(x)) = x 3 (4x 2 -3x + 1 -2x 2 C(x)) (2x 2 C(x) -xC(x) -3x + 1)(1 -2x) 2 .
Hence, substituting u = C(x) into the equation for A(x, u), we obtain

x 2 C 2 (x)(F T (x) -1) -((1 -2x)F T (x) -1 + x) + B(x, C(x)) = 0,
which implies the following result.

Theorem 40. Let T = {2341, 1243, 1234}. Then

F T (x) = x(4x 4 + 3x 3 -11x 2 + 6x -1)C(x) + 2x 4 -12x 3 + 16x 2 -7x + 1 (1 -2x) 2 1 -4x + 2x 2 -x(1 -3x)C(x) .
For the final three cases, denoting the set of triples involved by T , we recall the generating trees method. The notion of generating tree to enumerate pattern avoiders was introduced by West [START_REF] West | Generating trees and the Catalan and Schröder numbers[END_REF].

To enumerate S n (T ) for each T ∈ T , we consider the generating forest whose vertices are identified with S := n≥2 S n (T ) where 12 and 21 are the roots and each non-root π ∈ S is a child of the permutation obtained from π by deleting its largest element. We will show that it is possible to label the vertices so that if v 1 and v 2 are any two vertices with the same label and ℓ is any label, then v 1 and v 2 have the same number of children with label ℓ. Indeed, we will specify (i) the labels of the roots, and (ii) a set of succession rules explaining how to derive from the label of a parent the labels of all of its children. This will determine a labelled generating forest depending on T .

Corollary 43. The labelled generating forest F is given by Roots: 3, 3

Rules: k 3, 4, . . . , k + 1, k + 1 for k ≥ 3, k 3, 4, . . . , k, k, k + 1 for k ≥ 3, k 2, 3, 4, . . . , k, k + 1 for k ≥ 2.
Proof. We treat the double-bar case (the others are similar). So suppose π ∈ S n (T ) has label k, k ≥ 2. This means that site n is not active, L(π) has k -1 entries, all ≤ n-1, and

A(π)\L(π) = {n+1}. Say L(π) = {L 1 = 1 < L 2 < • • • < L k-1 ≤ n -1}. Then for 1 ≤ i ≤ k -1, π
Li does not end with its largest letter and its active sites are {L 1 , . . . , L i , n + 2}. In particular, its penultimate site, namely n + 1, is not active. Hence, its label is i + 1. Also, π n+1 does end with its largest letter and its active sites are {L 1 , . . . , L k-1 , n + 1, n + 2} and so its label is k + 1. All told, the labels of the children of π are 2, 3, 4, . . . , k, k + 1.

Theorem 44. Let T = {3412, 3421, 2341}. Then

F T (x) = 1 + 1 + rt 1 + 1/r + 1/t -1/x , where r = r(x) = √ 5 -1 1 -1 -3 + √ 5 x + 1 2 3 - √ 5 x 2 -1 + √ 5 x 4x
and t is the same as r but with √ 5 replaced by -√ 5.

Proof. Let a k (x), b k (x) and c k (x) be the generating functions for the number of permutations in the nth level of the labelled generating forest F with label k, k and k, respectively. By Corollary 43, we have

a k (x) = x 2 δ k=3 + xa k-1 (v) + xb k-1 (v) + xc k-1 (v), b k (x) = x 2 δ k=3 + v 2 b 2 (x) + x(b k (x) + b k+1 (x) + • • • ) + x(a k-1 (x) + a k (x) + • • • ), c k (x) = xb k (x) + x(c k (x) + c k+1 (x) + • • • ), b 2 (x) = xb 2 (x) + x(c 3 (x) + c 4 (x) + • • • ), for all k ≥ 3. Now let A(x, v) = k≥3 a k (x)v k , B(x, v) = k≥2 b k (x)v k and C(x, v) = k≥3 c k (x)v k .
Hence, the above recurrences can be written as

A(x, v) = x 2 v 3 + xvA(x, v) + xvB(x, v) + xvC(x, v), (34) B(x, v) = x 2 v 3 + v 2 b 2 (x) + x 1 -v (v 3 B(x, 1) -vB(x, v)) + x 1 -v (v 3 A(x, 1) -v 2 A(x, v)), (35) C(x, v) = x(B(x, v) -v 2 b 2 (x)) + x 1 -v (v 3 C(x, 1) -vC(x, v)), (36)
where b 2 (x) = x 1-x C(x, 1).

Proof. Let a k (x), b k (x), c k (x) and d k (x) be the generating functions for the number of permutations in the nth level of the labelled generating forest F with label k, k, k and k, respectively. By Corollary 46, we have

a k (x) = xa k-1 (x), k ≥ 4, b k (x) = x(a k-1 (x) + b k-1 (x)), k ≥ 4, c k (x) = xc k (x) + x j≥k (c j (x) + b j (x) + a j (x)), k ≥ 3, d k (x) = xd k (x) + xb k (x) + xc k+1 (x) + x j≥k d j (x), k ≥ 2, with a 3 (x) = b 3 (x) = x 2 . Clearly, a k (x) = x k-1 and b k (x) = (k -2)x k-2 for all k ≥ 3. Now let A(x, v) = k≥3 a k (x)v k , B(x, v) = k≥3 b k (x)v k , C(x, v) = k≥3 c k (x)v k and D(x, v) = k≥2 d k (x)v k . Thus, A(x, v) = x 2 v 3 1-xv and B(x, v) = x 3 v 3 (1-xv) 2 .
Hence, the above recurrences can be written as

1 -x + xv 1 -v C(x, v) = xv 3 1 -v C(x, 1) + x 3 v 3 (2 -x -xv) (1 -x) 2 (1 -xv) 2 , (38) 1 -x + xv 1 -v D(x, v) = xB(x, v) + x v C(x, v) + xv 2 1 -v D(x, 1

). (39)

To solve the first functional equation, we apply the kernel method and take v = 1-x 1-2x . This gives

C(x, 1) = x 3 (2 -6x + 3x 2 ) (1 -x) 2 (1 -3x + x 2 ) 2 .
Multiplying (39) by 1x + xv 1-v , and using (38), yields

1 -x + xv 1 -v 2 D(x, v) = x 1 -x + xv 1 -v B(x, v) + x v xv 3 1 -v C(x, 1) + x 3 v 3 (2 -x -xv) (1 -x) 2 (1 -xv) 2 + xv 2 1 -v 1 -x + xv 1 -v D(x, 1).
Differentiating this functional equation with respect to v and then substituting v = 1-x 1-2x , we have

D(x, 1) = x 3 (1 -2x -x 3 ) (1 -3x + x 2 ) 3 .
The result now follows from the fact F T (x) = 1 + x + A(x, 1) + B(x, 1) + C(x, 1) + D(x, 1).

3.13. Case 188: {1432, 2143, 3214}. To find F T (x), we modify the generating trees of the last two cases as follows.

For any set of patterns R, to enumerate S n (R) one may consider the generating forest whose vertices are identified with S := n≥2 S n (R) where 12 and 21 are the roots and each non-root π ∈ S is a child of the permutation obtained from π by deleting its largest element. We will show that it is possible to label the vertices by irreducible permutations (as defined below) so that if c 1 and c 2 are any two vertices, then c 1 and c 2 have the same number of children. Indeed, we will specify (i) the irreducible permutations of the roots, and (ii) a set of succession rules explaining how to derive from the irreducible permutation of a parent the labels (presented by irreducible permutations) of all of its children. This will determine a generating forest depending on R.

For σ = σ 1 • • • σ k ∈ S k (R),
• • • 21 (k + 1)k • • • 21, k • • • 21, . . . , 1
, for all k ≥ 1 (as expected, see [START_REF] West | Generating trees and the Catalan and Schröder numbers[END_REF]). Now, we are ready to consider our case, T = {1432, 2143, 3214}. The irreducible permutations and the succession rules are given in the next proposition; the proof is left to the reader.

Proposition 48. The irreducible permutations of S k (T ) are given by α

i,k = i(i + 1) • • • k12 • • • (i - 1), α ′ i,k = i(i + 1) • • • (k -2)1(k -1)2k34 • • • (i -1), α ′′ i,k = i(i + 1) • • • (k -1)1k23 • • • (i -1), β k = 1k23 • • • (k-1), β ′ k = 1(k-1)2k34 • • • (k-2), γ k = 23 • • • (k-1)1k, γ ′ k = 2k34 • • • (k-2)1(k-1), and δ k = 67 • • • k14253.
The generating forest F is given by

Roots: α 1,2 , α 2,2 Rules: α 1,k α 1,k+1 β 3 • • • β k+1 α k+1,k+1 , for k ≥ 2, α i,k γ k+3-i α ′′ 3,k+4-i • • • α ′′ i,k+1 α i,k+1 β 3 • • • β k+2-i α k+2-i,k+2-i , for 2 ≤ i ≤ k, α ′ i,k α ′ 3,k+3-i • • • α ′ i,k (361425)γ ′ 5 • • • γ ′ k+2-i α k-i,k-i , for 3 ≤ i ≤ k -2, α ′′ i,k α ′ 3,k+4-i • • • α ′ i,k+1 α ′′ i,k β 3 γ ′ 5 • • • γ ′ k+3-i α k+1-i,k+1-i , for 3 ≤ i ≤ k -1, β k γ 3 β ′ 5 • • • β ′ k+1 β k α 2,2 , for k ≥ 3, β ′ k (142536)β ′ 5 • • • β ′ k δ 6 , for k ≥ 5, γ k γ k γ 3 γ ′ 5 • • • γ ′ k+1 α k-1,k-1 , for k ≥ 3, γ ′ k (253614)β ′ 5 • • • β ′ k-1 γ ′ k α 2,2 , for k ≥ 5, δ k δ k+1 β 3 • • • β k-4 α k-4,k-4 , for k ≥ 6, (361425) (361425)α 2,2 , (142536)
(142536)δ 6 , (253614) (253614)δ 6 .

Let A i,k = A i,k (x) be the generating function for the number of nodes α i,k in F at level n (the roots are at level 2). Similarly, we define

A ′ i,k , A ′′ i,k , B k , B ′ k , G k , G ′ k , D k , L, L ′ and L ′′ , for the number of nodes α ′ i,k , α ′′ i,k , β k , β ′ k , γ k , γ ′ k , δ k , 361425, 142536 and 253614 in F at level n, respectively. Define A k (v) = k i=1 A i,k v k-i , A ′ k (v) = k-2 i=3 A ′ i,k v k-2-i and A ′′ k (v) = k-1 i=3 A i,k v k-1-i . Also, define A(v, w) = k≥2 A k (v)w k-2 , A ′ (v, w) = k≥5 A ′ k (v)w k-5 , A ′′ (v, w) = k≥4 A ′′ k (v)w k-4 , B(w) = k≥3 B k w k-3 , B ′ (w) = k≥5 B ′ k w k-5 , G(w) = k≥3 G k w k-3 , G ′ (w) = k≥5 G ′ k w k-5 , D(w) = k≥6 D k w k-6 , L(w) = k≥6 L k w k-6 , L ′ (w) = k≥6 L ′ k w k-6 , L ′′ (w) = k≥6 L ′′ k w k-6 . L = x 6 (1 -2x)(1 -x) K , L ′ = x 6 (1 -2x)(1 -x) 2 K , L ′′ = x 6 (1 -3x + 3x 2 ) K .
Hence, by Proposition 48, we have

) = 18x 7 +31x 6 +22x 5 +8x 4 +2x 3 +2x 2 -2x+1

(1-x) 3 4 F {4231,2143,1234} (x) = 2x 10 -6x 9 +6x 8 +4x 7 +4x 6 +8x 5 +6x 4 -4x 3 +7x 2 -4x+1

(1-x) 5 5 F {2143,3412,1234} (x) = 2x 5 +10x 4 -11x 3 +11x 2 -5x+1

(1-x) 6 7 F {3421,4312,1234} (x) = -9x 7 +24x 6 +23x 5 +8x 4 +2x 3 +2x 2 -2x+1

(1-x) 3 8 F {2431,4213,1234} (x) = 26+21x+15x 2 2(1-x-x 2 -x 3 ) + 4x 10 (1+3x)-62x 9 -28x 8 +66x 7 +27x 6 -15x 5 -53x 4 +41x 3 +51x 2 -75x+24 (x-1) 3 (1-x-x 2 ) 2 9 F {2134,4312,1243} (x) = -3x 7 -5x 6 +3x 5 +10x 4 -11x 3 +11x 2 -5x+1

(1-x) 6 10 F {4213,1432,1234} (x) = 2x 11 +4x 10 +10x 9 +12x 8 +6x 7 -19x 6 -19x 5 -7x 4 -x 3 +2x-1 (x-1)(x 5 +3x 4 +2x 3 +x 2 +x-1)(x 3 +x 2 +x-1)

11 F {4231,1432,1234} (x) = 5x 9 -2x 8 -x 7 +9x 6 +9x 5 +6x 4 -4x 3 +7x 2 -4x+1

(1-x) 5 12 F {2341,4312,1324} (x) = x 10 -4x 9 +3x 8 +5x 7 -7x 5 +21x 4 -22x 3 +16x 2 -6x+1

(1-x) 7 13 F {3214,1432,1234} (x) = -

x 5 +x 3 +x 2 +x-1 x 12 +16x 11 +10x 10 +17x 9 +25x 8 +25x 7 -7x 6 -14x 5 -5x 4 -2x 3 -x 2 -2x+1

14

F {4231,2134,1243} (x) = 4x 9 -11x 8 +10x 7 +2x 6 -7x 5 +21x 4 -22x 3 +16x 2 -6x+1

(1-x) 7 16 F {2314,1432,4123} (x) = 2x 9 -x 8 +x 7 +3x 6 +6x 5 -6x 4 +11x 3 -13x 2 +6x-1 (x 2 -3x+1)(x 3 +x 2 +x-1)(1-x) 3 17 F {2341,2143,4123} (x) = x 7 -13x 5 +25x 4 -29x 3 +20x 2 -7x+1 (x 2 -3x+1)(1-x) 5 18 F {2341,1432,4123} (x) = x 10 -7x 9 +19x 8 -25x 7 +12x 6 +10x 5 -20x 4 +25x 3 -19x 2 +7x-1 (x 2 +1)(x 2 -3x+1)(x 3 -x 2 -2x+1)(x-1) 3 19 F {2431,4312,1234} (x) = 6x 9 -7x 8 -7x 7 +4x 6 +10x 5 +6x 4 -4x 3 +7x 2 -4x+1

(1-x) 5 20 F {4312,1432,1234} (x) = (x+1)(2x 9 -18x 8 +33x 7 -20x 6 +12x 5 -22x 4 +16x 3 -12x 2 +5x-1) (x-1) 5 21 F {4312,3142,1234} (x) = 2x 9 -3x 8 -2x 6 -6x 5 +21x 4 -22x 3 +16x 2 -6x+1

(1-x) 7 22 F {2134,4312,1432} (x) = x 6 +6x 5 -21x 4 +22x 3 -16x 2 +6x-1 (x-1) 7

23

F {2431,4132,1234} (x) = 1-2x x 2 -3x+1 + (24x 9 -116x 8 +213x 7 -158x 6 +9x 5 +37x 4 -9x 3 +x 2 -3x+1)x 3 (x-1) 5 (2x-1) 3 24 F {4231,3412,1234} (x) = 2x 6 -6x 5 +21x 4 -22x 3 +16x 2 -6x+1

(1-x) 7 25 F {3412,4132,1234} (x) = 3x 6 -6x 5 +21x 4 -22x 3 +16x 2 -6x+1

(1-x) 7 26 F {2134,4312,1342} (x) = -x 8 -9x 6 +27x 5 -43x 4 +38x 3 -22x 2 +7x-1

(1-x) 8 27 F {2314,4312,1432} (x) = -3x 9 -x 8 -18x 7 +17x 6 +15x 5 -44x 4 +47x 3 -27x 2 +8x-1 (2x-1)(x 2 +x-1)(x-1) 6 28 F {4231,3142,1234} (x) = 2x 8 -10x 7 +40x 6 -70x 5 +81x 4 -60x 3 +29x 2 -8x+1

(1-x) 9 31 F {2314,4312,1342} (x) = 5x 10 -22x 9 +12x 8 +89x 7 -249x 6 +354x 5 -316x 4 +179x 3 -62x 2 +12x-1 (x 2 -3x+1)(2x-1) 3 (x-1) 4 32 F {2134,1432,4123} (x) = x 10 -4x 9 +4x 8 -x 6 -5x 5 +6x 4 -11x 3 +13x 2 -6x+1 (x 2 -3x+1)(x 3 +x 2 +x-1)(x-1) 3 33 F {2134,3412,4132} (x) = 2x 7 -16x 5 +36x 4 -42x 3 +26x 2 -8x+1 (2x-1) 3 (x-1) 3 34 F {2143,4132,1234} (x) = -x 9 -2x 8 -x 7 +4x 6 -x 5 -2x 4 +3x 3 -8x 2 +5x-1 (x 2 -3x+1)(x-1)(2x-1)

35

F {1324,2143,3412} (x) = 1-9x+33x 2 -62x 3 +64x 4 -38x 5 +10x 6

(1-3x+x 2 )(1-2x) 2 (1-x) 3 36 F {3412,3124,1432} (x) = -x 8 +2x 7 -26x 6 +62x 5 -83x 4 +69x 3 -34x 2 +9x-1 (x-1) 5 (x 2 -3x+1)(2x-1) 37 F {3142,1432,1234} (x) = (x 3 -2x 2 +3x-1) 2 x 8 -x 7 +4x 6 -7x 5 +19x 4 -24x 3 +18x 2 -7x+1

38

F {4321,1423,1234} (x) = 147x 9 + 359x 8 + 367x 7 + 198x 6 + 72x 5 + 21x 4 + 6x 3 + 2x 2 + x + 1 39 F {4321,4123,1234} (x) = 185x 9 + 400x 8 + 396x 7 + 205x 6 + 72x 5 + 21x 4 + 6x 3 + 2x 2 + x + 1 40 F {2341,4312,1234} (x) = x 9 -5x 8 +6x 7 +x 6 +5x 5 -21x 4 +22x 3 -16x 2 +6x-1 (x-1) 7

Continuation of Table 2 No.

F T (x) 96 F {2134,4132,1342} (x) = -4x 8 +6x 7 -45x 6 +100x 5 -126x 4 +95x 3 -42x 2 +10x-1 (2x-1) 2 (x 2 -3x+1)(x-1) 4 97 F {2341,4312,4123} (x) = -(x-1) 4 (x 3 -2x 2 +3x-1) x 8 -4x 7 +18x 6 -35x 5 +51x 4 -47x 3 +26x 2 -8x+1

98

F {2134,3124,1432} (x) = (x-1) 3 (x 3 +2x-1) 4x 6 -7x 5 +9x 4 -15x 3 +13x 2 -6x+1 100 F {4312,1342,4123} (x) = -4x 6 -16x 5 +30x 4 -31x 3 +20x 2 -7x+1 (x-1) 3 (2x 4 -7x 3 +8x 2 -5x+1) 101 F {3124,4132,1342} (x) = -4x 6 -16x 5 +30x 4 -31x 3 +20x 2 -7x+1 (x-1) 3 (2x 4 -7x 3 +8x 2 -5x+1) 102 F {2413,3142,1234} (x) = -(x-1) 3 (x 3 -2x 2 +3x-1) x 7 -4x 6 +12x 5 -23x 4 +28x 3 -19x 2 +7x-1

104

F {2134,4132,1423} (x) = -3x 7 -4x 6 +17x 5 -46x 4 +55x 3 -32x 2 +9x-1

113

F {2134,1432,1234} (x) = 2x 5 -x 4 -3x 3 -2x 2 -2x+1 2x 5 -2x 3 -x 2 -3x+1 114 F {4312,1423,1234} (x) = -x 10 -3x 9 +2x 8 +4x 7 -9x 6 +24x 5 -43x 4 +38x 3 -22x 2 +7x-1 (x-1) 8 115 F {4231,1423,1234} (x) = -2x 10 -17x 9 +66x 8 -158x 7 +256x 6 -289x 5 +230x 4 -126x 3 +46x 2 -10x+1 (x-1) 11 116 F {4312,4123,1243} (x) = x 9 -23x 8 +133x 7 -315x 6 +419x 5 -350x 4 +188x 3 -63x 2 +12x-1 (2x-1) 4 (x-1) 5 117 F {3124,4132,1234} (x) = x 9 -6x 8 +22x 7 -53x 6 +92x 5 -104x 4 +76x 3 -35x 2 +9x-1 (x 3 -2x 2 +3x-1)(2x-1)(x-1) 5 119 F {4312,1432,1324} (x) = -350x 4 -63x 2 +419x 5 -26x 8 +138x 7 -317x 6 +188x 3 +x 9 -1+12x (2x-1) 4 (x-1) 5 120 F {4132,1423,1234} (x) = -x 8 +4x 7 -41x 6 +99x 5 -126x 4 +95x 3 -42x 2 +10x-1 (x 2 -3x+1)(2x-1) 2 (x-1) 4 122 F {4213,1432,1324} (x) = -5x 5 -19x 4 +25x 3 -19x 2 +7x-1 (x-1)(x 2 -3x+1)(3x 3 -5x 2 +4x-1)

123 F {4132,1342,1234} (x) = -3x 8 -46x 7 +141x 6 -225x 5 +221x 4 -137x 3 +52x 2 -11x+1 (x 2 -3x+1)(2x-1) 2 (x-1) 5 124 F {2341,4132,4123} (x) = -(2x-1)(x-1) 4 2x 6 -8x 5 +19x 4 -27x 3 +19x 2 -7x+1

128

F {2341,3142,4123} (x) = (x 2 -3x+1)(x-1) 5 4x 7 -23x 6 +55x 5 -78x 4 +66x 3 -33x 2 +9x-1 135 F {1432,4123,1243} (x) = -5x 5 -14x 4 +22x 3 -18x 2 +7x-1 (x-1) 4 (2x 2 -4x+1) 136 F {4213,1342,4123} (x) = x 5 -3x 3 +4x 2 -4x+1

x 5 +x 4 -6x 3 +7x 2 -5x+1 137 F {3124,1432,1342} (x) = -(x 2 -3x+1)(x 2 +2x-1) (x-1)(x 4 -2x 3 -5x 2 +5x-1)

138

F {2134,3142,1243} (x) = -(x 2 -3x+1)(x 2 +2x-1) (x-1)(x 4 -2x 3 -5x 2 +5x-1)

139

F {2143,3124,1342} (x) = -(x 2 -3x+1)(x 2 +2x-1) (x-1)(x 4 -2x 3 -5x 2 +5x-1)

140

F {3124,1432,1243} (x) = (3x-1)(x-1) 3 9x 4 -19x 3 +17x 2 -7x+1 141 F {2143,1423,1234} (x) = 2x 4 -4x 3 +7x 2 -5x+1 4x 4 -9x 3 +11x 2 -6x+1 142 F {1432,1342,4123} (x) =

x 3 +3x-1 x 3 -2x 2 +4x-1

143

F {4312,4123,1234} (x) = -x 8 -3x 7 -12x 6 +23x 5 -43x 4 +38x 3 -22x 2 +7x-1 (x-1) 8 144 F {4231,4123,1234} (x) = -3x 8 -15x 7 +40x 6 -66x 5 +81x 4 -60x 3 +29x 2 -8x+1 (x-1) 9

145 F {4312,1423,1243} (x) = 2x 7 -2x 6 -25x 5 +59x 4 -61x 3 +33x 2 -9x+1 (x-1) 2 (2x-1) 4

146 F {4132,1243,1234} (x) = x 9 -4x 8 +20x 6 -58x 5 +83x 4 -69x 3 +34x 2 -9x+1 (2x-1)(x 2 -3x+1)(x-1) 5 147 F {4132,1324,1234} (x) = -13x 10 -45x 9 +83x 8 -38x 7 -141x 6 +308x 5 -306x 4 +178x 3 -62x 2 +12x-1 (x 2 -3x+1)(x 2 +x-1)(2x-1) 2 (x-1) 5 148 F {2134,4132,1324} (x) = -5x 8 -51x 7 +172x 6 -288x 5 +283x 4 -170x 3 +61x 2 -12x+1 (2x-1) 2 (x 2 -3x+1) 2 (x-1) 3 152 F {4231,2341,4123} (x) = (x-1) 6 (x 2 -3x+1) 5x 8 -31x 7 +83x 6 -134x 5 +144x 4 -99x 3 +42x 2 -10x+1 Continuation of Table 2 No.

F T (x) 154 F {4312,1342,1423} (x) = -3x 5 -14x 4 +21x 3 -18x 2 +7x-1 (x-1)(2x 3 -4x 2 +4x-1)(x 2 -3x+1) 155 F {3124,4132,1243} (x) = -3x 5 -14x 4 +21x 3 -18x 2 +7x-1 (x-1)(2x 3 -4x 2 +4x-1)(x 2 -3x+1) 160 F {4312,1432,1342} (x) = 2x 5 -4x 4 -10x 3 +16x 2 -7x+1 (x-1)(3x-1)(2x-1)(x 2 +2x-1)

161 F {4312,4132,1342} (x) = -7x 5 -22x 4 +33x 3 -24x 2 +8x-1 (x 3 -3x 2 +4x-1)(x-1)(2x-1) 2 167 F {3142,3124,1432} (x) = -(2x-1)(x-1)(x 2 -3x+1)

x 5 -7x 4 +18x 3 -17x

2 )( 3 •

 23 2 n -(n -1)(n 2 -3n + 12)). Proof. Let B n denote the set of T -avoiding permutations in question. Suppose π ∈ B n has first letter b ≤ n -2, leftmost ascent at index m, and leftmost ascent bottom a. Note that the IDS of π not comprising a set of consecutive integers implies b ≥ a + 2 and 2 ≤ m ≤ ba. Then π may be written as π = ba 1 • • • a m-2 anπ ′ (*), where a 1 > • • • > a m-2 belong to [a + 1, b -1]. Note that the subsequence of π comprising [b + 1, n] avoids {123, 132, 3412} and thus must either (i) decrease, (ii) have the form n, n -1, . . . , s + 1, s -1, . . . , b + 1, s for some b + 2 ≤ s ≤ n -1, or (iii) have the form n, n -1, . . . , s + 1, s -1, . . . , t, s, t -1, . . . , b + 1 for some b + 3 ≤ s ≤ n -1 and b + 2 ≤ t ≤ s -1. Observe further that the bm letters in [b -1] lying within π ′ must decrease in order to avoid 3412. Let x denote the largest (and hence leftmost) letter in [b -1] occurring in π ′ . Note that x > a by the assumption on the IDS of π. If (i) holds, then the element x must occur between b + 2 and b + 1 or directly following b + 1 in order to avoid an occurrence of 1243 of the form ax(b + 2)(b + 1). Since the letters in [b -1] within π ′ must decrease, it follows that there are bm + 1 ways in which to position the elements of [bm] in π ′ , which uniquely determines π ′ . If (ii) holds, then there are once again bm + 1 ways in which to position the elements of [b -1] in π ′ for each s. Thus, combining cases (i) and (ii), there are (bm + 1)(nb -1) possibilities for π ′ for each b and m.

b 2 = 2 2 - 2 = 2 6 (n 3 -

 2222263 a -1 m -2 (bm + 1)(nb -1) + nb -2 b-a-2 (n 2 + (ab -6)n + 5b + 7aab) (2b + 5 -2a)n + (b + 2)(b + 3) -2a(b + 1)), m + 1)(nb -1) + nb -2 n-a-2 (n -4 + a) -1 6n 2 -(3a 2 -9a -11)n + 2a 3 -3a 2 -5a -18).

Proof.b

  Let π be a member of S n (T ) under consideration have first letter b ≤ n -2 and leftmost ascent bottom a. Then the elements of [b + 1, n -1] must decrease within π. For if not and b + 1 ≤ x < y ≤ n -2 with x to the left of y, then there is a 1234 if n is to the right of y, a 1243 if n occurs between x and y, and a 3412 if n occurs between n -1 and x. Let S denote the elements of [n] comprising the IDS of π. First suppose S does not consist of consecutive integers and let x denote the largest element of [a + 1, b -1] not belonging to S. We consider further cases based off of the position of the letter n within π. First assume n lies to the right of b + 1. Then x must occur after n or between b + 1 and n in order to avoid 1234. Let the leftmost ascent of π occur at index m. Since the elements of [b -1] to the right of n -1 within π must decrease, we see that there are bm + 1 ways in which to arrange the elements of [b] -S. As there are b-a-1 m-2 ways in which to select the middle m -2 elements of S, considering all a, b and m gives a -1 m -2 (bm + 1) possible permutations in this case. On the other hand, if n lies to the left of b + 1, then all letters in [b -1] -S must occur after b + 1, for otherwise there would be a 3412 as seen with (n -1)nx(b + 1) or a 1243 in the form axn(b + 1). There are thus nb -2 possible positions for n relative to the letters in [b + 1, n -2], which yields

Lemma 6 .

 6 For d ≥ 1, define N d (x) to be the generating function for permutations π = (nd -1)π ′ nπ ′′ ∈ S n (T ) such that π ′′ contains the subsequence (n -1)(n -2) • • • (nd), and set N

3. 3 . 1 .

 31 Case I. Let T = {1243, 2341, 4123} and u n denote the number of T -avoiding permutations of length n starting with n -1 and having leftmost ascent of the form a, n, where 2 ≤ a ≤ n -1.

5 , with d 4 = 1 ,

 541 where b n is given by (7) above.Proof. Let B m and D m denote the subsets of S m (T ) enumerated by b m and d m for m ≥ 3. To show[START_REF] Firro | Three-letter-pattern avoiding permutations and functional equations[END_REF], consider forming members of D n by inserting n somewhere to the right of n -1 within members of B n-1 , where n ≥ 5. First note that there are d n-1 possibilities if the letter n -2 is to directly follow n -1 within a member of B n-1 , upon deleting n -1. Let B ′ m denote the subset of B m consisting of those members where m -1 does not directly follow m. Note that one may always append the letter n to a member of B ′ n-1 without introducing an occurrence of one of the patterns in T , which yields b n-1b n-2 members of D n .

5 , 5 ℓ=0 (n - 4 - 3 2

 5543 in which case n may be inserted directly prior to any element of [ℓ + 3, n -2]. This gives nℓ) = n-additional members of D n . Combining this case with the previous yields (8). 3.3.3. Case III. Let e n denote the number of T -avoiding permutations of length n not starting with n whose leftmost ascent is of the form a, b, where 2 ≤ a < b ≤ n -2. Note that e 4 = 0 and e 5 = 2, the enumerated permutations being 23145 and 42315. The sequence e n may be expressed in terms of b n and d n as follows.

  ), we consider cases on the first and the last letters of π. Let a and b be the letters involved in the leftmost ascent of π, where 2 ≤ a < b ≤ n -2, and let x and y denote the first and last letters of π. If x = n -1 and y = n, then deleting n gives e n-1 + d n-1 possibilities in this case, upon considering whether or not b is less than n -2. If x = n -1 and y = n, then π must start n -1, n -2, . . . , b + 1. For if not, and p ∈ [b + 1, n -1] lies to the right of b within π, then π contains a 4123, as witnessed by the subsequence (n -1)abp. Then the elements of [b + 1, n] may be deleted from π, which leaves a 123-avoiding permutation of length b whose leftmost ascent is a, b, where a ≥ 2. Upon subtracting the 123-avoiding permutations of length b that start with b or whose leftmost ascent is 1, b

3. 4 . 1 .

 41 The case of two l-r maxima. We first count T -avoiding permutations that have two left-right maxima in which the first component is decreasing. Let E n denote the set of permutations of length n avoiding {123, 3412} and let e n = |E n |.Lemma 18. The number of T -avoiding permutations of length n having two left-right maxima and of the form π = aπ ′ nπ ′′ where π ′ is decreasing is given by

  ) Proof. We first determine the number e * n of members of E n whose final letter is not part of an occurrence of 231. Let E * n denote the subset of E n enumerated by e * n and let E * n,ℓ ⊆ E * n consist of those members whose final decreasing run is of length ℓ, with e * n,ℓ = |E * n,ℓ |. We define a bijection between E * n,ℓ and E * n-ℓ as follows where 1 ≤ ℓ ≤ n -1. Suppose λ ∈ E * n,ℓ and let b denote the leftmost ascent bottom of λ. First assume b ≥ 2. Then letters in [b -1] decrease so as to avoid 3412, while letters greater than b to the right of it must also decrease to avoid 123. Since b ≥ 2 and the final letter of λ is not part of a 231, it follows that the final ℓ + 1 letters of λ are 1, b + r + ℓ, b + r + ℓ -1, . . . , b + r + 1 for some r ≥ 0. In this case, we delete from λ the letters in [b + r + 1, b + r + ℓ -1], together with 1, and standardize the resulting permutation which is seen to result in a member λ ′ ∈ E * n-ℓ .

  Let π ∈ E ′ n,ℓ and b be the leftmost ascent bottom of π. If the letters to the right of n within π are decreasing, then π = π ′ bnπ ′′ (b -1) • • • 21, where π ′ and π ′′ are decreasing and π ′′ has length ℓb, assuming b ≤ ℓ. Considering all possible b gives

  for otherwise π would have a final decreasing run of length strictly greater than ℓ. Then r satisfies the same conditions as before and K again comprises [nr, n -1]. Considering all b, i and r gives the second triple sum in the expression for e ′ n,ℓ above and combining the previous cases yields the desired expression for the cardinality of E ′ n,ℓ .Let b n denote the number of T -avoiding permutations of length n having exactly two left-right maxima. It is given explicitly as follows.

  Proof. Let D n (a, b) denote the set of T -avoiding permutations whose left-right maxima are a, b, n, where 1 ≤ a < b ≤ n-1. We will show that |D n (a, b)| is given by d n (a, b) above, which implies[START_REF] Wikipedia | Permutation pattern[END_REF]. Let π = aπ ′ bπ ′′ nπ ′′′ ∈ D n (a, b). Then all letters in π ′ and [b + 1, n -1] decrease so as to avoid 1234 as well as any letters from [a + 1, b -1] in π ′′ . Also, any letters of [b -1] within π ′′′ and any letters of [a -1] occurring to the right of b must decrease, for otherwise there would be an occurrence of 3412 in either case. We now consider cases based off of whether or not the subsequence α of π comprising [a -1] is decreasing. First assume that it is. Suppose for now that the subsequence β of π comprising [a + 1, b -1] is not decreasing and thus contains exactly one ascent. Then all elements of [b -1] within π ′′′ in this case must occur at the end of π ′′′ (necessarily in decreasing order), for otherwise there is a 1234 of the form axy(b + 1) for some x, y ∈ [a + 1, b -1] with x < y. Also, any elements of [a -1] in π ′′ must occur at the end of π ′′ , for otherwise there is a 4123 of the form bzxy where z ∈ [a -1].Let j denote the number of elements of [a -1] occurring to the right of b within π and i, the number of elements of [a -1] in π ′′ , where 0 ≤ j ≤ a -1 and 0 ≤ i ≤ j. Let r denote the number of elements of [a + 1, b -1] in π ′′ . Then there are n-1-a r

1 j- 1

 11 [a + 1, b -1], then all elements of [b -1] in π ′′′ must come at the end, for otherwise there is an occurrence of 1234 of the form uvw(b + 1), where u, v ∈ [a -1] with u < v and w ∈ [a + 1, b -1]. We now consider cases on [a + 1, b -1]. If [a + 1, b -1] is confined to π ′′ , then there are a-possibilities for the letters of α in π ′ and possibilities for π ′′′ once π ′ is determined. Considering all j gives

  1b possibilities for π ′′′ once r and π ′ are specified. Note that r ≤ b -2a since π ′′′ ∩ [a + 1, b -1] = ∅. Thus, we get additional members of D n (a, b). Combining all of the previous cases implies that the cardinality of D n (a, b) is given by d n (a, b), as desired.

3. 5 . 1 .

 51 Case I. Let b n denote the number of T -avoiding permutations of length n whose leftmost ascent is of the form a, n for some 2 ≤ a ≤ n -1. We have the following recurrence relation for b n . Lemma 23. If n ≥ 3, then

3 5 3 5n - 5 -ℓ -m a - 3 m 3 . 5 . 3 .

 3353353 [a + 1, d -1] occurs to the right of n -2, then one cannot insert n between 1 and n -2 in this case as doing so introduces a 2341 of the form d(n -1)nd ′ for some d ′ ∈ [a + 1, d -1]. Upon subtracting this last case, which pertains to n-members of B ′ n-1 , one sees that there are b n-1b n-2 -n-members of D n that can be obtained either by adding n to the end of π (if π starts with n -2 or does not but has y ∈ [a -1]) or by inserting n between 1 and n -2 (if π does not start with n -2 and has a + 1 ≤ y ≤ n -3, where either π ′ = ∅ or π ′ = ∅ and no member of [a + 1, d -1] occurs to the right of n -2). Finally, from the proof of Lemma 14, one gets nadditional members of D n in the case when y = a -1 and the last letter of π is greater than a, upon inserting n somewhere to the right of 1, but not at the very end. Combining all of the prior cases gives (21). Case III. We now seek a formula for e n . Note that e 4 = 0 and e 5 = 2, the enumerated permutations being 23154 and 42315. To determine e n , we refine it as follows. Let E n denote the subset of S n (T ) enumerated by e n . Given π ∈ E n with leftmost ascent a, b where 2 ≤ a < b ≤ n-2, let V denote the subset of [a + 1, b -1] occurring to the right of b within π.

  ascent a, b, where 2 ≤ a ≤ n -4 and a + 2 ≤ b ≤ n -2, and let R denote the subset of [a + 1, b -1] occurring to the left of a within π. Then R must be of the form [a + 1, a + r] for some 0 ≤ r ≤ b -2a. To see this, suppose it is not the case and let x be the largest element of R and y be the smallest element of [a + 1, b -1] -R. By the assumption on V that it be decreasing, y is the rightmost element of [a + 1, b -1] within π and hence occurs to the right of n. But then xbny is a 2341, which is impossible. Furthermore, note that no element of [a -1] can occur to the right of n within π, for otherwise there is a 2341 of the form abnz for some z ∈ [a -1]. Thus, the subsequence of π comprising [a -1] must decrease, for otherwise there is a 4123 of the form ba 1 a 2 v where 1 ≤ a 1 < a 2 ≤ a -1 and v ∈ V . Therefore, we have shown that π contains a subsequence of the form a + r, . . . , a + 1, a, b, a -1, . . . , 1, n. Note that members of [b + 1, n -1] cannot occur between b and n (due to 1234), and thus must occur prior to a + r or to the right of n, in either case as a decreasing subsequence. Finally, members of [b + 1, n -1] occurring to the right of n must comprise a set of the form [nℓ, n -1] for some 0 ≤ ℓ ≤ n -1b, for otherwise there would be a 4123 as witnessed by b 1 abb 2 where b 1 , b 2 ∈ [b + 1, n -1]. Thus, we have the subsequence nℓ -1, . . . , b + 1, a + r, . . . , a + 1, a, b, a -1, . . . , 1, n, n -1, . . . , nℓ, into which we insert the elements of V = [a + r + 1, b -1] to form members of V n . One may verify that the letters of V may be inserted in positions directly following any member of [a -1] ∪ {b} or [nℓ, n] without introducing a pattern in T . If m denotes |V |, then m = b -1ar and thus 1 ≤ b -1a. Since the subsequence consisting of elements of V must decrease and contain at least one letter to the right of n, there are a+ℓ+m m -a-1+m m ways in which to insert the elements of V , by subtraction. Considering all possible a, b, ℓ and m implies

  where m = |V |. Let j be the smallest index in [m -1] such that π ij < π ij+1 . Then y = π ij+1 must occur to the right of the letter b + 1 in π, for otherwise there is a 1234 as seen with axy(b + 1), where x = π ij . Also, letters in [a -1] must occur between b and n (due to 2341). Let z be the leftmost letter in π belonging to [a -1].

  First assume V = [bm, b -1], where 2 ≤ m ≤ b -1a, and thus α = [a + 1, b -1m]. If j denotes the number of elements in β, then 1 ≤ j ≤ m -1 and there are m j -1 possibilities for β and γ since they are both decreasing with min(β) < max(γ) (the latter condition preventing β from being the set [bj, b -1]

  the 341 of a 3412) and β is increasing (or π m-1 1 is the 21 of a 2143). If β = ∅, the contribution is xH m , and so H m = xH m-1 + xH m + J m where J m is the contribution for the case β = ∅. Now let us write an equation for J m . If n -1 is in β, then n -1 is the last letter in π and, deleting n -1, we have a contribution of x(H m -xH m-1 ). Otherwise, n -1 is in α, and π has the form shown in Figure 1 below,

Figure 1 .

 1 Figure 1. A T -avoider counted by J m with n -1 before 1

Figure 2 .

 2 Figure 2. A T -avoider with m ≥ 2 left-right maxima

3. 10 .

 10 Case 230: {2341, 1243, 1234}. Note that all three patterns in T contain 123. We count by initial letters and define a(n; i 1 , i 2 , . . . , i m ) to be the number of T -avoiders in S n whose first m letters are i 1 , i 2 , . . . , i m , with a(n) := |S n (T )|. Clearly, a(n; n) = a(n; n -1) = a(n -1). So we need to consider T -avoiders with first letter ≤ n -2. Accordingly, for m ≥ 1, denote the generating function for T -avoiders π = π 1 π 2 • • • π n such that n -2 ≥ π 1 > π 2 > • • • > π m and π m+1 is arbitrary (resp. π m+1 = n -1) by A m (resp. B m ). Also for m ≥ 1, denote the generating function for T -avoidersπ = π 1 π 2 • • • π n such that n -1 ≥ π 1 > π 2 > • • • > π mby D m (which will be needed to define a recursion).

F

  T (x) = 1 + x + L + L ′ + L ′′ + D(1) + G ′ (1) + G(1) + B ′ (1) + B(1) + A ′′ (1, 1) + A ′ (1, 1) + A(1, 1),which leads to the following result.Theorem 49. Let T = {1432, 2143, 3214}. ThenF T (x) = (1x) 4 (1 -6x + 12x 2 -9x 3 + x 4 ) 1 -11x + 51x 2 -132x 3 + 209x 4 -208x 5 + 128x 6 -44x 7 + 5x 8 .

(x- 1 ) 3 105F 2 107F 3 110F

 1323 (x 2 -3x+1)(2x-1) {4213,2134,1342} (x) = -7x 6 -25x 5 +51x 4 -56x 3 +32x 2 -9x+1 (2x-1)(x-1) 2 (x 2 -3x+1) {4213,3412,1342} (x) = -(x 2 -x+1)(2x-1) 3 (4x 3 -7x 2 +5x-1)(x-1) {2134,3142,1432} (x) = -(x-1)(3x 3 -5x 2 +4x-1) 2 x 9 +2x 8 -27x 7 +86x 6 -144x 5 +150x 4 -100x 3 +42x 2 -10x+1 111 F {2143,3142,1234} (x) = (x 3 -2x 2 +3x-1) 2 (2x 3 -3x 2 +4x-1)(x-1) 3

2 +7x- 1 168F 1 (x 4 - 6 186F

 1146 {3124,1432,1423} (x) = -(x 2 -3x+1)(2x-1) 2 (x-1)(x 4 -13x 3 +16x 2 -7x+1) 169 F {3142,1423,1234} (x) = -(x 2 -3x+1)(2x-1) 2 (x-1)(x 4 -13x 3 +16x 2 -7x+1) 179 F {2134,1432,1423} (x) = -2x 5 -8x 4 +12x 3 -12x 2 +6x-5x 3 +10x 2 -6x+1)(x 2 -x+1) 181 F {2143,1324,1234} (x) = -2x 3 +3x-1 x 4 -2x 3 +2x 2 -4x+1 183 F {4132,4123,1234} (x) = x 8 -8x 7 +31x 6 -75x 5 +98x 4 -75x 3 +35x 2 -9x+1 (2x-1) 2 (x-1) {4132,4123,1243} (x) = --27x 5 +55x 4 -57x 3 +32x 2 -9x+1+4x 6 (3x-1)(x 2 -3x+1)(x-1) 4 189 F {2143,2134,1432} (x) = -x 4 -7x 3 +8x 2 -5x+1 x 5 -5x 4 +13x 3 -12x 2 +6x-1 200 F {2143,3124,1243} (x) = x 3 -6x 2 +5x-1 (x-1)(5x 2 -5x+1) 202 F {1432,1423,1234} (x) = x 4 -4x 3 +10x 2 -6x+1 3x 4 -11x 3 +15x 2 -7x+1 205 F {1432,1324,1234} (x) = -x 7 -2x 6 +4x 5 -17x 4 +24x 3 -18x 2 +7x-1 2x 6 -14x 5 +34x 4 -38x 3 +24x 2 -8x+1 206 F {1432,1243,1234} (x) = -x 6 +5x 4 -12x 3 +12x 2 -6x+12x 5 -13x 4 +21x 3 -17x 2 +7x-1

Table 1 :

 1 Small Wilf classes not amenable to INSENC.

			Start of Table
	No. T	Reference	No. T

  • • • a t anπ ′ , where a 1 > a 2 > • • • > a t > a for some t ≥ 1 or π = (n -1)anπ ′ .One may verify that the letters a 1 , . . . , a t are extraneous concerning the avoidance of the patterns in T (note that these letters have no bearing on 2341, since letters in [a + 1, n -2] occurring to the right of a in π must occur as a decreasing subsequence to avoid 4123). Let u ′ (m, a) denote the number of T -avoiding permutations of length m starting (m -1)am. Considering all possible a and t thus implies that there are

	form above.	n-2 a=2	n-2-a t=0	n-2-a t	u ′ (n -t, a) permutations π of the stated

  • • • 21. One may verify in each case that the mapping λ → λ ′ is a bijection, as desired. Since e * n,n = 1 and e * n =

		n ℓ=1 e * n,ℓ , we
	have e * n = 1 +	n-1 ℓ=1 e

* n-ℓ for n ≥ 2, with e * 1 = 1, which implies e * n = 2 n-1 and e * n,ℓ

  Since β is nonempty but does not contain members of either [a + 1, c] or [d, n -2], then it must be the case that d ≥ c + 2, whence a+ 1 ≤ c ≤ n -4 and c + 2 ≤ d ≤ n -2. Note further that β comprises [c + 1, s] for some s ∈ [c + 1, d -1]. For if not, and s 1 , s 2 ∈ [c + 1, d -1] with s 1 < s 2 , s 1 ∈ α and s 2 ∈ β, then s 1 s 2 (n -1)c is a 2341. Finally, the elements of [a + 1, c -1] belonging to γ must comprise [t, c -1] for some t ∈ [a + 1, c].For if not, and t 1 , t 2 ∈ [a + 1, c -1] with t 1 > t 2 , t 1 ∈ α and t 2 ∈ γ, then t 1 (c + 1)(n -1)t 2 is a 2341. Thus, we have shown in this case that α, β and γ comprise the sets

  we say that σ is reducible if there is a subsequence σ ′ of length k -1 such that by inserting k in some position in the set A(σ ′ ) of active sites we obtain σ. Otherwise, σ is irreducible. Thus, to specify the generating forest F , we need to know the set of irreducible permutations and the succession rules (what irreducible permutations are obtained by inserting a letter in a given irreducible permutation).For instance, if R = {132}, then 12 is reducible because if π = π ′ 1π ′′ 2π ′′′ avoids 132 then π ′′ = ∅, which leads to the conclusion that π avoids 132 if and only if π ′ 1π ′′ avoids 132, thus 2 is a letter verifying the reducibility of 12. In general, it is not hard to see that there is exactly one irreducible permutation in S k (132), namely, k • • • 21. Moreover, by inserting k + 1 in k • • • 21, we obtain the following irreducible permutations (k + 1)k • • • 21, k • • • 21, . . . , 1, thus we have the following succession rule k

Table 2 :

 2 Small Wilf classes of three 4-letter patterns counted by INSENC. {4321,3412,1234} (x) = 73x 9 + 199x 8 + 240x 7 + 162x 6 + 69x 5 + 21x 4 + 6x 3 + 2x 2 + x + 1 2 F {4321,3142,1234} (x) = 85x 9 + 221x 8 + 252x 7 + 164x 6 + 69x 5 + 21x 4 + 6x 3 + 2x 2 + x + 1

	Begin of Table

F {2314,4132,1342} (x) = -4x 6 -25x 5 +51x 4 -56x 3 +32x 2 -9x+1 (2x-1)(x-1) 2 (x 2 -3x+1) 2

A permutation π = π 1 π 2 • • • π n ∈ S n determines n + 1 positions, called sites, between its entries. The sites are denoted 1, 2, . . . , n + 1 left to right. In particular, site i is the space between π i-1 and π i if 2 ≤ i ≤ n. Site i in π is said to be active (with respect to T ) if, by inserting n + 1 into π in site i, we get a permutation in S n+1 (T ), otherwise inactive. For the next two triples T under consideration and π ∈ S n (T ), sites 1 and n + 1 are always active, and if π n = n, then site n is active.

Given T ∈ T and π ∈ S n (T ), define A(π) to be the set of all active sites for π, and define L(π) to be the set of active sites lying to the left of n. For example, for T = {3412, 3421, 2341}, L(23154) = {1, 2, 4} since there are 4 possible sites to insert 6 to the left of n = 5 and, of these insertions, only 236154 is not in S 6 (T ).

Lemma 41. If T denotes one of the following two cases and π ∈ S n (T ), then A(π) = L(π)∪{n+1} unless π n < n and site n is active, in which case A(π) = L(π) ∪ {n, n + 1}.

Proof. No site to the right of n is active except (possibly) site n and (definitely) site n + 1 for if n + 1 is inserted after n in a site ≤ n -1, then n (n + 1) π n-1 π n is a 3412 or a 3421, both forbidden.

3.11. Case 240: {3412, 3421, 2341}. Here, if site n is inactive, then 1 and n + 1 are the only active sites iff π 1 = n. In particular, there are at least 3 active sites unless site n is inactive and π 1 = n.

To construct the generating forest, we first specify the labels.

Otherwise, if the site n is active, then label π by k, and if the site n is inactive, then label it by k.

For instance, all 3 sites for π = 12 are active and π n = n, so the label for 12 is 3. Also, 12 has three children 312, 132 and 123 with active sites {1, 3, 4}, {1, 2, 3, 4} and {1, 2, 3, 4}, respectively, hence labels 3, 4 and 4. All sites for 21 are active, so its label is 3, and it has three children 321, 231 and 213 with active sites {1, 3, 4}, {1, 2, 4} and {1, 2, 3, 4}, respectively, hence labels 3, 3 and 4.

To establish the succession rules, we need to know how the active sites of a child are related to those of its parent. This relationship is given by the following proposition. The proof makes frequent use of Lemma 41 and is left to the reader.

Proposition 42. Suppose π ∈ S n (T ) and let π j denote the result of inserting n + 1 into an active site j.

If j ≤ n -1, then for 1 ≤ i ≤ j, site i is active in π j iff site i is active in π; site n + 1 is active in π j iff site n is active in π; site n + 2 is active in π j ; all other sites in π j are inactive.

Next, suppose n is an active site in π. Then for 1 ≤ i ≤ n -1, site i is active in π n iff site i is active in π; sites n and n + 2 are active in π n ; all other sites in π n are inactive. Also, site n + 1 is active in π (as always) and for 1 ≤ i ≤ n -1, site i is active in π n+1 iff site i is active in π; sites n, n + 1, n + 2 are active in π n+1 ; all other sites in π n+1 are inactive.

Lastly, suppose n is not an active site in π. Then site n + 1 is active in π and for 1 ≤ i ≤ n -1, site i is active in π n+1 iff site i is active in π; sites n + 1, n + 2 are active in π n+1 ; all other sites in π n+1 are inactive.

By finding C(x, v) from (34), and then substituting it in (35)-(36), we obtain

Multiplying the first equation by 1 + x + xv 1-v and the second by 1 + xv 1-v , then summing the results, we have

where

There are two power series v ′ and v ′′ such that K(x, v ′ ) = K(x, v ′′ ) = 0 given by v ′ = r + 1 and v ′′ = t + 1, where r and t are as stated above. For example, the expansion of v ′ begins

Substituting v ′ and v ′′ for v in (37) gives a pair of equations for A(x, 1) and B(x, 1) with solution

which, by (34), implies

Since F T (x) = 1 + x + A(x, 1) + B(x, 1) + C(x, 1), the result follows.

3.12. Case 109: {3412, 3421, 2143}. In this case, if site n is inactive, then 1 and n + 1 are the only active sites iff π 1 ≥ 3. If site i is active for i ≤ n -1, then all sites ≤ i are active. Hence, for n ≥ 2, the active sites ≤ n -1 form a nonempty initial segment of the positive integers.

For n ≥ 2, say π ∈ S n is mostly increasing if it has exactly one descent and the descent bottom is the last entry, that is, if π has the form π = 12

We now assign labels. So suppose n ≥ 2 and π ∈ S n (T ) has k active sites. For instance, all 3 sites are active for both 12 and 21 and 12 is increasing while 21 is mostly increasing, so their labels are 3 and 3 respectively; 12 has three children 312, 132 and 123 with active sites {1, 3, 4}, {1, 2, 3, 4} and {1, 2, 3, 4}, respectively, hence labels 3, 4 and 4 because the second is mostly increasing and the third is increasing; 21 has three children 321, 231 and 213 with active sites {1, 3, 4}, {1, 2, 3, 4} and {1, 2, 4}, respectively, hence labels 3, 4 and 3.

To establish the succession rules, we have the following proposition. The proof is left to the reader.

Proposition 45. Suppose n ≥ 2 and π ∈ S n (T ) has k active sites.

If π is increasing, then all sites {1, 2, . . . , n + 1} are active (hence, k = n + 1) and

If π is mostly increasing, then all sites {1, 2, . . . , n + 1} are active (hence, k = n + 1) and

Now suppose π is neither increasing nor mostly increasing.

If site n is active so that the active sites for π are {1, 2, . . . , k -2, n, n + 1}, then

If site n is inactive so that the active sites for π are {1, 2, . . . , k -1, n + 1}, then

An immediate consequence is

Corollary 46. The labelled generating forest F is given by Roots: 3, 3 Rules:

Theorem 47. Let T = {3412, 3421, 2143}. Then

Proposition 48 leads to the following system of equations:

Let K = 5x 8 -44x 7 + 128x 6 -208x 5 + 209x 4 -132x 3 + 51x 2 -11x + 1. Then, by computer algebra, one can show the solution of the above system is given by

57

F {2143,1432,1234} (x) = x 7 +x 6 -x 5 +3x 3 +2x 2 +2x-1

67 F {4312,1324,1243} (x) = 2x 10 -7x 8 +65x 7 -187x 6 +274x 5 -248x 4 +145x 3 -53x 2 +11x-1 (x-1) 6 (2x-1) 3 68 F {4312,1342,1243} (x) = 3x 7 -4x 6 -14x 5 +36x 4 -42x 3 +26x 2 -8x+1 (x-1) 3 (2x-1) 3 70 F {4312,3124,1243} (x) = -11x 7 -62x 6 +128x 5 -146x 4 +102x 3 -43x 2 +10x-1 (2x-1) 3 (x-1) 5 71 F {4231,1243,1234} (x) = -4x 8 -2x 7 -17x 6 +25x 5 -43x 4 +38x 3 -22x 2 +7x-1 (x-1) 8 73 F {4231,1324,1234} (x) = -x 10 -15x 8 +55x 7 -111x 6 +149x 5 -141x 4 +89x 3 -37x 2 +9x-1 (x-1) 10 79 F {2134,4132,1234} (x) = 2x 11 +x 10 -10x 9 -9x 8 +12x 7 +17x 6 -30x 5 +2x 4 +28x 3 -24x 2 +8x-1 (x 2 +2x-1)(2x-1)(x-1) 3 (x 2 +x-1) 2 81 F {2431,4312,1324} (x) = 145x 3 +11x-1-248x 4 -193x 6 +274x 5 -53x 2 -x 9 -13x 8 +80x 7 ) (2x-1) 3 (x-1) 6 82 F {4312,3142,1243} (x) = x 7 +2x 6 -27x 5 +59x 4 -61x 3 +33x 2 -9x+1 (x-1) 2 (2x-1) 4 83 F {4312,3412,1243} (x) = x 7 +2x 6 +4x 5 -23x 4 +36x 3 -25x 2 +8x-1 (x-1)(2x-1) 4 85 F {2314,4132,1432} (x) = -x 5 +5x 4 -11x 3 +13x 2 -6x+1 (2x-1)(x 2 -3x+1)(x-1) 2 87 F {4312,3124,1432} (x) = -2x 9 -46x 7 +143x 6 -226x 5 +221x 4 -137x 3 +52x 2 -11x+1 (x-1) 5 (x 2 -3x+1)(2x-1) 2 89 F {3142,4132,1234} (x) = -4x 5 -16x 4 +24x 3 -19x 2 +7x-1 (2x-1)(x 2 -3x+1)(x-1) 3 91 F {4213,1342,1243} (x) = -4x 5 -14x 4 +17x 3 -14x 2 +6x-1 (3x-1)(x 2 -x+1)(x-1) 3 92 F {2314,3124,1432} (x) = (x 3 -2x 2 +3x-1)(x 2 +x-1)(1-x) 3 x 9 -2x 8 +6x 7 -4x 6 -7x 5 +32x 4 -40x 3 +25x 2 -8x+1