Séminaire Lotharingien de Combinatoire 47 (2002), Article B47c

RESTRICTED PERMUTATIONS AND CHEBYSHEV POLYNOMIALS

T. MANSOUR^{∗} AND A. VAINSHTEIN^{†}

∗ LABRI, Université Bordeaux 351 cours de la Libération, 33405 Talence Cedex, France † Department of Mathematics and Department of Computer Science University of Haifa, Haifa, Israel 31905

              toufik@labri.fr, alek@mathcs.haifa.ac.il

Abstract. We study generating functions for the number of permutations in 𝔖_{n} subject to two restrictions. One of the restrictions belongs to 𝔖_{3}, while the other belongs to 𝔖_{k}. It turns out that in a large variety of cases the answer can be expressed via Chebyshev polynomials of the second kind.

Contents:

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1. Pattern avoidance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2. Chebyshev polynomials of the second kind . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Transfer matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1. Generating trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2. Dyck paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3. Continued fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4. Block decompositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

5. Counting 132-restricted permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.1. Avoiding 132 and another pattern. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.2. Avoiding 132 and containing another pattern exactly once . . . . . . . 10 5.3. Containing 132 exactly once and avoiding another pattern . . . . . . . 12 5.4. Containing 132 and another pattern exactly once . . . . . . . . . . . . . . . . . 13

2000 Mathematics Subject Classification. Primary 05A05, 05A15; Secondary 30B70, 42C05.

5.5. Generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

6. Counting 321-restricted permutations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1. Introduction

1.1. Pattern avoidance. Let π = (π_{1}, …, π_{n}) ∈ 𝔖_{n} and τ ∈ 𝔖_{k} be two permutations. An occurrence of τ in π is a subsequence π′ = (π_{i_{1}}, …, π_{i_{k}}) such that 1 ⩽ i_{1} < i_{2} < ⋯ < i_{k} ⩽ n and π′ is order-isomorphic to τ; in such a context τ is usually called a pattern. We say that π avoids τ, or is τ-avoiding, if there is no occurrence of τ in π. For example, let π = 83176254, and τ_{1} = 1234, τ_{2} = 1243, τ_{3} = 4213. Then it is easy to see that π avoids τ_{1}, contains exactly one occurrence of τ_{2}, namely, 1254, and contains six occurrences of τ_{3}, which are 8317, 8316, 8315, 8314, 8325, 8324.

The set of all τ-avoiding permutations in 𝔖_{n} is denoted by 𝔖_{n}(τ). For an arbitrary finite collection of patterns T, we say that π avoids T if π avoids any τ ∈ T; the corresponding subset of 𝔖_{n} is denoted by 𝔖_{n}(T). By F_{τ} and F_{T} we denote the corresponding (ordinary) generating functions F_{τ}(x) = ∑_{n=0}^{∞} |𝔖_{n}(τ)|x^{n} and F_{T} (x) = ∑_{n=0}^{∞} |𝔖_{n}(T)|x^{n}.

The following simple symmetry arguments allow to decrease the variety of different T ’s to be considered. Define the reversal and the complementation operations as follows: r(π_{1}, π_{2}, …, π_{n}) = (π_{n}, π_{n−1}, …, π_{1}), c(π_{1}, π_{2}, …, π_{n}) = (n + 1 − π_{1}, n + 1 − π_{2}, …, n + 1 − π_{n}). It is easy to see that the following four statements are equivalent:

(i) π avoids τ;

(ii) r(π) avoids r(τ);

(iii) c(π) avoids c(τ);

(iv) π^{−1} avoids τ^{−1}.

More generally, denote by G the group of transformations generated by r, c, and the usual group inverse operation (it is easy to see that G is isomorphic to the dihedral group D_{8}). The for any g ∈ G one has F_{T} (x) = F_{g(T)}(x).

The first paper devoted entirely to the study of permutations avoiding certain patterns (restricted permutations) appeared in 1985 (see [SS]). Currently there exist more than fifty papers on this subject.

1.2. Chebyshev polynomials of the second kind. Chebyshev polynomials of the second kind (in what follows just Chebyshev polynomials) are defined by

U_{r}(cos θ) = \frac{sin(r + 1)θ}{sin θ}

for r ⩾ 0. Evidently, U_{r}(x) is a polynomial of degree r in x with integer coefficients. For example, U_{0}(x) = 1, U_{1}(x) = 2x, U_{2}(x) = 4x^{2} −1, and in general, U_{r}(x) = 2xU_{r−1}(x)− U_{r−2}(x). Chebyshev polynomials were invented for the needs of approximation theory, but are also widely used in various other branches of mathematics, including algebra, combinatorics, and number theory (see [Ri]).

For k ⩾ 1 we define R_{k}(x) by

R_{k}(x) = \frac{2tU_{k−1}(t)}{U_{k}(t)}, t = \frac{1}{2\sqrt{x}}.

For example, R_{1}(x) = 1, R_{2}(x) = \frac{1}{1−x}, and R_{3}(x) = \frac{1−x}{1−2x}. It is easy to see that for any k, R_{k}(x) is rational in x. These rational functions arise in some of the results below.

1.3. Preliminaries. Apparently, for the first time the relation between restricted permutations and Chebyshev polynomials was discovered by Chow and West in [CW]. The main result of [CW] can be formulated as follows.

Theorem 1.1. ([CW, Th. 3.1]) Let T_{1} = {321, (2, 3, …, k, 1)}, T_{2} = {132, (1, 2, …, k)}, and T_{3} = {132, (2, 3, …, k, 1)}, then :

(i) F_{T_{1}}(x) = R_{k}(x);

(ii) F_{T_{2}}(x) = R_{k}(x);

(iii) F_{T_{3}}(x) = R_{k}(x).

The original proof is based on the use of transfer matrices (see Sec. 2 below). Several different proofs of various parts of this theorem appeared recently in [Kr, Th. 9] (part (i)), [MV1, Th. 3.1] and [Kr, Th. 2] (part (ii)), and [Kr, Th. 6] (part (iii)). They all are based on the use of continued fractions; the latter approach to restricted permutations was initiated in [RWZ] and developed in [MV1, JR, Kr]. In fact, there are two different ways to use continued fractions. One of them is more geometrical, and is based on the relation between continued fractions and Dyck paths discovered by Flajolet (see Sec. 3 below). Another is more analytical, and is based on the study of block decompositions (see Sec. 4 below).

In this paper we describe these three approaches, and present several ways to extend and generalize the above result. All our results deal with multiple (mainly, double) restrictions, of which one belongs to 𝔖_{3} and others to 𝔖_{k}. Some of the results have been published previously, and we state them here without a proof. Observe that modulo standard symmetry operations (complement, reversal, and inversion), there are only two nonequivalent patterns in 𝔖_{3}; we choose them to be 132 and 321.

For the sake of brevity, we denote by [k] the identity pattern (1, 2, …, k) ∈ 𝔖_{k}, and by [k, m] the two-layered pattern (m+1, m+2, …, k, 1, 2, …, m) ∈ 𝔖_{k}. In general, we say that τ ∈ 𝔖_{k} is a layered pattern if it can be represented as τ = (τ^{0}, τ^{1}, …, τ^{r}), where each of τ^{i} is a nonempty permutation of the form τ^{i} = (m_{i+1} +1, m_{i+1} +2, …, m_{i}) with k = m_{0} > m_{1} > ⋯ > m_{r} > m_{r+1} = 0; in this case we abbreviate τ by [m_{0}, …, m_{r}]. Observe that our definition slightly differs from the one used in [Bo, MV3]: their layered patterns are exactly the complements of our layered patterns.

The authors are grateful to C. Krattenthaler and to an anonymous referee for valuable comments that helped us to improve the presentation.

2. Transfer matrices

The main idea behind the transfer matrix approach can be described as follows (see [St1, Th. 4.7.2]). Consider a directed multigraph on n vertices v_{1}, …, v_{n}, and let A denote its weighted adjacency matrix, that is, a_{ij} is the number of edges directed from v_{i} to v_{j}. Then the generating function for the number of walks from v_{r} to v_{s} is given by

\frac{(−1)^{r+s} det(I − xA; r, s)}{det(I − xA)}  (2.1)

where I is the identity matrix and det(B; r, s) is the minor of B with the rth row and sth column deleted.

To apply this approach, one has to construct a bijection between the permutations in question and walks in an appropriate directed graph. We describe below two bijections of this type: the first based on generating trees, and the second based on Dyck paths.

2.1. Generating trees. Following [W], a generating tree is a rooted labeled tree with the property that if v_{1} and v_{2} are any two nodes with the same label and l is any label, then v_{1} and v_{2} have exactly the same number of children with the label l. To specify a generating tree it therefore suffices to specify:

(1) the label of the root, and

(2) a set of succession rules explaining how to derive from the label of a parent the labels of all of its children.

Example 2.1. (The complete binary tree) Since all the nodes in the complete binary tree are similar, it is enough to use only one label, which we choose to be 2. So we get the following description:

Root: (2)

Rule: (2) → (2)(2).

Example 2.2. (The Fibonacci tree) Here we have nodes of two different types, so we use two labels: 1 for a non-breeding pair and 2 for a breeding pair. We thus get:

Root: (1)

Rules: (1) → (2), (2) → (1)(2)

Given a generating tree, one assigns to it a directed graph whose vertices correspond to labels and edges from l_{i} to l_{j} correspond to the occurrences of l_{j} in the succession rule (l_{i}) → · · ·. The graphs corresponding to the above two examples are shown in Figure 1.

Figure 1. Directed graphs for the complete binary tree and the Fibonacci tree

Given a permutation τ, one defines a rooted tree as follows. The nodes on level n are precisely the elements of 𝔖_{n}(τ). The parent of a permutation π = (π_{1}, π_{2}, …, π_{n}) is the unique permutation π′ = (π_{1}, …, π_{j−1}, π_{j+1}, …, π_{n}) such that π_{j} = n. We denote the resulting tree by T (τ). Similarly, the tree corresponding to the set 𝔖_{n}(T) is denoted by T (T).

Chow and West [CW] proved that the succession rules for the tree T (123, (k−1, …, 1, k)) are

\begin{matrix}(l) → (2) ⋯ (l)(l + 1), & l < k − 1 \\ (k − 1) → (2) ⋯ (k − 1)(k − 1), \end{matrix}

and the label of the root is (2). The corresponding graph is shown in Figure 2.

Figure 2. The directed graph for T (123, (k − 1, …, 2, 1, k))

The corresponding transfer matrix is

A_{k} = [ \begin{matrix}1 & 1 & 0 & 0 & ⋯ & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & ⋯ & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & ⋯ & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ \\ 1 & 1 & 1 & 1 & ⋯ & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & ⋯ & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & ⋯ & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & ⋯ & 1 & 1 & 2 \end{matrix} ]

Besides, Chow and West proved that the graphs, and hence the transfer matrices for T (213, (k, 1, 2 …, k − 1)) and T (213, (1, 2, …, k)) are exactly the same (though the succession rules may vary). The number of permutations in 𝔖_{n}(T) (in all cases) is thus equal to the number of walks of length n starting from the vertex 2. However, since each vertex is connected to vertex 2 by exactly one edge, this number is equal to the number of walks of length n + 1 starting at vertex 2 and ending at the same vertex. The generating function for this number is given by (2.1) with A = A_{k}. It is proved in [CW] that the determinants in question satisfy linear recurrences of order two very similar to that for Chebyshev polynomials, which almost immediately yields Theorem 1.1, since T_{1} = c({123, (k − 1, …, 2, 1, k)}), T_{2} = r ∘ c({213, (1, 2, …, k)}), and T_{3} = r ∘ c({213, (k, 1, 2, …, , k − 1)}).

2.2. Dyck paths. A Dyck path is a path in the plane integer lattice Z^{2}, consisting of up-steps (1, 1) and down-steps (1, −1), which never passes below the x-axis.

Following [Kr], we define a bijection Φ between permutations in 𝔖_{n}(132) and Dyck paths from the origin to the point (2n, 0). Let π = (π_{1}, …, π_{n}) be a 132-avoiding permutation. We read the permutation π from left to right and successively generate a Dyck path. When π_{j} is read, then in the path we adjoint as many up-steps as necessary, followed by a down-step from height h_{j} + 1 to height h_{j} (measured from the x-axis), where h_{j} is the number of elements in π_{j+1}, π_{j+2}, …, π_{n} which are larger that π_{j}.

For example, let π = 534261. The first element to be read is 5. There is one element in 34261 which is larger than 5, therefore the path starts with two up-steps followed by a down-step, thus reaching height 1. Next 3 is read. There are 2 elements in 4261 which are larger than 3, therefore the path continues with two up-steps followed by a down-step, thus reaching height 2. Etc.

Conversely, given a Dyck path starting at the origin and returning to the x-axis, the obvious inverse of the bijection Φ produces a 132-avoiding permutation.

It is proved in [Kr] that the bijection Φ takes permutations in 𝔖_{n}(132, [k]) to Dyck paths that never pass above the line y = k − 1. Evidently, such paths correspond bijectively to walks of length 2n starting at vertex 0 in the graph shown in Figure 3.

Figure 3. The directed graph for Dyck paths in a strip

Using again (2.1) one gets Theorem 1.1(ii). A further study of the bijection Φ yields part (iii) of the same Theorem.

3. Continued fractions

The relation between restricted permutations and continued fractions was discovered by Robertson, Wilf, and Zeilberger in [RWZ]. The main result in [RWZ] can be formulated as follows. Let G_{τ}^{r}(x) be the generating function for the number of permutations in 𝔖_{n}(132) containing a pattern τ exactly r times.

Theorem 3.1. (Robertson, Wilf, and Zeilberger [RWZ, Th. 1])

∑_{r⩾0}G_{123}^{r}(x)z^{r} = \frac{1}{1 − \frac{xz^{\binom{0}{2}}}{1 − \frac{xz^{\binom{1}{2}}}{1 − \frac{xz^{\binom{2}{2}}}{...}}}}

in which the jth numerator is xz^{\binom{j−1}{2}}.

To prove this, let π be a permutation avoiding 132. Then each letter in π to the left of n must be greater than any letter to the right of n. Thus, if π = (π′, n, π′′) (where both π′ and π′′ must necessarily be 132-avoiding), then

(123)π = (123)π′ + (12)π′ + (123)π′′,

where (τ)π is the number of occurrences of τ in π. It follows that the generating function

F (x, y, z) = ∑_{π∈𝔖(132)}x^{(1)π}y^{(12)π}z^{(123)π}

satisfies the equation F (x, y, z) = 1 + xF (xy, yz, z)F (x, y, z). Equivalently,

F (x, y, z) = \frac{1}{1 − xF (xy, yz, z)},

and the theorem follows by induction after plugging in y = 1.

This result was generalized by Mansour and Vainshtein [MV1], by Krattenthaler [Kr], and by Jani and Rieper [JR] to the case of permutations containing the pattern [k] = 12 … k exactly r times. It turns out that

∑_{r≥0} G_{[k]}^{r}(x)z^{r} = \frac{1}{1 − \frac{xz^{d_{1}}}{1 − \frac{xz^{d_{2}}}{1 − \frac{xz^{d_{3}}}{…}}}} ,  (3.1)

where d_{j} = \binom{j−1}{k−1}.

The proof in [MV1] is a straightforward generalization of the above proof of Theorem 3.1. The proof in [Kr] is based on the bijection Φ between 132-avoiding permutations and Dyck paths described in the previous section and on the result of Flajolet [Fl, Th. 1] presenting the generating function for the Dyck paths in terms of continued fractions. The proof of [JR] is based on a bijection between 132-avoiding permutations and rooted ordered trees, which can be obtained from the bijection Φ via the standard bijection between rooted ordered trees and Dyck paths through a depth-first traversal of the trees (see [St2, Prop. 6.2.1, Cor. 6.2.3]). For further generalizations and interesting combinatorial applications see [BCS].

It was observed in [MV1] that R_{k}(x) is the kth approximant for the continued fraction

\frac{1}{1 − \frac{x}{1 − \frac{x}{1 − ...}}}

so (3.1) for r = 0 immediately gives Theorem 1.1(ii).

Paper [Kr] contains the description of a bijection Ψ between 123-avoiding permutations and Dyck paths. This bijection, combined with Roblet and Viennot’s continued fraction representation of the generating function for Dyck paths [RV, Prop. 1] gives the first part of Theorem 1.1.

4. Block decompositions

The core of this approach initiated by Mansour and Vainshtein [MV2] lies in the study of the structure of 132-avoiding permutations, and permutations containing a given number of occurrences of 132.

Let us start with the simplest case of 132-avoiding permutations. It was noticed in [MV2] that if α ∈ 𝔖_{n}(132) and α_{t} = n, then α = (α′, n, α′′) where α′ is a permutation of the numbers n−t+1, n−t+2, …, n, α′′ is a permutation of the numbers 1, 2, …, n−t, and both α′ and α′′ avoid 132. This representation is called the block decomposition of α, see Figure 4.

Figure 4. The block decomposition for α ∈ 𝔖_{n}(132)

The simple observation allows to formulate a general result concerning permutations avoiding 132 and an arbitrary pattern τ = (τ_{1}, …, τ_{k}) ∈ 𝔖_{k}(132). Recall that τ_{i} is said to be a right-to-left maximum if τ_{i} > τ_{j} for any j > i. Let m_{0} = k, m_{1}, …, m_{r} be the right-to-left maxima of τ written from left to right. Then τ can be represented as

τ = (τ^{0}, m_{0}, τ^{1}, m_{1}, …, τ^{r}, m_{r}),

where each of τ^{i} may be possibly empty, and all the entries of τ^{i} are greater than all the entries of τ^{i+1}. Define the ith prefix of τ by π^{i} = (τ^{0}, m_{0}, …, τ^{i}, m_{i}) for 1 ⩽ i ⩽ r and π^{0} = τ^{0}, π^{−1} = ∅. Besides, the ith suffix of τ is defined by σ^{i} = (τ^{i}, m_{i}, …, τ^{r}, m_{r}) for 0 ⩽ i ⩽ r and σ^{r+1} = ∅.

Theorem 4.1. ([MV2, Th. 1]) For any τ ∈ 𝔖_{k}(132), F_{τ}(x) is a rational function satisfying the relation

F_{τ}(x) = 1 + x ∑_{j=0}^{r}(F_{π^{j}}(x) − F_{π^{j−1}}(x))F_{σ^{j}}(x).

The proof is rather straightforward. Let α = (α′, n, α′′) be the block decomposition of α ∈ 𝔖_{n}(132). It is easy to see that α contains τ if and only if there exists i, 0 ⩽ i ⩽ r + 1, such that α′ contains π^{i−1} and α′′ contains σ^{i}. Therefore, α avoids τ if and only if there exists i, 0 ⩽ i ⩽ r, such that α′ avoids π^{i} and contains π^{i−1}, while α′′ avoids σ^{i}. We thus get the following relation:

f_{τ}(n) = ∑_{t=1}^{n} ∑_{j=0}^{r} f_{π^{j}}^{π^{j−1}}(t − 1)f_{σ^{j}}(n − t),

where f_{τ}(n) = |𝔖_{n}(132, τ)|, and f_{τ}^{ρ}(n) is the number of permutations in 𝔖_{n}(τ) containing ρ at least once. To obtain the recursion for F_{τ}(x) it remains to observe that

f_{π^{j}}^{π^{j−1}}(l) + f_{π^{j−1}}(l) = f_{π^{j}}(l)

for any l and j, and to pass to generating functions. Rationality of F_{τ}(x) follows easily by induction.

Theorem 4.1 allows to reduce the calculation of F_{τ}(x) to finding similar functions for several simpler patterns. For example, if τ = [k, m] is a two-layered pattern, then Theorem 4.1 gives

F_{[k,m]}(x) = 1 + xF_{[k−m−1]}(x)F_{[k,m]}(x) + x(F_{[k,m]}(x) − F_{[k−m−1]}(x))F_{[m]}(x) (4.1)

and hence F_{[k,m]}(x) can be expressed via F_{[m]}(x) and F_{[k−m−1]}(x), (see Theorem 5.1 below).

Consider now the case of permutations containing 132 exactly once.

Figure 5. The block decomposition for α ∈ 𝔖_{n} containing 132 exactly once

Theorem 4.2. Let α ∈ 𝔖_{n} contain 132 exactly once. Then the block decomposition of α can have one of the following three forms:

(i) there exists t such that α = (α′, n, α′′), where α′ is a permutation of n − 1, n − 2, …, n − t + 1 containing 132 exactly once, and α′′ is a permutation of 1, 2, …, n − t avoiding 132;

(ii) there exists t such that α = (α′, n, α′′), where α′ is a permutation of n − 1, n − 2, …, n − t + 1 avoiding 132, and α′′ is a permutation of 1, 2, …, n − t containing 132 exactly once;

(iii) there exist t, u such that α = (α′, n − t + 1, n, α′′, n − t + 2, α′′′), where α′ is a permutation of n − 1, n − 2, …, n − t + 3 avoiding 132, α′′ is a permutation of n − t, n − t − 1, …, n − u + 1 avoiding 132, and α′′′ is a permutation of 1, 2, …, n − u avoiding 132.

Proof. Let α ∈ 𝔖_{n} contain 132 exactly once. There are two possibilities: either the only occurrence of 132 in α does not contain n, or it contains n. In the first case we get immediately that any entry of α to the right of n is less than any entry of α to the left of n, since otherwise one gets an occurrence of 132 involving n. In the second case, let i n j be the occurrence of 132 in α. First, we have j = i + 1, since otherwise either (i + 1) n j or i n (i + 1) would be a second occurrence of 132 in α. Next, i immediately precedes n in α, since if l lies between i and n, then either l n j or i l j would be a second occurrence of 132 in α. Finally, any entry to the right of j is less than any entry between n and j, which, in turn, is less than any entry to the left of i (the proof is similar to the analysis of the first case). □

The block decompositions of types (i) and (ii) are similar to that for α ∈ 𝔖_{n}(132) (see Figure 4). The block decomposition of type (iii) is shown in Figure 5.

For a far reaching generalization of this idea, allowing to enumerate permutations with any given number of occurrences of 132, see [MV4].

5. Counting 132-restricted permutations

Throughout this section we write F̄_{τ}(x) instead of F_{132,τ}(x).

5.1. Avoiding 132 and another pattern. By Theorem 1.1 (ii) and (iii), the pairs {132, [k]} and {132, [k, 1]} are Wilf-equivalent, that is F̄_{[k]}(x) = F̄_{[k,1]}(x). It turns out that this equivalence class can be extended as follows.

Theorem 5.1. ([MV2, Th. 2.4]) For any m, 1 ≤ m ≤ k − 1,

F̄_{[k,m]}(x) = R_{k}(x).

This result follows immediately from Theorem 1.1 and (4.1).

A further extension is provided by the following result. We say that τ ∈ 𝔖_{k} is a wedge pattern if it can be represented as τ = (τ^{1}, ρ^{1}, …, τ^{r}, ρ^{r}) so that each of τ^{i} is nonempty, (ρ^{1}, ρ^{2}, …, ρ^{r}) is a layered permutation of 1, …, s for some s, and (τ^{1}, τ^{2}, …, τ^{r}) = (s + 1, s + 2, …, k). For example, 645783912 is a wedge pattern; here r = 3, s = 5, τ^{1} = (6), τ^{2} = (7, 8), τ^{3} = (9), ρ^{1} = (4, 5), ρ^{2} = (3), ρ^{3} = (1, 2). Evidently, [k, m] is a wedge pattern for any m.

Theorem 5.2. ([MV2, Th. 2.6]) F̄_{τ}(x) = R_{k}(x) for any wedge pattern τ ∈ 𝔖_{k}(132).

This result follows easily from Theorem 4.1. The proof of the above two results are purely analytical. It would be very interesting to find a bijective proof of these results.

The case of general layered patterns can be also expressed in terms of Chebyshev polynomials, using the same technique of block decompositions. Since the expressions become rather cumbersome, we present here only the case of a 3-layered pattern.

Theorem 5.3. ([MV2, Th. 2.5]) For any k > m_{1} > m_{2} > 0,

F̄_{[k,m_{1},m_{2}]}(x) = 2t\frac{U_{a+b}(t)U_{a+c−1}(t)U_{b+c}(t) + U_{b−1}(t)U_{b}(t)}{U_{a+b}(t)U_{a+c}(t)U_{b+c}(t)}, t = \frac{1}{2\sqrt{x}},

where a = k − m_{1}, b = m_{1} − m_{2}, c = m_{2}.

5.2. Avoiding 132 and containing another pattern. Denote by G_{τ}^{r}(x) the generating function for the number of permutations in 𝔖_{n}(132) containing a pattern τ ∈ 𝔖_{k} exactly r times. The continued fraction representation (3.1) for r = 1 immediately gives the following result.

Theorem 5.4. ([MV1, Th. 3.1]) For any k ≥ 1,

G_{[k]}^{1}(x) = \frac{1}{U_{k}^{2}(t)}, t = \frac{1}{2\sqrt{x}}.

RESTRICTED PERMUTATIONS AND CHEBYSHEV POLYNOMIALS 11

This result may be extended in two directions. First, let us fix r = 1 and consider other patterns τ. The case of τ = [k, 1] was studied in [Kr]. Theorem 5.5. ([Kr, Th. 7]) For k ≥ 2,

G_{[k,1]}^{1}(x) = \frac{1}{4t^{2}U_{k−2}(t)U_{k}(t)}, t = \frac{1}{2\sqrt{x}}.

The proof involves bijection Φ and the result of Flajolet mentioned in Section 3. A more general case of τ = [k, m] is investigated in [MV2], based on block decompositions. Theorem 5.6. ([MV2, Th. 3.4]) For any k > m > 0,

G_{[k,m]}^{1}(x) = \frac{1}{2tU_{k}(t)U_{m}(t)U_{k−m−1}(t)}, t = \frac{1}{2\sqrt{x}}.

Another direction would be to increase the value of r. A generalization of Theorem 5.4 to the case 1 ≤ r ≤ k was obtained in [MV1], directly from (3.1). Theorem 5.7. ([MV1, Th. 3.1]) For any r, 1 ≤ r ≤ k,

G_{[k]}^{r}(x) = \frac{U_{k−1}^{r−1}(t)}{(2t)^{r−1}U_{k}^{r+1}(t)}, t = \frac{1}{2\sqrt{x}}.

A similar generalization of Theorem 5.5 is as follows. Theorem 5.8. ([Kr, Th. 7]) For any r, 1 ≤ r ≤ k − 1,

G_{[k,1]}^{r}(x) = \frac{1}{U_{k−3}(t)U_{k}(t)} ∑_{l|r} \frac{1}{l + 1}\binom{2l}{l}(2t)^{1−2l− \frac{r}{l}} (\frac{U_{k−3}(t)}{U_{k−2}(t)})^{r/l} , t = \frac{1}{2\sqrt{x}}.

The ideas behind the proof are the same as in the proof of Theorem 5.5. Theorem 5.7 can be extended to cover a wider range of r’s. Theorem 5.9. ([MV1, Th. 4.1]) For any r, 1 ≤ r ≤ k(k + 3)/2,

G_{[k]}^{r}(x) = \frac{U_{k−1}^{r−1}(t)}{(2t)^{r−1}U_{k}^{r+1}(t)} ∑_{j=0}^{⌊(r−1)/k⌋} \binom{r − kj + j − 1}{j} (\frac{(2t)^{\frac{k−2}{k}} U_{k}(t)}{U_{k−1}(t)})^{kj} ,

where t = 1/2\sqrt{x}. The case of general r was treated in [Kr]. Theorem 5.10. ([Kr, Th. 3]) For any r,

G_{[k]}^{r}(x) = ∑ (\binom{l_{1} + l_{2} − 1}{l_{2}}\binom{l_{2} + l_{3} − 1}{l_{3}} …) \frac{U_{k−1}^{l_{1}−1}(t)}{U_{k}^{l_{1}+1}(t)}(2t)^{−(l_{1}−1)−2(l_{2}+l_{3}+...)},

where the sum is over all nonnegative integers l_{1}, l_{2}, … with

l_{1}\binom{k − 1}{k − 1} + l_{2}\binom{k}{k − 1} + l_{3}\binom{k + 1}{k − 1} + ⋯ = r,

and t = 1/2\sqrt{x}.

5.3. Containing 132 exactly once and avoiding another pattern. Denote by H_{τ}(x) the generating function for the number of permutations in 𝔖_{n} avoiding a pattern τ ∈ 𝔖_{k} and containing 132 exactly once. We start from the following result obtained in [MV1].

Theorem 5.11. ([MV1, Th. 4.2]) For any k ≥ 3,

H_{[k]}(x) = \frac{1}{4t^{2}U_{k}^{2}(t)} ∑_{j=1}^{k−2} U_{j}^{2}(t), t = \frac{1}{2\sqrt{x}}.

The idea behind the proof is similar to that of the proof of Theorem 3.1 explained above in Section 3.

This result can be extended to the case of general 2-layered patterns as follows.

Theorem 5.12. (i) For any k ≥ 4,

H_{[k,1]}(x) = \frac{1}{4t^{2}U_{k}^{2}(t)} (∑_{j=1}^{k−2} U_{j}^{2}(t) − 1) , t = \frac{1}{2\sqrt{x}};

besides,

H_{[3,1]}(x) = \frac{x^{3}}{1 − 2x}.

(ii) For any k ≥ 5,

H_{[k,2]}(x) = \frac{1}{4t^{2}U_{k}^{2}(t)} (∑_{j=1}^{k−2} U_{j}^{2}(t) − \frac{2tU_{k−3}(t)}{U_{k−2}(t)} − 2) , t = \frac{1}{2\sqrt{x}};

besides,

H_{[4,2]}(x) = \frac{x^{3}(1 + x)}{(1 − x)(1 − 3x + x^{2})}.

(iii) For any k ≥ 6 and any m, 3 ≤ m ≤ k/2,

\begin{matrix}H_{[k,m]}(x) = \frac{1}{4t^{2}U_{k}^{2}(t)}( ∑_{j=1}^{k−m−2} U_{j}^{2}(t) + ∑_{j=1}^{m−1} U_{j}^{2}(t) − 1 \\ +U_{k−1}(t)U_{m−1}(t)U_{k−m−2}(t)), t = \frac{1}{2\sqrt{x}}. \end{matrix}

Remark. Clearly, the cases k = 3, m = 2; k = 4, 5, m = 3; k ≥ 6, m > k/2 are also covered, since H_{[k,m]}(x) = H_{[k,k−m]}(x).

Proof. By Theorem 4.2, we have exactly three possibilities for the block decomposition of an arbitrary α ∈ 𝔖_{n}. Let us write an equation for H_{[k,1]}(x) with k ≥ 4. The contribution of the first decomposition above is xH_{[k−2]}(x)F̄_{[k,1]}(x) + x(H_{[k,1]}(x) − H_{[k−2]}(x)). Here the first term corresponds to the case α′ avoids [k − 2] and α′′ avoids [k, 1], while the second term corresponds to the case α′ avoids [k, 1] but contains [k−2], and α′′ = ∅.

The contribution of the second possible decomposition is xF̄_{[k−2]}(x)H_{[k,1]}(x); here α′′ contains 132, and hence is always distinct from ∅.

Finally, the contribution of the third possible decomposition is

x^{3}F̄_{[k−2]}^{2}(x)F̄_{[k,1]}(x) + x^{3}F̄_{[k−2]}(x)(F̄_{[k,1]}(x) − F̄_{[k−2]}(x)).

Here the first term corresponds to the case α′, α′′ avoid [k − 2], α′′′ avoids [k, 1], while the second term corresponds to the case α′ avoids [k − 2], α′′ avoids [k, 1] but contains [k − 2], and α′′′ = ∅.

Solving the obtained linear equation and using Theorems 1.1, 5.11, and well known identities involving Chebyshev polynomials (see e.g. [MV2, Lem. 4.1]), we get the desired expression for H_{[k,1]}(x), k ≥ 4.

In the case k = 3, the contributions of the first and the second decompositions degenerate to xH_{[3,1]}(x) each, while the contribution of the third decomposition degenerates to x^{3} (which means that the only permutation having this decomposition is 132 itself). The result follows immediately.

Let us consider now the case of H_{[k,2]}(x) with k ≥ 5. The contribution of the first decomposition is xH_{[k−3]}(x)F̄_{[k,2]}(x) + x(H_{[k,2]}(x) − H_{[k−3]}(x))F̄_{[2]}(x). Here the first term corresponds to the case α′ avoids [k − 3] and α′′ avoids [k, 2], while the second term corresponds to the case α′ avoids [k, 2] but contains [k − 3], and α′′ avoids [2].

The contribution of the second decomposition is xF̄_{[k−3]}(x)H_{[k,2]}(x).

Finally, the contribution of the third decomposition is

\begin{matrix}x^{3}F̄_{[k−3]}^{2}(x)F̄_{[k,2]}(x) + x^{3}F̄_{[k−3]}(x)(F̄_{[k,2]}(x) − F̄_{[k−3]}(x))F̄_{[2]}(x) \\ +x^{3}(F̄_{[k−2]}(x) − F̄_{[k−3]}(x))F̄_{[2]}(x). \end{matrix}

Here the first term corresponds to the case α′, α′′ avoid [k − 3], α′′′ avoids [k, 2], the second term corresponds to the case α′ avoids [k − 3], α′′ avoids [k, 2] but contains [k −3], and α′′′ avoids [2], while the third term corresponds to the case α′ avoids [k −2] but contains [k − 3], α′′ = ∅, and α′′′ avoids [2].

The expression for H_{[k,2]}(x) follows easily from this equation and Theorems 1.1 and 5.11.

The case k = 4 is treated similarly.

For general m, 3 ≤ m ≤ k − m, the contribution of the first decomposition equals xH_{[k−m−1]}(x)F̄_{[k,m]}(x) + x(H_{[k,m]}(x) − H_{[k−m−1]}(x))F̄_{[m]}(x), the contribution of the second decomposition equals xF̄_{[k−m−1]}(x)H_{[k,m]}(x) + x(F̄_{[k,m]}(x) − F̄_{[k−m−1]}(x))H_{[m]}(x), and the contribution of the third structure decomposition

\begin{matrix}x^{3}F̄_{[k−m−1]}^{2}(x)F̄_{[k,m]}(x) + x^{3}F̄_{[k−m−1]}(x)(F̄_{[k,m]}(x) − F̄_{[k−m−1]}(x))F̄_{[m]}(x) \\ +x^{3}(F̄_{[k,m]}(x) − F̄_{[k−m−1]}(x))F̄_{[m−1]}(x)F̄_{[m]}(x). \end{matrix}

The final result again follows from Theorems 1.1 and 5.11. □

5.4. Containing 132 and another pattern exactly once. Denote by Φ_{τ}(x) the generating function for the number of permutations in 𝔖_{n} containing both 132 and a pattern τ ∈ 𝔖_{k} exactly once. We start from the following result.

Theorem 5.13. For any k ≥ 1,

Φ_{[k]}(x) = \frac{1}{4t^{3}U_{k}^{2}(t)} ∑_{i=1}^{k−2} \frac{∑_{j=1}^{k−i} U_{j}^{2}(t) − 1}{U_{k−i}(t)U_{k−i+1}(t)}, t = \frac{1}{2\sqrt{x}}.

Proof. The three possible block decompositions of permutations containing 132 exactly once are described in Theorem 4.2. Let us find the recursion for Φ_{[k]}(x). It is easy to see that the contribution of the first decomposition equals

xΦ_{[k−1]}(x)F̄_{[k]}(x) + xH_{[k−1]}(x)G_{[k]}^{1}(x),

the contribution of the second decomposition equals

xG_{[k−1]}^{1}(x)H_{[k]}(x) + xF̄_{[k−1]}(x)Φ_{[k]}(x),

while the contribution of the third decomposition equals

2x^{3}G_{[k−1]}^{1}(x)F̄_{[k−1]}(x)F̄_{[k]}(x) + x^{3}F̄_{[k−1]}^{2}(x)G_{[k−1]}^{1}(x).

Solving the obtained recursion with the initial condition Φ_{[2]}(x) = 0 and using Theorems 1.1, 5.4, and 5.11, we get the desired result. □

In particular, for k = 3 we get Φ_{[3]}(x) = 2x^{5}(1−2x)^{−3}, which means that the number of permutations in 𝔖_{n} containing both 132 and 123 exactly once equals (n−3)(n−4)2^{n−5} (see [R, Th. 1.3.18]).

Similarly to the previous section, this result can be extended to the case of general 2-layered patterns. Since the answers become very cumbersome, we present here only the simplest case.

Theorem 5.14. For any k ≥ 4,

\begin{matrix}Φ_{[k,1]}(x) = \frac{1}{8t^{3}U_{k}^{2}(t)} (\frac{U_{k}(t)}{2t^{2}U_{k−2}(t)} ∑_{i=1}^{k−4} \frac{∑_{j=1}^{k−i−2} U_{j}^{2}(t)−1}{U_{k−i−2}(t)U_{k−i−1}(t)} \\ + \frac{1}{2tU_{k−2}^{2}(t)} ∑_{i=1}^{k−4} U_{i}^{2}(t) + \frac{U_{k−3}(t)}{2tU_{k−1}(t)} + \frac{U_{k}(t)}{U_{k−1}(t)}) , \end{matrix}

where t = 1/2\sqrt{x}.

5.5. Generalizations. Here we present several directions to generalize the results of the previous sections. The first of these directions is to consider more than one additional restriction. For example, the following result is true. Let F̄_{τ_{1},τ_{2}}(x) be the generating function for the number of permutations in 𝔖_{n}(132, τ_{1}, τ_{2}). Assume that τ_{1} = [k, m], k − m ⩾ m, and τ_{2} = [l]. It is easy to see that the only interesting case is l > k − m, since otherwise F̄_{[k,m],[l]}(x) = F̄_{[l]}(x).

Theorem 5.15. Let l > k − m ≥ m, then

F̄_{[k,m],[l]}(x) = R_{k}(x) − (xR_{k−m}(x)R_{m}(x))^{l+m−k}(R_{k}(x) − R_{k−m}(x)).

Proof. Let α ∈ 𝔖_{n}(132), then either α = ∅ (which means that n = 0), or α = (α′, n, α′′), where both α′ and α′′ avoid 132. According to this dichotomy, we get the following recursion:

F̄_{[k,m],[l]}(x) = 1 + xF̄_{[k−m−1]}(x)F̄_{[k,m],[l]}(x) + x(F̄_{[k,m],[l−1]}(x) − F̄_{[k−m−1]}(x))F̄_{[m]}(x).

Solving this recursion with the initial condition F̄_{[k,m],[k−m]}(x) = F̄_{[k−m]}(x) and using Theorem 1.1, we get the desired result. □

Similarly, let G_{τ_{1};τ_{2}}(x) be the generating function for the number of permutations in 𝔖_{n}(132, τ_{1}) that contain τ_{2} exactly once. As before, we assume τ_{1} = [k, m], k −m ⩾ m, and τ_{2} = [l]. Once again, the case m ⩾ l is of no interest, since in this case G_{[k,m];[l]}(x) = G_{[l]}(x).

Theorem 5.16. (i) Let l > k − m ≥ m, then

\begin{matrix}G_{[k,m];[l]}(x) = \frac{1}{U_{m}(t)U_{k−m}(t)} (\frac{U_{m−1}(t)}{U_{m}(t)})^{l−m} (\frac{U_{k−m−1}(t)}{U_{k−m}(t)})^{l+m−k} \\ × (∑_{j=m+2}^{k−m} \frac{U_{j−m−2}(t)}{U_{j−2}(t)U_{j−1}(t)} (\frac{U_{m−1}(t)}{U_{m}(t)})^{m+1−j} + 1) , \end{matrix}

where t = 1/2\sqrt{x}.

(ii) Let k − m ≥ l > m, then

\begin{matrix}G_{[k,m];[l]}(x) = \\ \frac{1}{U_{l}(t)U_{m}(t)} (\frac{U_{m−1}(t)}{U_{m}(t)})^{l−m} (∑_{j=m+1}^{l} \frac{U_{j−m−1}(t)}{U_{j−1}(t)U_{j}(t)} (\frac{U_{m−1}(t)}{U_{m}(t)})^{m−j} + 1) , \end{matrix}

where t = 1/2\sqrt{x}.

Another possible direction is to replace 132 by some restriction of length 4 or more having a similar restrictive power. Define L_{p} as the set of all patterns in 𝔖_{p} of the form π_{1}1π_{2}2π_{3}, where π_{2} is nonempty. Evidently, L_{3} = {132}; for p = 4 we get L_{4} = {1324, 1423, 1342, 1432, 3142, 4132}, and so on. It turns out that L_{p} is, in a sense, an analog of 132 for p > 3. For example, the following result is an analog of Theorem 1.1 (ii) for p = 4.

Theorem 5.17. For any k ≥ 2,

F_{{L_{4},[k]}}(x) = 1 + x + x^{2}R_{k}(x)R_{k−1}(x)(R_{k−1}(x) + R_{k−2}(x)).

Proof. The main ingredient of the proof is the following description of the block decompositions of permutations in 𝔖_{n}(L_{4}). Let α ∈ 𝔖_{n}(L_{4}), then there exist 0 ⩽ r ≤ s ≤ n − 1 such that either α = α_{1}, n − 1, α_{2}, n, α_{3}, or α = α_{1}, n, α_{2}, n − 1, α_{3}, where α_{1} is a permutation of the numbers s + 1, s + 2, …, n − 2, α_{2} is a permutation of the numbers r + 1, r + 2, …, s, and α_{3} is a permutation of the numbers 1, 2, …, r. □

Consider now the case of a general p > 3. For an arbitrary π ∈ 𝔖_{p} we define a sequence a(π) of zeros and ones of length p − 1 as follows. First of all, we put a_{1}(π) = 1 if π_{p−1} < π_{p} and a_{1}(π) = 0 otherwise. If a_{1}(π), …, a_{j}(π) are already determined, we put a_{j+1}(π) = 1 if the length of the maximal increasing subsequence in (π_{k−j−1}, π_{k−j}, …, π_{k}) is greater than that of (π_{k−j}, …, π_{k}), and a_{j+1}(π) = 0 otherwise. For example, let π = 7346215, then a_{1}(π) = 1, a_{2}(π) = 0, a_{3}(π) = 0, a_{4}(π) = 0, a_{5}(π) = 1, a_{6}(π) = 0. For an arbitrary sequence a = (a_{1}, …, a_{p−1}) ∈ Q^{p−1} = {0, 1}^{p−1} we denote by N(a) the number of permutations π ∈ 𝔖_{p} such that a(π) = a. The following result is a further generalization of Theorem 5.17.

Theorem 5.18. For any k ≥ p − 2 and any p > 3,

F_{{L_{p},[k]}}(x) = ∑_{i=0}^{p−3} i!x^{i} + x^{p−2}R_{k}(x)R_{k−1}(x) ∑_{a∈Q^{p−3}} N(a) ∏_{j=1}^{p−3} R_{k−j−a_{j}}(x).

As a generalization of Theorem 5.1 we get the following result.

Theorem 5.19. (i) For any m, 1 ≤ m ≤ k − 2,

\begin{matrix}F_{\{L_{4},[k,m]\}}(x) = 1 + \frac{1}{4t^{2}} + \frac{U_{k−2}(t)U_{m−1}(t)}{tU_{k}(t)U_{m}(t)} \\ +\frac{U_{k−m−2}(t)}{2tU_{k}(t)U_{m}(t)} (\frac{U_{k−m−2}(t)}{U_{k−m−1}(t)} + \frac{U_{k−m−3}(t)}{U_{k−m−2}(t)}) , t = \frac{1}{2\sqrt{x}}. \end{matrix}

(ii)

F_{{L_{4},[k,k−1]}}(x) = F_{{L_{4},[k]}}(x).

6. Counting 321-restricted permutations

The case of 321-restricted permutations is studied much less than the previous one. We start from the following generalization of Theorem 1.1(i).

Theorem 6.1. ([MV3, Th. 1.2(ii)]) For k ≥ 2 and any m, 1 ≤ m ≤ k − 1,

F_{{321,[k,m]}}(x) = R_{k}(x).

Therefore, the Wilf class of {132, [k, m]} contains the pair {321, [k, m]} as well. Once again, we have only an analytical proof of this result. Moreover, the ideas behind this proof are very different from these behind the proofs in the previous section. Let T = {321, [k, m]}; we define

A(n, r) = ∑_{i=0}^{r+m}(−1)^{i}\binom{r + m − i}{i}f_{T} (n − i),

where f_{T} (n) = |S_{n}(T)|, and prove that A(n, r) satisfy a linear recurrence (see [MV3, Th. 2.3]). It follows that

∑_{i=0}^{k}(−x)^{i}\binom{k − i}{i} (F_{T} (x) − ∑_{j=0}^{k−i−1} x^{j}c_{j}) = 0,

where c_{j} is the jth Catalan number. Using classical identities involving Catalan numbers we get the desired result.

In view of Theorems 5.1 and 5.2, it is a challenge to find a bijective proof of Theorem 6.1.

A striking analog of Theorem 5.7 is given by the following result.

Theorem 6.2. ([Kr, Th. 10]) For k ≥ 3 and any r, 1 ≤ r ≤ k,

G_{321;[k,1]}^{r}(x) = \frac{U_{k−1}^{r−1}(t)}{(2t)^{r−1}U_{k}^{r+1}(t)}, t = \frac{1}{2\sqrt{x}}.

The proof of this result is based on the bijection Ψ between 123-avoiding permutations with exactly r occurrences of the pattern [k, 1] and Dyck paths which start at the origin, return to the x-axis, and have exactly r peaks at height k.

The case of a general 2-layered pattern remains intractable. Our computational experiments suggest that G_{321;[k,1]}^{r}(x) = G_{321;[k,2]}^{r}(x) for 1 ⩽ r ⩽ k; however, we are unable to prove this.

References

[Bo] M. Bona, The solution of a conjecture of Stanley and Wilf for all layered patterns, J. Combin. Theory Ser. A 85 (1999), 96–104.

[BCS] P. Brändén, A. Claesson, and E. Steingrímsson, Catalan continued fractions and increasing subsequences in permutations, (2001), preprint http://www.cs.chalmers.se/~einar.

[CW] T. Chow and J. West, Forbidden subsequences and Chebyshev polynomials, Discr. Math. 204 (1999), 119–128.

[Fl] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), 125–161.

[JR] M. Jani and R. Rieper, Continued fractions and Catalan problems Electron. J. Combin. 7 (2000), #R45.

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

[MV1] T. Mansour and A. Vainshtein, Restricted permutations, continued fractions, and Chebyshev polynomials, Electron. J. Combin. 7 (2000), #R17.

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

[MV3] T. Mansour and A. Vainshtein, Layered restrictions and Chebyshev polynomials, Annals of Combinatorics, to appear (2001), preprint CO/0008173.

[MV4] T. Mansour and A. Vainshtein, Counting occurrences of 132 in a permutation, Adv. Appl. Math., to appear (2002), preprint CO/0105073.

[Ri] Th. Rivlin, Chebyshev polynomials. From approximation theory to algebra and number theory, John Wiley, New York, 1990.

[R] A. Robertson, Permutations containing and avoiding 123 and 132 patterns, Discrete Mathematics and Theoretical Computer Science, 3 (1999), 151–154.

[RWZ] A. Robertson, H. Wilf, and D. Zeilberger, Permutation patterns and continued fractions, Electron. J. Combin. 6 (1999), #R38.

[RV] E. Roblet and X. Viennot, Théorie combinatoire des T-fractions et approximants des Padé en deux points, Discrete Math. 153 (1996), 271–288.

[SS] R. Simion, F.W. Schmidt, Restricted Permutations, Europ. J. Combin. 6 (1985), 383–406.

[St1] R. P. Stanley, Enumerative combinatorics, vol. 1, 2nd edition, Cambridge University Press, 1997.

[St2] R. P. Stanley, Enumerative combinatorics, vol. 2, Cambridge University Press, 1999.

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