ON MULTI-AVOIDANCE OF GENERALIZED PATTERNS

SERGEY KITAEV AND TOUFIK MANSOUR

Abstract. In [Kit1] Kitaev discussed simultaneous avoidance of two 3-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. In three essentially different cases, the numbers of such n-permutations are 2^{n−1}, the number of involutions in S_{n}, and 2E_{n}, where E_{n} is the n-th Euler number. In this paper we give recurrence relations for the remaining three essentially different cases.

To complete the descriptions in [Kit3] and [KitMans], we consider avoidance of a pattern of the form x-y-z (a classical 3-pattern) and beginning or ending with an increasing or decreasing pattern. Moreover, we generalize this problem: we demand that a permutation must avoid a 3-pattern, begin with a certain pattern and end with a certain pattern simultaneously. We find the number of such permutations in case of avoiding an arbitrary generalized 3-pattern and beginning and ending with increasing or decreasing patterns.

1. Introduction and Background

Permutation patterns: All permutations in this paper are written as words π = a_{1}a_{2} … a_{n}, where the a_{i} consist of all the integers 1, 2, …, n. Let α ∈ S_{n} and τ ∈ S_{k} be two permutations. We say that α contains τ if there exists a subsequence 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n such that (α_{i_{1}}, …, α_{i_{k}}) is order-isomorphic to τ; in such a context τ is usually called a pattern. We say that α avoids τ, or is τ-avoiding, if such a subsequence does not exist. The set of all τ-avoiding permutations in S_{n} is denoted by S_{n}(τ). For an arbitrary finite collection of patterns T, we say that α avoids T if α avoids any τ ∈ T; the corresponding subset of S_{n} is denoted by S_{n}(T).

While the case of permutations avoiding a single pattern has attracted much attention, the case of multiple pattern avoidance remains less investigated. In particular, it is natural, as the next step, to consider permutations avoiding pairs of patterns τ_{1}, τ_{2}. This problem was solved completely for τ_{1}, τ_{2} ∈ S_{3} (see [SchSim]), for τ_{1} ∈ S_{3} and τ_{2} ∈ S_{4} (see [W]), and for τ_{1}, τ_{2} ∈ S_{4} (see [B, K] and references therein). Several recent papers [CW, MV1, Kr, MV3, MV2] deal with the case τ_{1} ∈ S_{3}, τ_{2} ∈ S_{k} for various pairs τ_{1}, τ_{2}.

Generalized permutation patterns: In [BabStein] Babson and Steingrímsson introduced generalized permutation patterns (GPs) where two adjacent letters in a pattern may be required to be adjacent in the permutation. Such an adjacency requirement is indicated by the absence of a dash between the corresponding letters in the pattern. For example, the permutation π = 516423 has only one occurrence of the pattern 2-31, namely the subword 564, but the pattern 2-3-1 occurs also in the subwords 562 and 563. Note that a classical pattern should, in our notation, have dashes at the beginning and end. Since most of the patterns considered in this paper satisfy this, we suppress these dashes from the notation. Thus, a pattern with no dashes corresponds to a contiguous subword anywhere in a permutation. The motivation for introducing these patterns was the study of Mahonian statistics. A number of results on GPs were obtained by Claesson, Kitaev and Mansour. See for example [Claes], [Kit1, Kit2, Kit3] and [Mans1, Mans2, Mans3].

As in [SchSim], dealing with the classical patterns, one can consider the case when permutations have to avoid two or more generalized patterns simultaneously. A complete solution for the number of permutations avoiding a pair of 3-patterns of type (1,2) or (2,1), that is the patterns having one internal dash, is given in [ClaesMans1]. In [Kit1] Kitaev discussed simultaneous avoidance of two 3-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. In three essentially different cases, the numbers of such n-permutations are 2^{n−1}, the number of involutions in S_{n}, and 2E_{n}, where E_{n} is the n-th Euler number. The remaining cases are avoidance of 123 and 231, 213 and 231, 132 and 213. In Section 3 we give recurrence relations for these cases.

In Section 4, we consider avoidance of a pattern x-y-z, and beginning or ending with increasing or decreasing pattern. This completes the results made in [KitMans], which concerns the number of permutations that avoid a generalized 3-pattern and begin or end with an increasing or decreasing pattern.

In Sections 5–8, we give enumeration for the number of permutations that avoid a generalized 3-pattern, begin and end with increasing or decreasing patterns. We record our results in terms of either generating functions, or exponential generating functions, or formulas for the numbers which appear.

In Section 9, we discuss possible directions of generalization of the results from Sections 5–8.

2. Preliminaries

The reverse R(π) of a permutation π = a_{1}a_{2} … a_{n} is the permutation a_{n} … a_{2}a_{1}. The complement C(π) is the permutation b_{1}b_{2} … b_{n} where b_{i} = n + 1 − a_{i}. Also, R ∘ C is the composition of R and C. For example, R(13254) = 45231, C(13254) = 53412 and R ∘ C(13254) = 21435. We call these bijections of S_{n} to itself trivial, and it is easy to see that for any pattern p the number A_{p}(n) of permutations avoiding the pattern p is the same as for the patterns R(p), C(p) and R ∘C(p). For example, the number of permutations that avoid the pattern 132 is the same as the number of permutations that avoid the pattern 231. This property holds for sets of patterns as well. If we apply one of the trivial bijections to all patterns of a set G, then we get a set G′ for which A_{G′}(n) is equal to A_{G}(n). For example, the number of permutations avoiding {123, 132} equals the number of those avoiding {321, 312} because the second set is obtained from the first one by complementing each pattern.

In this paper we denote the nth Catalan number by C_{n}; the generating function for these numbers by C(x); the nth Bell number by B_{n}.

Also, N_{p}^{q}(n) denotes the number of permutations that avoid the pattern p and begin with the pattern q; G_{p}^{q}(x) (respectively, E_{p}^{q}(x)) denotes the ordinary (respectively, exponential) generating function for the number of such permutations. Besides, N_{p}^{q,r}(n) denotes the number of permutations that avoid the pattern p, begin with the pattern q and end with the pattern r; G_{p}^{q,r}(x) (respectively, E_{p}^{q,r}(x)) denotes the ordinary (respectively, exponential) generating function for the number of such permutations.

Recall the following properties of C(x):

(1)  C(x) = \frac{1 − \sqrt{1 − 4x}}{2x} = \frac{1}{1 − xC(x)}.

3. Simultaneous avoidance of two 3-patterns with no dashes

3.1. Avoidance of patterns 123 and 231 simultaneously. We first consider the avoidance of the patterns 123 and 231 simultaneously. Let a(n; i_{1}, i_{2}, …, i_{m}) denote the number of permutations π ∈ S_{n}(123, 231) such that π_{1}π_{2} … π_{m} = i_{1}i_{2} … i_{m} and let a(n) = |S_{n}(123, 231)|. By the definitions, we get that a(n) = ∑_{j=1}^{n} a(n; j) and a(n; n) = a(n − 1). Hence

(2)  a(n) = a(n − 1) + a(n; 1) + a(n; 2) + ⋯ + a(n; n − 1).

Also, by the definitions, for all 1 ≤ i ≤ n − 1, we get

(3)  a(n; i) = ∑_{j=1}^{i−1} a(n; i, j) + ∑_{j=i+1}^{n} a(n; i, j).

Suppose π ∈ S_{n}(123, 231) is such that π_{1} = i and π_{2} = j. If i > j then there is no occurrence of the pattern 123 or 231 that contains π_{1}, so a(n; i, j) = a(n − 1; j). If i < j then since π avoids 123 and 231, we get that i < π_{3} < j, and thus in this case a(n; i, j) = a(n−2; i)+a(n−2; i+1)+⋯+a(n−2; j−2). Hence, using (2) and (3), we get the following theorem.

Proposition 1. For all n ≥ 3,

a(n) = a(n − 1) + a(n; 1) + a(n; 2) + ⋯ + a(n; n − 1),

where for all 1 ≤ i ≤ n,

a(n; i) = ∑_{j=1}^{i−1} a(n − 1; j) + ∑_{j=i}^{n−2}(n − 1 − j)a(n − 2; j),

and a(3; 1) = 1, a(3; 2) = 1, a(3; 3) = 2.

Using this theorem, we get quickly the first values of the sequence a(n) for n = 0, 1, 2, …, 10:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ a(n) & 1 & 1 & 2 & 4 & 11 & 39 & 161 & 784 & 4368 & 27260 & 189540 \end{matrix}

3.2. Avoidance of patterns 132 and 213 simultaneously. We consider avoidance of the patterns 132 and 213 simultaneously. Let b(n; i_{1}, i_{2}, …, i_{m}) denote the number of permutations π ∈ S_{n}(132, 213) such that π_{1}π_{2} … π_{m} = i_{1}i_{2} … i_{m} and let b(n) = |S_{n}(132, 213)|. Suppose π ∈ S_{n}(132, 213) is such that π_{1} = i and π_{2} = j. If i > j then, since π avoids 213, we get π_{3} ≤ i − 1. Thus

(4)  b(n; i, j) = ∑_{k=1, k≠j}^{i−1} b(n − 1; j, k).

If i < j then, since π avoids 132, we get π_{3} ≤ i − 1 or π_{3} ≥ j + 1. Thus

(5)  b(n; i, j) = ∑_{k=1}^{i−1} b(n − 1; j − 1, k) + ∑_{k=j}^{n−1} b(n − 1; j − 1, k).

Using (4) and (5), we get the following theorem.

Proposition 2. We have b(n) = ∑_{i,j=1}^{n} b(n; i, j) with b(n; i, i) = 0 for all n, i ≥ 1;

b(n; i, j) = ∑_{k=1}^{i−1} b(n − 1; j, k) if i > j;

b(n; i, j) = ∑_{k=1}^{i−1} b(n − 1; j − 1, k) + ∑_{k=j}^{n−1} b(n − 1; j − 1, k) if i < j;

and b(2; 1, 2) = b(2; 2, 1) = 1, b(2; 1, 1) = b(2; 1, 1) = 0.

Using this theorem, we get

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ b(n) & 1 & 1 & 2 & 4 & 11 & 37 & 149 & 705 & 3814 & 23199 & 156940 \end{matrix}

3.3. Avoidance of the patterns 213 and 231 simultaneously. We now consider avoidance of the patterns 213 and 231 simultaneously. This case is equivalent to avoidance of the patterns 132 and 312 by applying the reverse operation. Let c(n; i_{1}, i_{2}, …, i_{m}) denote the number of permutations π ∈ S_{n}(132, 312) such that π_{1}π_{2} … π_{m} = i_{1}i_{2} … i_{m} and let c(n) = |S_{n}(132, 312)|. We proceed as in the previous case. For n ≥ i > j ≥ 1, we have

(6)  c(n; i, j) = ∑_{k=1}^{j−1} c(n − 1; j, k) + ∑_{k=i}^{n−1} c(n − 1; j, k).

For 1 ≤ i < j ≤ n, we have

(7)  c(n; i, j) = ∑_{k=1}^{i−1} c(n − 1; j − 1, k) + ∑_{k=j}^{n−1} c(n − 1; j − 1, k).

Using (6) and (7), we get the following theorem. Proposition 3. We have c(n) = ∑_{i,j=1}^{n} c(n; i, j) with

c(n; i, i) = 0 for all n, i ≥ 1;

c(n; i, j) = ∑_{k=1}^{j−1} c(n − 1; j, k) + ∑_{k=i}^{n−1} c(n − 1; j, k) if i > j;

c(n; i, j) = ∑_{k=1}^{i−1} c(n − 1; j − 1, k) + ∑_{k=j}^{n−1} c(n − 1; j − 1, k) if i < j;

and c(2; 1, 2) = c(2; 2, 1) = 1, c(2; 1, 1) = c(2; 1, 1) = 0.

Using this theorem, we get

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ c(n) & 1 & 1 & 2 & 4 & 10 & 30 & 108 & 454 & 2186 & 11840 & 71254 \end{matrix}

4. Avoiding a pattern x-y-z and beginning or ending with certain patterns

Recall that according to the definitions from Section 2, N_{p}^{q,r}(n) denotes the number of permutations that avoid the pattern p, begin with the pattern q and end with the pattern r; G_{p}^{q,r}(x) (respectively, E_{p}^{q,r}(x)) denotes the ordinary (respectively, exponential) generating function for the number of such permutations. Besides, C_{n} and C(x) denote the n-th Catalan number and the ordinary generating function for the Catalan numbers. Proposition 4. We have

G_{1-3-2}^{12...k}(x) = x^{k}C^{2}(x).

Proof. Suppose π = π′nπ′′ ∈ S_{n}(1-3-2) is such that π_{1} < π_{2} < ⋯ < π_{k} and π_{j} = n. It is easy to see that π avoids 1-3-2 if and only if π′ is a 1-3-2-avoiding permutation on the letters n − j + 1, n − j + 2, …, n − 1, and π′′ ∈ S_{n−j}(1-3-2). If we now consider two cases, namely j = k and j ≥ k + 1, we get

G_{1-3-2}^{12...k}(x) = x^{k}C(x) + xG_{1-3-2}^{12...k}(x)C(x).

Thus, G_{1-3-2}^{12...k}(x) = x^{k}C(x)/(1 − xC(x)) and, using (1), we get the desired result. □

Proposition 5. We have

G_{1-3-2}^{k(k−1)...1}(x) = x^{k}C^{k+1}(x).

Proof. Suppose π = π′nπ′′ ∈ S_{n}(1-3-2) is such that π_{1} > π_{2} > ⋯ > π_{k} and π_{j} = n. It is easy to see that π avoids 1-3-2 if and only if π′ is a 1-3-2-avoiding permutation on the letters n − j + 1, n − j + 2, …, n − 1, and π′′ ∈ S_{n−j}(1-3-2). If we consider separately the cases j = 1 and j ≥ 2, we get

G_{1-3-2}^{k(k−1)...1}(x) = xG_{1-3-2}^{(k−1)(k−2)...1}(x) + xG_{1-3-2}^{k(k−1)...1}(x)C(x).

Hence,

G_{1-3-2}^{k(k−1)...1}(x) = xG_{1-3-2}^{(k−1)(k−2)...1}(x)/(1 − xC(x))

and, using (1), we get G_{1-3-2}^{k(k−1)...1}(x) = xC(x)G_{1-3-2}^{(k−1)(k−2)...1}(x). By induction on k, using the fact that G_{1-3-2}^{1}(x) = C(x) − 1 = xC^{2}(x), we get the desired result. □

Proposition 6. We have

G_{2-1-3}^{12...k}(x) = x^{k}C^{k+1}(x).

Proof. One can use the same considerations as we have in the proof of Proposition 5, by considering a permutation π = π′1π′′ ∈ S_{n}(2-1-3) such that π_{1} < π_{2} < ⋯ < π_{k} and π_{j} = 1. □

Proposition 7. We have

G_{2-1-3}^{k(k−1)...1}(x) = x^{k}C^{2}(x).

Proof. One can use the same considerations as we have in the proof of Proposition 4, by considering a permutation π = π′1π′′ ∈ S_{n}(2-1-3) such that π_{1} > π_{2} > ⋯ > π_{k} and π_{j} = 1. □

Let s_{n}(i_{1}, …, i_{m}) denote the number of permutations π ∈ S_{n}(1-2-3) such that π_{1}π_{2} … π_{m} = i_{1}i_{2} … i_{m}. It is easy to see that

(8)  s_{n}(n) = s_{n}(n − 1) = C_{n−1},

and for 1 ≤ t ≤ n − 2,

(9)  s_{n}(t) = s_{n}(t, n) + ∑_{j=1}^{t−1} s_{n}(t, j) = s_{n−1}(t) + ∑_{j=1}^{t−1} s_{n−1}(j).

Now, (8) and (9) with induction on t give

(10)  s_{n}(n − t) = ∑_{j=0}^{t}(−1)^{j}\binom{t − j}{j}C_{n−j−1}

Let us prove the following proposition. Proposition 8. We have

G_{1-2-3}^{12...k}(x) = \{ \begin{matrix}0, & if k ≥ 3, \\ x^{2}C^{2}(x), & if k = 2, \\ xC^{2}(x), & if k = 1 . \end{matrix}

Proof. For k ≥ 3, the statement is obviously true. If k = 1 then

G_{1-2-3}^{1}(x) = C(x) − 1 = xC^{2}(x).

Suppose now that k = 2. From the definitions, for all n ≥ 2, we have

N_{1-2-3}^{12}(n) = ∑_{i=1}^{n−1} ∑_{j=i+1}^{n} s_{n}(i, j).

In this formula, j can only be equal to n, since otherwise we have an occurrence of the pattern 1-2-3. Using this fact with (8) and (9), we get for n ≥ 2,

N_{1-2-3}^{12}(n) = ∑_{i=1}^{n−1} s_{n}(i, n) = ∑_{i=1}^{n−1} s_{n−1}(i) = C_{n−1}.

Hence, G_{1-2-3}^{12}(x) = x(C(x) − 1) = x^{2}C^{2}(x). □

Proposition 9. We have

N_{1-2-3}^{k(k−1)...1}(n) = ∑_{t=1}^{n+1−k} \binom{n − t}{k − 1} ∑_{j=0}^{n−t}(−1)^{j}\binom{n − t − j}{j}C_{n−t−j−1}.

Proof. From the definitions, we have

N_{1-2-3}^{k(k−1)...1}(n) = ∑_{t=1}^{n+1−k} \binom{n − t}{k − 1}s_{n}(t).

Using (10), we get

N_{1-2-3}^{k(k−1)...1}(n) = ∑_{t=1}^{n+1−k} \binom{n − t}{k − 1} ∑_{j=0}^{n−t}(−1)^{j}\binom{n − t − j}{j}C_{n−t−j−1}.

□

5. Avoiding a pattern x-y-z, beginning and ending with certain patterns simultaneously

Recall that according to the definitions from Section 2, N_{p}^{q,r}(n) denotes the number of permutations that avoid the pattern p, begin with the pattern q and end with the pattern r; G_{p}^{q,r}(x) (respectively, E_{p}^{q,r}(x)) denotes the ordinary (respectively, exponential) generating function for the number of such permutations. Proposition 10. Let k, ℓ ≥ 1 and m = max(k, ℓ). We have

(i) G_{1-3-2}^{12...k,ℓ(ℓ−1)...1}(x) = x^{k+ℓ−1}C^{2}(x).

(ii) G_{1-3-2}^{12...k,12...ℓ}(x) = x^{k+ℓ−1}C^{ℓ+1}(x) + \frac{x^{m}−x^{k+ℓ−1}}{1−x}.

(iii) G_{1-3-2}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) = x^{k+ℓ−1}C^{k+1}(x) + \frac{x^{m}−x^{k+ℓ−1}}{1−x}.

(iv) the generating function G_{1-3-2}(x, y, z) = ∑_{k,ℓ≥0} G_{1-3-2}^{k(k−1)...1,12...ℓ}(x)y^{k}z^{ℓ}

for the sequence {G_{1-3-2}^{k(k−1)...1,12...ℓ}(x)}_{k,ℓ≥0} (where k and ℓ go through all natural numbers) is

\frac{1}{1 − x(y + z)} (x(y + z + yz) + \frac{C(x) − 1}{(1 − xyC(x))(1 − xzC(x))}) .

Proof.

(i) Beginning with 12 … k and ending with ℓ(ℓ − 1) … 1: Suppose π = π′nπ′′ ∈ S_{n}(1-3-2) is such that π_{1} < π_{2} < ⋯ < π_{k}, π_{n} < π_{n−1} < ⋯ < π_{n−ℓ+1} and π_{j} = n. It is easy to see that π avoids 1-3-2 if and only if π′ is a 1-3-2-avoiding permutation on the letters n − j + 1, n − j + 2, …, n − 1, and π′′ ∈ S_{n−j}(1-3-2). We now consider three cases, namely j = k, k + 1 ≤ j ≤ n − ℓ and j = n − ℓ + 1. In terms of generating functions, we have

\begin{matrix}G_{1-3-2}^{12...k,ℓ(ℓ−1)...1}(x) \\ = x^{k}G_{2-1-3}^{ℓ(ℓ−1)...1}(x) + xG_{1-3-2}^{12...k}(x)G_{2-1-3}^{ℓ(ℓ−1)...1}(x) + x^{ℓ}G_{1-3-2}^{12...k}(x) + x^{k+ℓ−1}, \end{matrix}

where we observed that to avoid 1-3-2 and end with ℓ(ℓ − 1) … 1 is the same as to avoid 2-1-3 and begin with ℓ(ℓ − 1) … 1 by applying the reverse and complement operations. Also, we added the term x^{k+ℓ−1}, since when j = k = n − ℓ + 1, we have one “good” (k + ℓ − 1)-permutation, which is not counted by our three cases.

From Propositions 4 and 7, we have that

G_{1-3-2}^{12...k}(x) = x^{k}C^{2}(x) and G_{2-1-3}^{ℓ(ℓ−1)...1}(x) = x^{ℓ}C^{2}(x).

Thus, using the fact that xC^{2}(x) = C(x) − 1, we get

G_{1-3-2}^{12...k,ℓ(ℓ−1)...1}(x) = x^{k+ℓ}C^{2}(x)(2 + xC^{2}(x)) + x^{k+ℓ−1}
= x^{k+ℓ−1}(C(x) − 1)(C(x) + 1) + x^{k+ℓ−1}
= x^{k+ℓ−1}C^{2}(x).

(ii) Beginning with 12 … k and ending with 12 … ℓ: Suppose π = π′nπ′′ ∈ S_{n}(1-3-2) is such that π_{1} < π_{2} < ⋯ < π_{k}, π_{n} > π_{n−1} > ⋯ > π_{n−ℓ+1} and π_{j} = n. As above, π avoids 1-3-2 if and only if π′ is a 1-3-2-avoiding permutation on the letters n − j + 1, n − j + 2, …, n − 1, and π′′ ∈ S_{n−j}(1-3-2). We consider the cases j = k, k + 1 ≤ j ≤ n − ℓ and j = n. In terms of generating functions, the first approximation for the function G_{1-3-2}^{12...k,12...ℓ}(x) is

G_{1-3-2}^{12...k,12...ℓ}(x) ≈ x^{k}G_{2-1-3}^{12...ℓ}(x) + xG_{1-3-2}^{12...k}(x)G_{2-1-3}^{12...ℓ}(x) + xG_{1-3-2}^{12...k,12...(ℓ−1)}(x),

where we observed that to avoid 1-3-2 and end with 12 … ℓ is the same as to avoid 2-1-3 and begin with 12 … ℓ by applying the reverse and complement operations. We use the sign “≈” because there are some “good” permutations, which are not counted by our considerations. We discuss them below.

From Propositions 4 and 6, we have that G_{1-3-2}^{12...k}(x) = x^{k}C^{2}(x) and G_{2-1-3}^{12...ℓ}(x) = x^{ℓ}C^{ℓ+1}(x). Thus, using the fact that xC^{2}(x) = C(x) − 1 and G_{1-3-2}^{12...k,1}(x) = G_{1-3-2}^{12...k}(x) = x^{k}C^{2}(x) (Proposition 4), we get

G_{1-3-2}^{12...k,12...ℓ}(x)

≈ x^{k+ℓ}C^{ℓ+1}(x) + x^{k+ℓ+1}C^{ℓ+3}(x) + xG_{1-3-2}^{12...k,12...(ℓ−1)}(x)
= x^{k+ℓ}C^{ℓ+2}(x) + xG_{1-3-2}^{12...k,12...(ℓ−1)}(x)
= x^{k+ℓ}C^{ℓ+2}(x) + x^{k+ℓ}C^{ℓ+1}(x) + x^{2}G_{1-3-2}^{12...k,12...(ℓ−2)}(x)

= ⋯ = x^{k+ℓ}C^{4}(x)(C^{ℓ−2}(x) + C^{ℓ−3}(x) + ⋯ + 1) + x^{k+ℓ−1}C^{2}(x)

= x^{k+ℓ−1}(C(x) − 1)C^{2}(x)\frac{1−C^{ℓ−1}(x)}{1−C(x)} + x^{k+ℓ−1}C^{2}(x)
= x^{k+ℓ−1}C^{ℓ+1}(x).

To complete the proof of this case, we observe that in our considerations above, we do not count increasing permutations of length m = max(k, ℓ), m + 1, …, k + ℓ − 2, which satisfy all our restrictions. We did not count them because the k-beginning and ℓ-ending in these permutations overlap in more than one letter. So, to get the desired result, we need to add the term

x^{m} + x^{m+1} + … + x^{k+ℓ−2} = (x^{m} − x^{k+ℓ−1})/(1 − x)

to the approximate value of G_{1-3-2}^{12...k,12...ℓ}(x). For example, expanding the ordinary generating function G_{1-3-2}^{12,123}(x), we have, in particular, that there are 2002 10-permutations that avoid 1-3-2, begin with the pattern 12 and end with the pattern 123.

(iii) Beginning with k(k − 1) … 1 and ending with ℓ(ℓ − 1) … 1: If ℓ = 1 then, by Proposition 5, G_{1-3-2}^{k(k−1)...1,1}(x) = x^{k}C^{k+1}(x). Suppose ℓ ≥ 2, and π = π′1π′′ ∈ S_{n}(1-3-2) is such that π_{1} > π_{2} > ⋯ > π_{k}, π_{n} < π_{n−1} < ⋯ < π_{n−ℓ+1} and π_{j} = 1. Obviously, π′′ is the empty word, since otherwise we have an occurrence of the pattern 1-3-2 starting from the letter 1. Thus, the first approximation for the function G_{1-3-2}^{k(k−1)...1,ℓ(ℓ−1)...1} is

\begin{matrix}G_{1-3-2}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) \\ ≈ xG_{1-3-2}^{k(k−1)...1,(ℓ−1)(ℓ−2)...1}(x) = ⋯ = x^{k+ℓ−1}C^{k+1}(x). \end{matrix}

Like in the previous case, we did not count decreasing permutations of length m, m + 1, …, k + ℓ − 2, which satisfy all our restrictions. Thus, to get the desired result, we add the term (x^{m} − x^{k+ℓ−1})/(1 − x) to the approximate value of G_{1-3-2}^{k(k−1)...1,ℓ(ℓ−1)...1}(x).

(iv) Beginning with k(k − 1) … 1 and ending with 12 … ℓ: Suppose π = π′nπ′′ ∈ S_{n}(1-3-2). Any letter of π′ is greater than any letter of π′′, since otherwise we have an occurrence of the pattern 1-3-2 in π containing the letter n which is forbidden. Also, π′ and π′′ avoid 1-3-2. If π begins with k(k − 1) … 1, ends with 12 … ℓ and π′ and π′′ are not empty, then π′ must begin with k(k − 1) … 1 and π′′ must end with 12 … ℓ. If π′ is empty then π′′ must begin with (k − 1)(k − 2) … 1 and end with 12 … ℓ. If π′′ is empty then π′ must begin with k(k − 1) … 1 and end with 12 … (ℓ − 1). In terms of generating functions, the discussion above leads to the following:

\begin{matrix}G_{1-3-2}^{k(k−1)...1,12...ℓ}(x) ≈ xG_{1-3-2}^{k(k−1)...1}(x)G_{2-1-3}^{12...ℓ}(x) \\ +xG_{1-3-2}^{(k−1)...1,12...ℓ}(x) + xG_{1-3-2}^{k(k−1)...1,12...(ℓ−1)}(x), \end{matrix}

where we observed that to avoid 1-3-2 and end with 12 … ℓ is the same as to avoid 2-1-3 and begin with 12 … ℓ. However, to put the sign “=” instead of “≈”, we have to correct the right-hand side of the recurrence relation by observing that when either k = 1 and ℓ = 0, or k = 0 and ℓ = 1, or k = 1 and ℓ = 1, the formula does not count the permutation π = 1 which satisfies all the conditions needed. Thus, if we make correction of the righthand side, then multiply both parts of the obtained equality by x^{k}y^{ℓ} and sum over all natural k and ℓ we get (recall the definition of G_{1-3-2}(x, y, z) in the statement of the theorem):

\begin{aligned}G_{1-3-2}(x, y, z) & = x ∑_{k,ℓ≥0} G_{1-3-2}^{k(k−1)...1}(x)G_{2-1-3}^{12...ℓ}(x)y^{k}z^{ℓ} \\ & +x(y + z)G_{1-3-2}(x, y, z) + x(y + z + yz). \end{aligned}

From Propositions 5 and 6, G_{1-3-2}^{k(k−1)...1}(x)G_{2-1-3}^{12...ℓ}(x) = x^{k+ℓ}C^{k+ℓ+2}(x), and thus

G_{1-3-2}(x, y, z)

= \frac{1}{1−x(y+z)} (x(y + z + yz) + ∑_{k,ℓ≥0} x^{k+ℓ}C^{k+ℓ+2}(x)y^{k}z^{ℓ})

= \frac{1}{1−x(y+z)} (x(y + z + yz) + zC^{2}(z) ∑_{k≥0}(xyC(x))^{k} ∑_{ℓ≥0}(xzC(x))^{ℓ})

= \frac{1}{1−x(y+z)} (x(y + z + yz) + \frac{C(x)−1}{(1−xyC(x))(1−xzC(x))}) ,

where we used that xC^{2}(x) = C(x) − 1. □

Proposition 11. Let k, ℓ ≥ 1 and m = max(k, ℓ). We have (i) G_{2-1-3}^{12...k,12...ℓ}(x) = x^{k+ℓ−1}C^{k+1}(x) + \frac{x^{m}−x^{k+ℓ−1}}{1−x}.

(ii) G_{2−1−3}^{k(k−1)...1,12...ℓ}(x) = x^{k+ℓ−1}C^{2}(x).

(iii) G_{2-1-3}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) = x^{k+ℓ−1}C^{ℓ+1}(x) + \frac{x^{m}−x^{k+ℓ−1}}{1−x}.

(iv) the generating function G_{2-1-3}(x, y, z) = ∑_{k,ℓ≥0} G_{2-1-3}^{12...k,ℓ(ℓ−1)...1}(x)y^{k}z^{ℓ}

for the sequence {G_{2-1-3}^{12...k,ℓ(ℓ−1)...1}(x)}_{k,ℓ≥0} (where k and ℓ go through all natural numbers) is

\frac{1}{1 − x(y + z)} (x(y + z + yz) + \frac{C(x) − 1}{(1 − xyC(x))(1 − xzC(x))}) .

Proof. We apply the reverse and complement operations and then use the results of Proposition 10. For example, to avoid 2-1-3, begin with 12 … k and end with 12 … ℓ is the same as to avoid 1-3-2, begin with 12 … ℓ and end with 12 … k. □

Let h_{n}^{k,ℓ}(t; s) denote the number of 1-2-3-avoiding n-permutations such that π_{k} = t, π_{n−ℓ+1} = s, π_{1} > π_{2} > ⋯ > π_{k}, and π_{n−ℓ+1} > π_{n−ℓ+2} > ⋯ > π_{n}. Also, we define g_{n}(i_{1}, i_{2}, …, i_{m}; b) to be the number of 1-2-3-avoiding n-permutations such that π_{1}π_{2} ⋯ π_{m} = i_{1}i_{2} … i_{m} and π_{n} = b. We need the following two lemmas to prove Proposition 14. Lemma 12. For all n ≥ 2, g_{n}(a; b) is given by

\{ \begin{matrix}0, & 2 ≤ a + 1 < b ≤ n, \\ \binom{n−2}{a−1}, & 1 ≤ a ≤ n − 1, b = a + 1 \\ \binom{n+a−b−3}{a−2} − \binom{n+a−b−3}{a−b−2}, & 2 ≤ b < a ≤ n. \\ \binom{n+a−5}{a−2} − \binom{n+a−5}{a−4}, & 1 ≤ b < a ≤ n. \end{matrix}

Proof. By definitions we have (1) g_{n}(a; b) = 0 for all 2 ≤ a + 1 < b ≤ n;

(2) g_{n}(a; a + 1) = g_{n}(a, 1; a + 1) + … + g_{n}(a, a − 1; a + 1) + g_{n}(a, a + 2; a + 1) + … + g_{n}(a, n − 1; a + 1) + g_{n}(a, n; a + 1). Using the fact that no there exists a permutation π ∈ S_{n}(1-2-3) such that π_{1} = a, π_{2} ≤ a − 2, and π_{n} = a + 1 we get

g_{n}(a; a + 1) = g_{n}(a, a − 1; a + 1) + g_{n}(a, a + 2; a + 1) + … + g_{n}(a, n; a + 1).

Using the fact that no there exists a permutation π ∈ S_{n}(1-2-3) such that π_{1} = a and a ≤ π_{2} ≤ n−1 we get g_{n}(a; a+1) = g_{n}(a, a−1; a+1)+g_{n}(a, n; a+ 1). On the other hand, it is easy to see that g_{n}(a, a−1; a+1) = g_{n−1}(a−1; a) and g_{n}(a, n; a + 1) = g_{n−1}(a; a + 1). Hence,

g_{n}(a; a + 1) = g_{n−1}(a − 1; a) + g_{n−1}(a; a + 1).

Using induction we get that g_{n}(a; a + 1) = \binom{n−2}{a−1} for all n ≥ 2 and 1 ≤ a ≤ n − 1.

(3) Using Equation (10) we get

g_{n}(a; 1) = g_{n}(a; 2) = s_{n−1}(a − 1) = ∑_{j=0}^{n−a}(−1)^{j}\binom{n − a − j}{j}C_{n−2−j}.

Similarly as (2) we have for all a > b,

g_{n}(a; b) = g_{n−1}(b − 1; b) + g_{n−1}(b + 1; b) + g_{n−1}(b + 2; b) + ⋯ + g_{n−1}(a; b).

Using the above equation together with induction on n, a, b, we get the desired result. □

Lemma 13. The number h_{n}^{k,ℓ}(t; s) is given by

\{ \begin{matrix}\binom{n−t}{k−1}\binom{s−1}{ℓ−1}g_{n+2−k−ℓ}(t − (ℓ − 1); s − (ℓ − 1)), & if 1 ≤ s < t ≤ n; \\ h_{n}^{k,ℓ}(t + 1; t), & if s = t + 1; \\ h_{n−1}^{k,ℓ−1}(t; s − 1) + h_{n−1}^{k−1;ℓ}(t; s − 1), & if 2 ≤ t + 1 < s ≤ n. \end{matrix}

Proof. (1) Let n ≥ t > s ≥ 1; so by definitions we get

h_{n}^{k,ℓ}(t; s) = \binom{n − t}{k − 1}\binom{s − 1}{ℓ − 1}g_{n−(k−1)−(ℓ−1)}(t − (ℓ − 1); s − (ℓ − 1)).

(2) Let s = t + 1; so it is easy to see h_{n}^{k,ℓ}(t; t + 1) = h_{n}^{k,ℓ}(t + 1; t);

(3) Let 2 ≤ t + 1 < s ≤ n. Let π be any permutations in S_{n}(1-2-3) such that π_{k} = t and π_{n+1−ℓ} = s where π_{1} > ⋯ > π_{k} and π_{n+1−ℓ} > ⋯ > π_{n}; so there two possibilities either π_{n+2−ℓ} = s − 1 or π_{j} = s − 1 where j ≤ k − 1. In this first case we get that there exist h_{n−1}^{k,ℓ−1}(t; s − 1) permutations, and in the second case we have that there exist h_{n−1}^{k−1;ℓ}(t; s − 1) permutations. (We extend the number h_{n}^{k,l}(a; b) as 0 for any ℓ ≤ 0 or k ≤ 0). □

We recall that the Kronecker delta δ_{n,k} is defined to be

δ_{n,k} = \{ \begin{matrix}1, & if n = k, \\ 0, & else. \end{matrix}

Proposition 14. We have

(i) G_{1-2-3}^{12...k,12...ℓ}(x) = \{ \begin{matrix}0, & if k ≥ 3 or ℓ ≥ 3 \\ xC^{2}(x), & if k = 1 and ℓ = 1 \end{matrix} ,

N_{1-2-3}^{12,12}(n) = \{ \begin{matrix}0, & if n = 3 \\ C_{n−2}, & else \end{matrix} , and N_{1-2-3}^{12,1}(n) = N_{1−2−3}^{1,12}(n) = C_{n−1}.

(ii) The number N_{1-2-3}^{k(k−1)...1,12...ℓ}(n) is given by

\{ \begin{matrix}0, & if ℓ ≥ 3, \\ ∑_{t=1}^{n−k} \binom{n−t−1}{k−1} ∑_{j=0}^{n−t−1}(−1)^{j}\binom{n−t−j−1}{j}C_{n−t−j−1} + (k − 1)δ_{n,k+1}, & if ℓ = 2, \\ ∑_{t=1}^{n+1−k} \binom{n−t}{k−1} ∑_{j=0}^{n−t}(−1)^{j}\binom{n−t−j}{j}C_{n−t−j−1}, & if ℓ = 1. \end{matrix}

(iii) The number N_{1-2-3}^{12...k,ℓ(ℓ−1)...1}(n) is given by

\{ \begin{matrix}0, & if k ≥ 3, \\ ∑_{t=1}^{n−ℓ} \binom{n−t−1}{ℓ−1} ∑_{j=0}^{n−t−1}(−1)^{j}\binom{n−t−j−1}{j}C_{n−t−j−1} + (ℓ − 1)δ_{n,ℓ+1}, & if k = 2, \\ ∑_{t=1}^{n+1−ℓ} \binom{n−t}{ℓ−1} ∑_{j=0}^{n−t}(−1)^{j}\binom{n−t−j}{j}C_{n−t−j−1}, & if k = 1. \end{matrix}

(iv) N_{1−2−3}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) = ∑_{t=1}^{n−k+1} ∑_{s=ℓ}^{n} h_{n}^{k,ℓ}(t; s), where h_{n}^{k,ℓ}(t; s) is given in Lemma 13.

Proof.

(i) Beginning with 12 … k and ending with 12 … ℓ: If k ≥ 3 or ℓ ≥ 3, the statement is obvious, since in this case 12 … k or 12 … ℓ does not avoid the pattern 1-2-3. If k = 1 or ℓ = 1, we get the statement from Proposition 8 (in the first of these cases we apply the reverse and complement operations). Suppose now that k = 2, ℓ = 2, and an n-permutation π avoids 1-2-3, begins with the pattern 12 and ends with the pattern 12. The letter n must be next to the leftmost letter, since otherwise two leftmost letters and n form the pattern 1-2-3. Also, the letter 1 must be next to the rightmost letter, since otherwise 1 and the two rightmost letters form the pattern 1-2-3. It is easy to see now that there are C_{n−2} possibilities to choose π, since we can take any 1-2-3-avoiding permutation on the letters {2, 3, …, n − 1} (there are C_{n−2} such permutations), then let the letters n and 1 be in the second and (n − 1)-st positions respectively. These considerations only fail when n = 3, since in this case the second and (n − 1)-st positions coincide. However, in this case we obviously have no permutations with the good properties.

(ii) Beginning with k(k − 1) … 1 and ending with 12 … ℓ: The statement is true for ℓ ≥ 3, since in this case 12 … ℓ does not avoid 1-2-3. For the case ℓ = 1 we use Proposition 9. Suppose now that ℓ = 2, and an n-permutation π avoids 1-2-3, begins with the pattern k(k − 1) … 1 and ends with the pattern 12. The letter 1 must be next to the rightmost letter, since otherwise 1 and two rightmost letters form the pattern 1-2-3. So, to form π we can take any (n−1)-permutation on the letters {2, 3, …, n} that avoids 1-2-3 and begins with the pattern k(k − 1) … 1 (the number of such permutations is given by Proposition 9), and then let the letter 1 be in the (n − 1)-st position. Also, we observe that in the case n = k + 1 we have k −1 extra permutations, which are obtained from the (n−1)-permutations having the k − 1 leftmost letters in decreasing order and two rightmost letters in increasing order.

(iii) Beginning with 12 … k and ending with ℓ(ℓ − 1) … 1: By the reverse and complement operations, to avoid 1-2-3, begin with the pattern 12 … k and end with the pattern ℓ(ℓ − 1) … 1 is the same as to avoid 1-2-3, begin with the pattern ℓ(ℓ − 1) … 1 and end with the pattern 12 … k, so we can apply the results of the previous case.

(iv) Beginning with k(k −1) … 1 and ending with ℓ(ℓ−1) … 1: The statement is immediate from the definitions of N_{1-2-3}^{k(k−1)...1,ℓ(ℓ−1)...1}(n) and h_{n}^{k,ℓ}(t, s). □

6. Avoiding a pattern xyz, beginning and ending with certain patterns simultaneously

Recall that according to Section 2, E_{p}^{q,r}(x) denotes the exponential generating function for the number of permutations that avoid the pattern p, begin with the pattern q and end with the pattern r.

Proposition 15. We have (i)

E_{213}^{12...k,12...ℓ}(x) = \{ \begin{matrix}E_{132}^{12...ℓ}(x), & if k = 1 \\ E_{213}^{12...k}(x), & if ℓ = 1 \end{matrix} ,

where E_{132}^{12...ℓ}(x) and E_{213}^{12...k}(x) are given in Table 1(K1-K3) and Table 1(K5) respectively. For k, ℓ ≥ 2, E_{213}^{12...k,12...ℓ}(x) satisfies

\begin{matrix}\frac{∂}{∂x}E_{213}^{12...k,12...ℓ}(x) \\ = E_{213}^{12...k,12...(ℓ−1)}(x) + (E_{213}^{12...k,12}(x) + \frac{x^{k−1}}{(k−1)!}) E_{132}^{12...ℓ}(x). \end{matrix}

(ii)

E_{213}^{12...k,ℓ(ℓ−1)...1}(x) = \{ \begin{matrix}E_{132}^{ℓ(ℓ−1)...1}(x), & if k = 1 \\ E_{213}^{12...k}(x), & if ℓ = 1 \end{matrix} ,

where E_{132}^{ℓ(ℓ−1)...1}(x) and E_{213}^{12...k}(x) are given in Table 1(K4) and (K5) respectively. For k, ℓ ≥ 2, E_{213}^{12...k,ℓ(ℓ−1)...1}(x) satisfies

\begin{matrix}\frac{∂}{∂x}E_{213}^{12...k,ℓ(ℓ−1)...1}(x) = \frac{x^{ℓ−1}}{(ℓ−1)!}E_{213}^{12...k}(x) \\ + (E_{213}^{12...k,12}(x) + \frac{x^{k−1}}{(k−1)!}) E_{132}^{ℓ(ℓ−1)...1}(x) + \binom{k+ℓ−2}{k−1} \frac{x^{k+ℓ−2}}{(k+ℓ−2)!}. \end{matrix}

(iii)

E_{213}^{k(k−1)...1,12...ℓ}(x) = \{ \begin{matrix}E_{132}^{12...ℓ}(x), & if k = 1 \\ E_{213}^{k(k−1)...1}(x), & if ℓ = 1 \end{matrix} ,

Formula  Eq.
E_{132}^{1}(x) = _{\frac{1}{1−∫_{0}^{x} e^{−t^{2}/2} dt}}  K1
E_{132}^{12}(x) = \frac{e^{−x^{2}/2}}{1−∫_{0}^{x} e^{−t^{2}/2} dt} − x − 1  K2

E_{132}^{12...k}(x) = E_{132}^{1}(x)·

· ∫_{0}^{x} ∫_{0}^{t_{k−2}} ⋯ ∫_{0}^{t_{2}} (e^{−t_{1}^{2}/2} − \frac{t_{1}+1}{E_{132}^{1}(t_{1})}) dt_{2} ⋯ dt_{k−2}dt_{1}  K3
E_{132}^{k(k−1)...1}(x) = \frac{E_{132}^{1}(x)}{(k−1)!} ∫_{0}^{x} t^{k−1}e^{−t^{2}/2} dt.  K4
E_{213}^{12...k}(x) = ∫_{0}^{x} ∫_{0}^{t} \frac{s^{k−2}e^{T (t)−T (s)}}{(k−2)!(1−∫_{0}^{t} e^{−m^{2}/2}dm)} dsdt  K5

where T (x) = −x^{2}/2 + ∫_{0}^{x} \frac{e^{−t^{2}/2}}{1−∫_{0}^{t} e^{−s^{2}/2}ds} dt

E_{213}^{k(k−1)...1}(x) = −\frac{x^{k−1}}{(k−1)!}

+ ∑_{n=0}^{k−2} ∫_{0}^{x} ∫_{0}^{t_{n}} ⋯ ∫_{0}^{t_{1}} \frac{C_{k−n}(t) + δ_{n,k−2}}{1 − ∫_{0}^{t} e^{−m^{2}/2}dm} dtdt_{1} ⋯ dt_{n}  K6

where C_{k}(x) = e^{T (x)}· · ∫_{0}^{x} ∫_{0}^{t_{k−2}} ⋯ ∫_{0}^{t_{1}} e^{−T (t)} (\frac{e^{−t^{2}/2}}{1−∫_{0}^{t} e^{−m^{2}/2}dm} − t − 1) dtdt_{1} ⋯ dt_{k−2} with T (x) which is given in K5.

Table 1. [Kit3, Equation 12, Theorem 6(i),6(ii),7,10,11]. where E_{132}^{12...ℓ}(x) and E_{213}^{k(k−1)...1}(x) are given in Table 1(K1-K3) and (K6) respectively. For k, ℓ ≥ 2, E_{213}^{k(k−1)...1,12...ℓ}(x) satisfies

\begin{matrix}\frac{∂}{∂x}E_{213}^{k(k−1)...1,12...ℓ}(x) = E_{213}^{(k−1)...1,12...ℓ}(x) \\ +E_{213}^{k(k−1)...1,12}(x)E_{132}^{12...ℓ}(x) + E_{213}^{k(k−1)...1,12...(ℓ−1)}(x). \end{matrix}

(iv)

E_{213}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) = \{ \begin{matrix}E_{132}^{ℓ(ℓ−1)...1}(x), & if k = 1 \\ E_{213}^{k(k−1)...1}(x), & if ℓ = 1 \end{matrix} ,

where E_{132}^{ℓ(ℓ−1)...1}(x) and E_{213}^{k(k−1)...1}(x) are given in Table 1(K4) and (K6) respectively. For k, ℓ ≥ 2, E_{213}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) satisfies

\begin{matrix}\frac{∂}{∂x}E_{213}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) \\ = E_{213}^{(k−1)...1,ℓ(ℓ−1)...1}(x) + (E_{132}^{ℓ(ℓ−1)...1}(x) + \frac{x^{ℓ−1}}{(ℓ−1)!}) E_{213}^{k(k−1)...1,12}(x). \end{matrix}

Proof.

(ii) Beginning with 12 … k and ending with ℓ(ℓ−1) … 1: The statement is obviously true when k = 1 and ℓ = 1. Suppose now that k ≥ 2, ℓ ≥ 2 and an (n + 1)-permutation π avoids 213, begins with the pattern 12 … k and ends with the pattern 12 … ℓ. The letter (n + 1) can only be in the position k, or in the position i, where (k + 1) ≤ i ≤ n − ℓ + 1, or in the position n − ℓ + 2. In the first case, we choose the (k − 1) leftmost letters in \binom{n}{k−1} ways, rearrange them into the increasing order, and observe, that the letters of π to the right of (n + 1) must form an (n − k + 1)-permutation, that avoids 213 and ends with the pattern ℓ(ℓ − 1) … 1 (the number of such permutations, using the reverse and complement operation, is equal to the number of (n − k + 1)-permutations that avoid 132 and begin with the pattern ℓ(ℓ − 1) … 1). In the third case, we choose the (ℓ − 1) rightmost letters in \binom{n}{ℓ−1} ways, rearrange them into the decreasing order, and observe, that the letters of π to the left of (n + 1) must form an (n − ℓ + 1)-permutation, that avoids 213, begins with the pattern 12 … k, and ends with the pattern 12 (if it ends with the pattern 21, the letter (n + 1) and two letters immediately to the left of it form the pattern 213). In the second case, we choose the letters of π to the left of (n + 1) in \binom{n}{i−1} ways and observe, that these letters must form a (i − 1)-permutation that avoids 213, begins with the pattern 12 … k and ends with the pattern 12. At the same time, the letters to the right of (n + 1) must form an (n − i + 2)-permutation that avoids 213 and ends with the pattern ℓ(ℓ−1) … 1. Besides, we observe that if n = k + ℓ − 2, that is |π| = k + ℓ − 1, and first k-letters of π are rearranged into the increasing order, whereas the last ℓ letters are rearranged in the decreasing order, we have a number of extra “good” permutations. The number of such permutations is the number of ways of choosing the first (k − 1) letters, that is \binom{k+ℓ−2}{k−1}. This discussion leads to the following:

N_{213}^{12...k,ℓ(ℓ−1)...1}(n + 1) = \binom{n}{k−1}N_{132}^{ℓ(ℓ−1)...1}(n − k + 1) + \binom{n}{ℓ−1}N_{213}^{12...k}(n − ℓ + 1)

+ ∑_{i=0}^{n} \binom{n}{i}N_{213}^{12...k,12}(i)N_{132}^{ℓ(ℓ−1)...1}(n − i) + \binom{k + ℓ − 2}{k − 1}δ_{n,k+ℓ−2},

where δ_{n,k+ℓ−2} is the Kronecker delta. We get the desired result by multiplying both sides of the last equality by x^{n}/n! and summing over n.

(i) Beginning with 12 … k and ending with 12 … ℓ: The statement is obviously true when k = 1 and ℓ = 1. Suppose now that k ≥ 2, ℓ ≥ 2 and an (n + 1)-permutation π avoids 213, begins with the pattern 12 … k and ends with the pattern 12 … ℓ. The letter (n + 1) can only be in the position k, or in the position i, where (k + 1) ≤ i ≤ n − ℓ, or in the (n + 1)-th position. In the last case, the number of such permutations is obviously N_{213}^{12...k,12...ℓ−1}(n). In the first case, we choose the (k − 1) leftmost letters in \binom{n}{k−1} ways, rearrange them into increasing order, and observe, that the letters of π to the right of (n + 1) must form an (n − k + 1)-permutation, that avoids 213 and ends with the pattern 12 … ℓ (the number of such permutations, using the reverse and complement operation, is equal to the number of (n − k + 1)-permutations that avoid 132 and begin with the pattern 12 … ℓ). In the second case, we choose the letters of π to the left of (n + 1) in \binom{n}{i−1} ways and observe, that these letters must form a (i − 1)- permutation that avoids 213, begins with the pattern 12 … k and ends with the pattern 12 (if it ends with the pattern 21, the letter (n + 1) and two letters immediately to the left of it form the pattern 213). At the same time, the letters to the right of (n+1) must form an (n−i+2)-permutation that avoids 213 and ends with the pattern 12 … ℓ. This discussion leads to the following:

\begin{matrix}N_{213}^{12...k,12...ℓ}(n + 1) = N_{213}^{12...k,12...ℓ−1}(n) \\ + ∑_{i=0}^{n} \binom{n}{i}N_{213}^{12...k,12}(i)N_{132}^{12...ℓ}(n − i) + \binom{n}{k − 1}N_{132}^{12...ℓ}(n − k + 1). \end{matrix}

We get the desired result by multiplying both sides of the last equality by x^{n}/n! and summing over n.

(iii,iv) Beginning with k(k−1) … 1 and ending with 12 … ℓ or with ℓ(ℓ − 1) … 1: We proceed in the same way as we do under considering the previous case. □

We observe that the number of permutations that avoid the pattern 132, begin with the pattern p and end with the pattern r is equal to the number of permutations that avoid the pattern 213, begin with the pattern r′ and

18 SERGEY KITAEV AND TOUFIK MANSOUR

end with the pattern p′, where p′ and r′ are obtained from p and r by applying the composition of the reverse and complement operations. Thus,

E_{132}^{p,r}(x) = E_{213}^{C∘R(r),C∘R(p)}(x).

Proposition 16. We define Θ_{k}(x) to be

∫_{0}^{x} sec(Ψ_{6}(t)) (sin(Ψ_{3}(t)) − \frac{\sqrt{3}}{2}e^{−t/2}) (Φ_{k}(t) + \frac{t^{k−1}}{(k − 1)!}) dt,

where

Φ_{k}(x) = \frac{e^{x/2}}{(k − 1)!} sec(Ψ_{6}(x)) ∫_{0}^{x} e^{−t/2}t^{ℓ−1} sin(Ψ_{3}(t)) dt,

and Ψ_{k}(x) = \frac{\sqrt{3}}{2}x + \frac{π}{k}. We have (i) E_{123}^{12...k,12...ℓ}(x) =

= \{ \begin{matrix}0, if k ≥ 3 or ℓ ≥ 3, \\ x − \frac{1}{2} − \frac{\sqrt{3}}{2} tan(Ψ_{6}(x))+ \\ sec(Ψ_{6}(x)) (\frac{\sqrt{3}}{2} (e^{x/2} + e^{−x/2}) − sin(Ψ_{3}(x))) , \\ if k = 2 and ℓ = 2, \\ \frac{\sqrt{3}}{2}e^{x/2} sec(Ψ_{6}(x0) − 1, \\ if k = 1 and ℓ = 1, \\ \frac{\sqrt{3}}{2}e^{x/2} sec(Ψ_{6}(x)) − \frac{1}{2} − \frac{\sqrt{3}}{2} tan(Ψ_{6}(x)), \\ otherwise; \end{matrix}

(ii) E_{123}^{12...k,ℓ(ℓ−1)...1}(x) = \{ \begin{matrix}0, & if k ≥ 3, \\ Φ_{ℓ}(x), & if k = 1, \\ Θ_{ℓ}(x), & if k = 2; \end{matrix}

(iii) E_{123}^{k(k−1)...1,12...ℓ}(x) = \{ \begin{matrix}0, & if ℓ ≥ 3, \\ Φ_{k}(x), & if ℓ = 1, \\ Θ_{k}(x), & if ℓ = 2; \end{matrix}

(iv) E_{123}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) is given by

\{ \begin{matrix}E_{123}^{ℓ(ℓ−1)...1}(x), & if k = 1, \\ E_{123}^{k(k−1)...1}(x), & if ℓ = 1, \\ E_{123}^{k(k−1)...1}(x) − E_{123}^{k(k−1)...1,12}(x), & if ℓ = 2; \end{matrix}

For k ≥ 2 and ℓ ≥ 3, E_{123}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) satisfies

\begin{matrix}\frac{∂}{∂x}E_{123}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) \\ = (E_{123}^{ℓ(ℓ−1)...1}(x) + \frac{x^{ℓ−1}}{(ℓ−1)!}) E_{123}^{k(k−1)...1,21}(x) + E_{123}^{(k−1)...1,ℓ(ℓ−1)...1}(x), \end{matrix}

where E_{123}^{k(k−1)...1}(x) is given in [KitMans, Theorem 2]:

E_{123}^{k(k−1)...1}(x) = \frac{e^{x/2} ∫_{0}^{x} e^{−t/2}t^{k−1} sin(Ψ_{6}(t)) dt}{(k − 1)! cos(Ψ_{6}(x))},

and E_{123}^{k(k−1)...1,12} is given in this theorem above.

Proof.

(iii) Beginning with k(k − 1) … 1 and ending with 12 … ℓ: If ℓ ≥ 3 then the pattern 12 … ℓ does not avoid 123, thus the statement is true. If ℓ = 1, the statement is true according to [Kit3, Theorem 8] and the observation that if k = 1 then this formula gives the expression

\frac{\sqrt{3}}{2}e^{x/2} sec(Ψ_{6}(x)) − 1,

which is true according to [ElizNoy, Theorem 4.1] and the assumption that the empty permutation does not begin or end with the pattern p = 1. So, we need only to consider the case ℓ = 2.

Let P_{k}(n) denote the number of n-permutations that avoid the pattern 123, begin with a decreasing subword of length k and end with the pattern 12. Also, let R_{k}(n) denote the number of n-permutations that avoid the pattern 123 and begin with a decreasing subword of length k. Let π = π_{1}1π_{2} be an (n + 1)-permutation that avoids the pattern 123, begins with the pattern k(k − 1) … 1 and ends with the pattern 12. We observe that π_{1} avoids 123 and begins with k(k − 1) … 1; π_{2} ends with the pattern 12 and |π_{2}| > 0 since otherwise π cannot end with the pattern 12; if |π_{2}| > 1 then π_{2} must begin with the pattern 21 since otherwise we have an occurrence of the pattern 123 beginning from the letter 1. If |π_{1}| = i then the letters of π_{1} can be chosen in \binom{n}{i} ways. So, there are at least

∑_{i≥0} \binom{n}{i}R_{k}(i)P_{2}(n − i) + nR_{k}(n − 1)

(n + 1)-permutations with the good properties, where the first term corresponds to the case |π_{2}| > 1 and the second term to the case |π_{2}| = 1. By this formula, we do not count the permutations having |π_{1}| = k − 1, although in this case π begins with the pattern k(k − 1) … 1. So, we can choose the letters of π_{1} in \binom{n}{k−1} ways, and according to whether |π_{2}| ≥ 1 or |π_{2}| = 1, we have two terms:

\binom{n}{k − 1}P_{2}(n − k + 1) + kδ_{n,k},

where δ_{n,k} is the Kronecker delta. Thus,

\begin{matrix}P_{k}(n + 1) \\ = ∑_{i≥0} \binom{n}{i}R_{k}(i)P_{2}(n − i) + nR_{k}(n − 1) + \binom{n}{k−1}P_{2}(n − k + 1) + kδ_{n,k}. \end{matrix}

After multiplying both sides of the last equality with x^{n}/n! and summing over n, we have

(11) \frac{d}{dx}E_{123}^{k(k−1)...1,12}(x) = (E_{123}^{21,12}(x) + x) (E_{123}^{k(k−1)...1}(x) + \frac{x^{k−1}}{(k − 1)!}) ,

with the initial condition E_{123}^{k(k−1)...1,12}(0) = 0. Since

E_{123}^{k(k−1)...1}(x) = E_{123}^{k(k−1)...1,1}(x)
= \frac{e^{x/2}}{(k−1)!} sec(Ψ_{6}(x)) ∫_{0}^{x} e^{−t/2}t^{k−1} sin(Ψ_{3}(t)) dt,

to solve (11), we only need to know E_{123}^{21,12}(x). To find it, we set k = 2 into (11) and solve this equation. For an example how to solve such an equation, we refer to Table 1(K1-K3). We get

E_{123}^{21,12}(x) = −x + sec(Ψ_{6}(x))e^{−x/2} ∫_{0}^{x} e^{t/2} cos(Ψ_{6}(t)) dt.

Now, we put the formula for E_{123}^{21,12}(x) into (11) and solve this differential equation to get the desired result.

(ii) Beginning with 12 … k and ending with ℓ(ℓ − 1) … 1: By the reverse and complement operations, to avoid 123, begin with the pattern 12 … k and end with the pattern ℓ(ℓ − 1) … 1 is the same as to avoid 123, begin with the pattern ℓ(ℓ − 1) … 1 and end with the pattern 12 … k, so we can apply the results of the previous case.

(i) Beginning with 12 … k and ending with 12 … ℓ: The statement is obvious if k ≥ 3 or ℓ ≥ 3. If k = 1 and ℓ = 1 then the statement is true according to [ElizNoy, Theorem 4.1] (but we need to subtract 1, since by our assumption the empty permutation does not begin or end with the pattern p = 1). If ℓ = 1 and k = 2, the statement is true according [Kit3, Theorem 9]. If k = 1 and ℓ = 2, we apply the reverse and complement operations, and use again [Kit3, Theorem 9]. So, we only need to consider the case k = 2 and ℓ = 2. It is easy to see that

E_{123}^{12,12}(x) = E_{123}^{1,12}(x) − E_{123}^{21,12}(x),

and from the previous cases

E_{123}^{1,12}(x) = \frac{\sqrt{3}}{2}e^{x/2} sec(Ψ_{6}(x)) − \frac{1}{2} − \frac{\sqrt{3}}{2} tan(Ψ_{6}(x)),

and

E_{123}^{21,12}(x) = −x + sec(Ψ_{6}(x)) (sin(Ψ_{3}(x)) − \frac{\sqrt{3}}{2}e^{−x/2}) .

(iv) Beginning with k(k − 1) … 1 and ending with ℓ(ℓ − 1) … 1: If ℓ = 1, the statement is trivial. If k = 1, we get the statement by using the reverse and complement operations. For the case ℓ = 2, we observe that the number of n-permutations that avoid the pattern 123, begin with the pattern k(k − 1) … 1 and end with the pattern 21 is equal to the number of n-permutation that avoid 123 and begin with the pattern k(k−1) … 1 minus the number of n-permutations that avoid the pattern 123, begin with the pattern k(k − 1) … 1 and end with the pattern 12. Suppose now that k ≥ 2 and ℓ ≥ 3 and an (n+1)-permutation π avoids 123, begins with k(k−1) … 1 and ends with ℓ(ℓ − 1) … 1. It is easy to see that the letter (n + 1) can be either in the first position, or in the position i, where (k + 1) ≤ i ≤ (n − ℓ), or in the position (n − ℓ + 1). In the first of these cases, obviously we have N_{123}^{(k−1)...1,ℓ(ℓ−1)...1}(n) permutations. In the second case, we choose the letters of π to the left of (n + 1) in \binom{n}{i−1} ways. These letters must form a permutation that avoids 123, begins with the pattern k(k−1) … 1, and ends with the pattern 21 (if the last condition does not hold, the letter (n + 1) and two letters to the left of it form a 123-pattern. At the same time, the letters to the right of (n + 1) form a permutation that avoids 123 and ends with the pattern ℓ(ℓ − 1) … 1. In the third case, we can choose the letters to the right of (n + 1) in \binom{n}{ℓ−1} ways, rearrange them into the decreasing order, and form from the letters to the left of (n + 1) a permutation that avoids 123, begins with the pattern k(k − 1) … 1 and ends with the pattern 21 (by the same reasons as above) in N_{123}^{k(k−1)...1,21}(n − ℓ + 1) ways. Thus,

N_{123}^{k(k−1)...1,ℓ(ℓ−1)...1}(n + 1)

= N_{123}^{(k−1)...1,ℓ(ℓ−1)...1}(n) + ∑_{i=0}^{n} \binom{n}{i}N_{123}^{k(k−1)...1,21}(i)N_{123}^{ℓ(ℓ−1)...1}(n − i)

+\binom{n}{ℓ−1}N_{123}^{k(k−1)...1,21}(n − ℓ + 1),

where we observed, that to avoid 123 and end with ℓ(ℓ − 1) … 1 is the same as to avoid 123 and begin with ℓ(ℓ − 1) … 1 using the reverse and complement. Now, we multiply both sides of the equality by x^{n}/n! and sum over n to get the desired result. □

7. Avoiding a pattern x-yz, beginning and ending with certain patterns simultaneously

Proposition 17. We have

(i) E_{1-32}^{12...k,1}(x) = E_{1-32}^{12...k}(x) = \{ \begin{matrix}e^{e^{x}} ∫_{0}^{x} e^{−e^{t}} ∑_{n≥k−1} \frac{t^{n}}{n!} dt, & if k ≥ 2 \\ e^{e^{x}−1}, & if k = 1 \end{matrix} .

For ℓ ≥ 2, E_{1-32}^{12...k,12...ℓ}(x) satisfies

\frac{∂}{∂x}E_{1-32}^{12...k,12...ℓ}(x) = (e^{x} − ∑_{i=0}^{ℓ−2} \frac{x^{i}}{i!} ) E_{1-32}^{12...k}(x) + e^{x}x^{max(ℓ,k)−1}.

(ii) E_{1-32}^{12...k,ℓ(ℓ−1)...1}(x) satisfies

\frac{∂^{ℓ−1}}{∂x^{ℓ−1}} E_{1-32}^{12...k,ℓ(ℓ−1)...1}(x) = \{ \begin{matrix}e^{e^{x}} ∫_{0}^{x} e^{−e^{t}} ∑_{n≥k−1} \frac{t^{n}}{n!} dt, & if k ≥ 2, \\ e^{e^{x}−1}, & if k = 1. \end{matrix}

(iii) the generating functions E_{1-32}^{k(k−1)...1,1}(x) and E_{1-32}^{k(k−1)...1}(x) are given by

\{ \begin{matrix}(e^{e^{x}}/(k − 1)!) ∫_{0}^{x} t^{k−1}e^{−e^{t}+t} dt, & if k ≥ 2 \\ e^{e^{x}−1}, & if k = 1 \end{matrix} .

For ℓ ≥ 2, E_{1-32}^{k(k−1)...1,12...ℓ}(x) satisfies

\begin{matrix}\frac{∂}{∂x}E_{1-32}^{k(k−1)...1,12...ℓ}(x) \\ = (e^{x} − ∑_{i=0}^{ℓ−2} \frac{x^{i}}{i!} ) E_{1-32}^{k(k−1)...1}(x) + (e^{x} − ∑_{i=0}^{ℓ−2} \frac{x^{i}}{i!} ) \frac{x^{k−1}}{(k−1)!}. \end{matrix}

(iv) E_{1-32}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) satisfies

\begin{aligned}\frac{∂^{ℓ−1}}{∂x^{ℓ−1}} & (E_{1-32}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) − \frac{x^{max(k,ℓ)}−x^{k+ℓ−1}}{1−x} ) \\ & = \{ \begin{matrix}\frac{e^{e^{x}}}{(k−1)!} ∫_{0}^{x} t^{k−1}e^{−e^{t}+t} dt, & if k ≥ 2, \\ e^{e^{x}−1}, & if k = 1. \end{matrix} \end{aligned}

Proof.

(ii) Beginning with 12 … k and ending with ℓ(ℓ − 1) … 1: If ℓ = 1 then the result follows from [KitMans, Proposition 5], since to avoid 1-32 and begin with 12 … k is the same as to avoid 3-12 and begin with k(k −1) … 1. Suppose now that ℓ ≥ 2 and a permutation π avoids the pattern 1-32, begins with the pattern 12 … k and ends with the pattern ℓ(ℓ−1) … 1. Since ℓ ≥ 2, we have that the letter 1 must be in the rightmost position since otherwise, this letter and two rightmost letters of π form the pattern 1-32, which is forbidden. Thus,

N_{1-32}^{12...k,ℓ(ℓ−1)...1}(n) = N_{1-32}^{12...k,(ℓ−1)(ℓ−2)...1}(n − 1) = ⋯ = N_{1-32}^{12...k,1}(n − ℓ + 1).

Multiplying both sides of the equality

N_{1-32}^{12...k,ℓ(ℓ−1)...1}(n) = N_{1-32}^{12...k,1}(n − ℓ + 1)

by x^{n−ℓ+1}/(n − ℓ + 1)! and summing over n, we get

\frac{∂^{ℓ−1}}{∂x^{ℓ−1}} E_{1-32}^{12...k,ℓ(ℓ−1)...1}(x) = E_{1-32}^{12...k}(x),

where E_{1-32}^{12...k}(x) is given in [KitMans, Proposition 5], since to avoid 1-32 and begin with 12 … k is the same as to avoid 3-12 and begin with k(k −1) … 1.

(iv) Beginning with k(k − 1) … 1 and ending with ℓ(ℓ − 1) … 1: We use the same arguments as those given under consideration of the previous case, but instead of [KitMans, Proposition 5] we use [KitMans, Proposition 4]. However, we observe, that when we use the argument

\begin{matrix}N_{1-32}^{k(k−1)...1,ℓ(ℓ−1)...1}(n) \\ = N_{1-32}^{k(k−1)...1,(ℓ−1)(ℓ−2)...1}(n − 1) = ⋯ = N_{1-32}^{k(k−1)...1,1}(n − ℓ + 1) \end{matrix}

for k, ℓ ≥ 2, we do not count the decreasing permutations of length max(k, ℓ), max(k, ℓ)+1, …, k +ℓ−2, since in this case, the patterns k(k −1) … 1 and ℓ(ℓ − 1) … 1 overlap in more than one letter, which causes the observation. So, we need to consider additionally the term

x^{max(k,ℓ)} + x^{max(k,ℓ)+1} + ⋯ + x^{k+ℓ−2} = \frac{x^{max(k,ℓ)} − x^{k+ℓ−1}}{1 − x} ,

which vanishes if k = 1 or ℓ = 1.

(i) Beginning with 12 … k and ending with 12 … ℓ: The only interesting case here is the case k ≥ 2 and ℓ ≥ 2. Using the reverse and complement, instead of considering avoiding 1-32, beginning with 12 … k and ending with 12 … ℓ, we consider avoiding 21-3, beginning with 12 … ℓ and ending with 12 … k. Suppose an n-permutation π satisfies all the conditions. We observe, that the letter n can be in the position i, where ℓ ≤ i ≤ n − k. Also, n can be in the rightmost position if n ≥ max(ℓ, k). In any case, the letters of π to the left of n must be in increasing order, since otherwise we have an occurrence of the pattern 21-3. This means that in the second case we have the only one permutation. In the first case, the letters of π to the right of n must avoid 21-3 and end with the pattern 12 … k. The number of such permutations, using the reverse and complement, is given by N_{1-32}^{12...k}(n − i). Thus, for n ≥ max(ℓ, k),

N_{21-3}^{12...ℓ,12...k}(n) = ∑_{i=ℓ}^{n−k} \binom{n − 1}{i − 1}N_{1-32}^{12...k}(n − i) + 1.

This gives

N_{21-3}^{12...ℓ,12...k}(n) = ∑_{i=1}^{n} \binom{n − 1}{i − 1}N_{1-32}^{12...k}(n−i)−∑_{i=1}^{ℓ−1} \binom{n − 1}{i − 1}N_{1-32}^{12...k}(n−i)+1,

which leads to the desired result after multiplying both sides of the last equality by x^{n}/n! and summing over n.

(iii) Beginning with k(k −1) … 1 and ending with 12 … ℓ: The only interesting case here is the case k ≥ 2 and ℓ ≥ 2. Using the reverse and complement, instead of considering avoiding 1-32, beginning with k(k − 1) … 1 and ending with 12 … ℓ, we consider avoiding 21-3, beginning with 12 … ℓ and ending with k(k − 1) … 1. Suppose an n-permutation π satisfies all the conditions. We observe, that the letter n can only be in the position i, where ℓ ≤ i ≤ n − k, or in position (n − k + 1) (in the case n ≥ k + ℓ − 1). In the first case, it is easy to see that the letters of π to the left of n must be in the increasing order, and the letters of π to the right of n must avoid 21-3 and end with the pattern k(k − 1) … 1. Using the reverse and complement, the total number of permutations counted in the first case is ∑_{i=ℓ}^{n−k} \binom{n−1}{i−1}N_{1-32}^{k(k−1)...1}(n − i). In the second case, the letters to the left of n are in increasing order, whereas the letters to the right of n are in decreasing order. The number of such permutations is \binom{n−1}{k−1}, which is the number of ways to choose the last k − 1 letters. Thus,

N_{21-3}^{12...ℓ,k(k−1)...1}(n) = ∑_{i=ℓ}^{n−k} \binom{n − 1}{i − 1}N_{1-32}^{k(k−1)...1}(n − i) + \binom{n − 1}{k − 1}.

Multiplying both parts of the equality by x^{n−1}/(n − 1)! and summing over n, we get

\begin{matrix}\frac{∂}{∂x} E_{21-3}^{12...ℓ,k(k−1)...1}(x) = ∑_{n≥k+ℓ} \binom{n − 1}{k − 1} \frac{x^{n−1}}{(n − 1)!} + \\ ∑_{n≥0} (∑_{i=1}^{n−1} \binom{n − 1}{i − 1}N_{1-32}^{k(k−1)...1}(n − i) − ∑_{i=1}^{ℓ−1} \binom{n − 1}{i − 1}N_{1-32}^{k(k−1)...1}(n − i)) \frac{x^{n−1}}{(n − 1)!} , \end{matrix}

which leads to the desired result. □

Proposition 18. Let k, ℓ ≥ 1 and m = max(k, ℓ). We have (i) G_{2-13}^{12...k,12...ℓ}(x) = x^{k+ℓ−1}C^{k+1}(x) + \frac{x^{m}−x^{k+ℓ−1}}{1−x}.

(ii) G_{2-13}^{k(k−1)...1,12...ℓ}(x) = x^{k+ℓ−1}C^{2}(x).

(iii) G_{2-13}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) = x^{k+ℓ−1}C^{ℓ+1}(x) + \frac{x^{m}−x^{k+ℓ−1}}{1−x}.

(iv) the generating function G_{2-13}(x, y, z) = ∑_{k,ℓ≥0} G_{2-13}^{12...k,ℓ(ℓ−1)...1}(x)y^{k}z^{ℓ}

for the sequence {G_{2-13}^{12...k,ℓ(ℓ−1)...1}(x)}_{k,ℓ≥0} (where k and ℓ go through all natural numbers) is

\frac{1}{1 − x(y + z)} (x(y + z + yz) + \frac{C(x) − 1}{(1 − xyC(x))(1 − xzC(x))}) .

Proof. By [Claes, Lemma 2], to avoid the pattern 2-13 is the same as to avoid the pattern 2-1-3. Thus we can apply the results of Proposition 11. □

Proposition 19. We have

(i) E_{1-23}^{12...k,12...ℓ}(x) = \{ \begin{matrix}0, & if k ≥ 3 or ℓ ≥ 3, \\ E_{1-23}^{12...k}(x), & if ℓ = 1, \\ E_{12-3}^{12...ℓ}(x), & if k = 1, \\ ∫_{0}^{x} tE_{12-3}^{12}(t) dt + \frac{x^{2}}{2!} , & if k = 2 and ℓ = 2, \end{matrix}

where E_{12-3}^{12...k}(x) and E_{1-23}^{12...k}(x) are given by [KitMans, Proposition 10] and [KitMans, Proposition 6] respectively:

E_{12-3}^{12...k}(x) = \{ \begin{matrix}0, & if k ≥ 3, \\ x^{2} ∑_{j=0}^{k} \frac{1}{1 − jx} ∑_{d≥0} \frac{x^{d}}{∏_{s=0}^{d}(1 − sx)}, & if k = 2, \\ ∑_{d≥0} \frac{x^{d}}{∏_{s=0}^{d}(1 − sx)}, & if k = 1; \end{matrix}

E_{1-23}^{12...k}(x) = E_{3−21}^{k(k−1)...1}(x) = \{ \begin{matrix}0, & if k ≥ 3, \\ e^{e^{x}} ∫_{0}^{x} e^{−e^{t}}(e^{t} − 1) dt, & if k = 2, \\ e^{e^{x}−1}, & if k = 1. \end{matrix}

(ii) N_{1-23}^{12...k,ℓ(ℓ−1)...1}(n) =

0,  if k ≥ 3,
0,  if k = 2 and n ≤ ℓ,

1 + N_{1-23}^{12,(ℓ−1)(ℓ−2)...1}(n − 1)

+ ∑_{j=ℓ+1}^{n−2} \binom{n − 1}{j − 1}N_{1-23}^{12}(n − j), if k = 2 and n ≥ ℓ + 1,
N_{12-3}^{ℓ(ℓ−1)...1}(n),  if k = 1,

where the numbers N_{12-3}^{ℓ(ℓ−1)...1}(n) are given in [KitMans, Proposition 9], and the numbers N_{1-23}^{12}(n) are given by expanding the exponential generating functions in [KitMans, Proposition 6].

(iii) the exponential generating function E_{1-23}^{k(k−1)...1,12...ℓ}(x) is given by

\{ \begin{matrix}0, & if ℓ ≥ 3 \\ \frac{1}{(k−1)!} ∫_{0}^{x} ∫_{0}^{t} tm^{k−1}e^{e^{t}−e^{m}+m} dmdt + \frac{kx^{k+1}}{(k+1)!}, & if ℓ = 2 \\ (e^{e^{x}}/(k − 1)!) ∫_{0}^{x} t^{k−1}e^{−e^{t}+t} dt, & if ℓ = 1 \end{matrix} ,

where E_{1-23}^{k(k−1)...1,1}(n) = E_{1-23}^{k(k−1)...1}(n) is given by [KitMans, Proposition 4], and N_{1-23}^{1,ℓ(ℓ−1)...1}(n) = N_{12-3}^{ℓ(ℓ−1)...1}(n) is given by [KitMans, Proposition 9];

(iv) For k ≥ 2 and ℓ ≥ 2, E_{1-23}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) satisfies

\begin{matrix}\frac{∂}{∂x}E_{1-23}^{k(k−1)...1,ℓ(ℓ−1)...1}(x) \\ = E_{1-23}^{k(k−1)...1,(ℓ−1)...1}(x) + (e^{x} − ∑_{i=0}^{ℓ−1} \frac{x^{i}}{i!} ) (E_{1-23}^{k(k−1)...1}(x) + \frac{x^{k}}{(k−1)!}) . \end{matrix}

Proof.

(iii) Beginning with k(k − 1) … 1 and ending with 12 … ℓ: If ℓ ≥ 3 then E_{1-23}^{k(k−1)...1,12...ℓ}(x) = 0, since in this case the pattern 12 … ℓ does not avoid 1-23. If ℓ = 1 then we use [KitMans, Proposition 4], since in this case the only restrictions to the permutations are avoiding 1-23 and beginning with the pattern k(k − 1) … 1. Suppose now that ℓ = 2 and an (n + 1)- permutation π avoids 1-23, begins with k(k − 1) … 1 and ends with the pattern 12. The letter 1 must be in next to the rightmost position, since otherwise this letter and two rightmost letters form the pattern 1-23. We can choose the rightmost letter of π in n ways, and the letters to the left of 1 must form a 1-23-avoiding permutation that begins with k(k − 1) … 1. Besides, if n = k, and the k − 1 letters to the left of 1 are in the decreasing order, we get n extra permutations that satisfy our restrictions. Thus,

N_{1-23}^{k(k−1)...1,12}(n + 1) = nN_{1-23}^{k(k−1)...1}(n) + nδ_{n,k},

where δ_{n,k} is the Kronecker delta. Multiplying both sides of the equality by x^{n}/n! and summing over n we get

E_{1-23}^{k(k−1)...1,12}(x) = ∫_{0}^{x} tE_{1-23}^{k(k−1)...1}(t) dt + \frac{kx^{k+1}}{(k + 1)!}.

Using the formula for E_{1-23}^{k(k−1)...1}(t) in [KitMans, Proposition 4], we get the desired result.

(i) Beginning with 12 … k and ending with 12 … ℓ: The first three cases are easy to prove in the same manner as we do in the proves of previous propositions. The only interesting case is when k = 2 and ℓ = 2. Using the reverse and complement operations, instead of considering avoiding 1-23, beginning with 12 and ending with 12, we consider avoiding 12-3, beginning with 12 and ending with 12, which we find to be more easy. Suppose an (n + 1)-permutation π satisfies all the restrictions. It is easy to see that |π| ≠ 1 and |π| ≠ 3, as well as if |π| = 2 (that is n = 1) then π must be 12. Suppose |π| ≥ 4. Since π begins with the pattern 12, it is impossible for the letter (n + 1) to be somewhere to the right of the second letter of π or to be the leftmost letter. Thus, (n + 1) must be in the second position. We can choose the leftmost letter of π in n ways, since any choice of this letter will not lead to an occurrence of the pattern 12 − 3 beginning with two leftmost letters. If π = a(n + 1)π′ then π′ must avoid 12-3 and end with the pattern 12. The number of such permutations, using the reverse and complement, is given by N_{1-23}^{12}(n − 1). Thus,

N_{12-3}^{12,12}(n + 1) = nN_{1-23}^{12}(n − 1).

Multiplying both sides of the equality by x^{n}/n! and summing over all n, we get

(E_{12-3}^{12,12}(x))′ = xE_{1-23}^{12}(x) + x,

where the term x corresponds to the permutation 12. We have the desired result by integrating both sides of the last equality.

(ii) Beginning with 12 … k and ending with ℓ(ℓ − 1) … 1: All the cases but k = 2 and n ≥ ℓ + 1 are easy to prove. Let us consider this case. Using the reverse and complement operations, instead of considering avoiding 1-23, beginning with 12 and ending with ℓ(ℓ − 1) … 1, we consider avoiding 12-3, beginning with ℓ(ℓ − 1) … 1 and ending with 12, which we find to be easier. Let an n-permutation π satisfy all the conditions. We observe, that the letter n is either in the first position, or in position j, where k+1 ≤ j ≤ n−2, or in the last position. Obviously, in the first of these cases the number of “good” permutations is given by N_{12-3}^{(ℓ−1)(ℓ−2)...1,12}(n − 1), which is equivalent to N_{1-23}^{12,(ℓ−1)(ℓ−2)...1}(n − 1) by using the reverse and complement. In the second case, we choose the letters to the left of n in \binom{n−1}{j−1} ways, rearrange them to the decreasing order (we do it since otherwise we have an occurrence of the pattern 12-3 having the letter n). After that, the letters to the right of n must form a permutation that avoid 12-3 and end with the pattern 12. Using the reverse and complement, there are N_{1-23}^{12}(n − j) such permutations. So, totally, in the second case there are ∑_{j=ℓ+1}^{n−2} \binom{n−1}{j−1}N_{1-23}^{12}(n−j) permutations. Finally, if n is at the last position, we have the only one such permutation, since the other letters must be in the decreasing order.

(iv) Beginning with k(k −1) … 1 and ending with ℓ(ℓ−1) … 1: The only interesting case here is the case k ≥ 2 and ℓ ≥ 2. Using the reverse and complement operations, instead of considering avoiding 1-23, beginning with k(k − 1) … 1 and ending with ℓ(ℓ − 1) … 1, we consider avoiding 12-3, beginning with ℓ(ℓ − 1) … 1 and ending with k(k − 1) … 1, which we find to be more easy. Let an n-permutation π satisfy all the conditions. We observe, that the letter n is either in the first position, or in position j, where ℓ + 1 ≤ j ≤ n − k, or in the last position n − k + 1. We proceed as in the previous case to get the following

\begin{matrix}N_{12-3}^{ℓ(ℓ−1)...1,k(k−1)...1} \\ = N_{12-3}^{(ℓ−1)...1,k(k−1)...1} + ∑_{i=ℓ+1}^{n−k} \binom{n − 1}{i − 1}N_{1-23}^{k(k−1)...1}(n − i) + \binom{n − 1}{k − 1}, \end{matrix}

where three terms in the right-hand side correspond to the three cases described above. We now multiply both sides of the equality by x^{n}/n!, sum over n and observe the following detail. We cannot write instead of i = ℓ+1 (in the sum above) i = 1 as we did in most of the cases above, since, for instance, the case i = 1 do not necessarily make the term of summation equal 0 as it was before. Thus, instead of the factor e^{x}, we have the factor

(e^{x} − ∑_{i=0}^{ℓ−1} \frac{x^{i}}{i!} ) .

□

8. Avoiding a pattern xy-z, beginning and ending with certain patterns simultaneously

To obtain results for the number of permutations that avoid the pattern xy − z, begin with the pattern p and end with the pattern r, one can apply the results from Section 7 and subsequently together the composition of the reverse and complement operations.

9. Further results

In this section, we propose two directions of generalization of the results from the previous sections. The first one is a consideration of avoiding more than one pattern, beginning with some pattern and ending with another pattern. For example, suppose that v = 12-3, w = 21-3, p = 12 … k, q = 12 … ℓ, and E_{v,w}^{p,q}(x) denotes the exponential generating function for the number of permutations that avoid the patterns v and w simultaneously, begin with the pattern p and end with the pattern q. It is easy to see that if k ≥ 3 or ℓ ≥ 3 then E_{12-3,21-3}^{12...k,12...ℓ}(x) = 0. For the other k and ℓ, one can prove the following theorem:

Theorem 20. We have (i) E_{12-3,21-3}^{1,1}(x) = e^{x+x^{2}/2} − 1.

(ii) E_{12-3,21-3}^{1,12}(x) = e^{x+x^{2}/2} (1 − ∫_{0}^{x} e^{−t−t^{2}/2}dt) − 1.

(iii) E_{12-3,21-3}^{12,1}(x) = ∫_{0}^{x} te^{t+t^{2}/2}dt.

(iv) E_{12-3,21-3}^{12,12}(x) = \frac{1}{2}x^{2} + ∫_{0}^{x} [e^{t+t^{2}/2} (1 − ∫_{0}^{t} e^{−r−r^{2}/2}dr) − 1] dt.

The second direction is a consideration of permutations in S_{n} containing a pattern v exactly r times, beginning with some pattern and ending with another pattern. For example, suppose that v = 12-3, r = 1, p = 1 … k, q = 1, and N_{v;r}^{p,q}(n) denotes the number of n-permutations that contain the pattern v exactly r times, begin with the pattern p, and end with the pattern q. It is easy to see that the only interesting case is 1 ≤ k ≤ 3, since otherwise N_{12-3;1}^{12...k,1}(n) = 0. Moreover, one can prove the following theorem:

Theorem 21. Let F_{n} denote the number of n-permutations containing 12-3 exactly once. Then, for all n ≥ 3,

\begin{matrix}N_{12-3;1}^{1,1}(n) = F_{n}N_{12-3;1}^{12,1}(n) = (n − 1)F_{n−1} + (n − 2)B_{n−2}, \\ N_{12-3;1}^{123,1}(n) = (n − 2)B_{n−3}, \end{matrix}

where B_{n} is the nth Bell number, and F_{n} is given by [ClaesMans2, Corollary 13].

Acknowledgments. The authors are grateful to the referees for the careful reading of the manuscript.

References

[BabStein] E. Babson, E. Steingrímsson: Generalized permutation patterns and a classification of the Mahonian statistics, Séminaire Lotharingien de Combinatoire, B44b:18pp, 2000.

[Bon] M. Bóna: Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps. J. Combin. Theory Ser. A 80 (1997), no. 2, 257–272.

[B] M. Bóna: The permutation classes equinumerous to the smooth class. Electron. J. Combin. 5 (1998), no. 1, Research Paper 31, 12 pp. (electronic).

[CW] T. Chow and J. West: Forbidden subsequences and Chebyshev polynomials. Discrete Math. 204 (1999), no. 1-3, 119–128.

[Claes] A. Claesson: Generalised Pattern Avoidance, European J. Combin. 22 (2001), 961-971.

[ClaesMans1] A. Claesson and T. Mansour: Enumerating Permutations Avoiding a Pair

of Babson-Steingrímsson Patterns, preprint CO/0107044. [ClaesMans2] A. Claesson and T. Mansour, Counting Occurrences of a Pattern of Type

(1,2) or (2,1) in Permutations, Advances in Applied Mathematics, to appear (2002).

[ElizNoy] S. Elizalde and M. Noy: Enumeration of Subwords in Permutations, Proceedings of FPSAC 2001.

[Ent] R. Entringer: A Combinatorial Interpretation of the Euler and Bernoulli Numbers, Nieuw. Arch. Wisk. 14 (1966), 241–246.

[Kit1] S. Kitaev: Multi-avoidance of generalised patterns, Discrete Math. 260 (2003), 89–100.

[Kit2] S. Kitaev: Partially ordered generalized patterns, Discrete Math., to appear (2002).

[Kit3] S. Kitaev: Generalized pattern avoidance, Séminaire Lotharingien de Combinatoire 48 (2003), Article B48e, 19 pp.

[KitMans] S. Kitaev and T. Mansour: Simultaneous avoidance of generalized patterns, Ars Combinatorica, to appear, preprint math.CO/0205182.

[Knuth] D. E. Knuth: The Art of Computer Programming, 2nd ed. Addison Wesley, Reading, MA, (1973).

[Kr] C. Krattenthaler: Permutations with restricted patterns and Dyck paths, Adv. in Appl. Math. 27 (2001), 510–530.

[K] D. Kremer: Permutations with forbidden subsequnces and a generalized Schröder number, Discrete Math. 218 (2000), 121–130.

[Loth] M. Lothaire: Combinatorics on Words, Encyclopedia of Mathematics and its Applications, 17, Addison-Wesley Publishing Co., Reading, Mass. (1983).

[Mans1] T. Mansour: Continued fractions and generalized patterns, European Journal of Combinatorics 23:3 (2002), 329–344.

[Mans2] T. Mansour: Continued fractions, statistics, and generalized patterns, to appear in Ars Combinatorica (2002), preprint CO/0110040.

[Mans3] T. Mansour: Restricted 1-3-2 permutations and generalized patterns, Annals of Combinatorics 6 (2002), 65–76.

[MV1] T. Mansour and A. Vainshtein: Restricted permutations, continued fractions, and Chebyshev polynomials, Electron. J. Combin. 7 (2000) no. 1, Research Paper 17, 9 pp. (electronic).

[MV2] T. Mansour and A. Vainshtein: Restricted 132-avoiding permutations, Adv. in Appl. Math. 126 (2001), no. 3, 258–269.

[MV3] T. Mansour and A. Vainshtein: Layered restrictions and Chebyshev polynomials, Annals of Combinatorics 5 (2001), 451–458.

[MV4] T. Mansour and A. Vainshtein: Restricted permutations and Chebyshev polyonomials, Séminaire Lotharingien de Combinatoire 47 (2002), Article B47c.

[R] A. Robertson: Permutations containing and avoiding 123 and 132 patterns, Discrete Math. Theor. Comput. Sci. 3 (1999), no. 4, 151–154 (electronic).

[RWZ] A. Robertson, H. Wilf, and D. Zeilberger: Permutation patterns and continued fractions, Electron. J. Combin. 6 (1999), no. 1, Research Paper 38, 6 pp. (electronic).

[SloPlo] N. J. A. Sloane and S. Plouffe: The Encyclopedia of Integer Sequences, Academic Press, (1995).

[Stan] R. Stanley: Enumerative Combinatorics, Vol. 1, Cambridge University Press, (1997).

[SchSim] R. Simion, F. Schmidt: Restricted permutations, European J. Combin. 6 (1985), no. 4, 383–406.

[W] J. West: Generating trees and forbidden subsequences, Discrete Math. 157 (1996), 363–372.

Matematik, Chalmers tekniska högskola och Göteborgs universitet, 412 96 Göteborg, Sweden

   E-mail address: kitaev@math.chalmers.se

Department of mathematics, Chalmers university of technology, 412 96 Göteborg, Sweden

   E-mail address: toufik@math.chalmers.se