RESTRICTED EVEN PERMUTATIONS AND CHEBYSHEV POLYNOMIALS

Toufik Mansour ^{1}

Department of Mathematics, Chalmers University of Technology, S-412 96 Göteborg, Sweden

                              toufik@math.chalmers.se

Abstract

We study generating functions for the number of even (odd) permutations on n letters avoiding 132 and an arbitrary permutation τ on k letters, or containing τ exactly once. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.

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

1. Introduction

The aim of this paper is to give analogies of enumerative results on certain classes of permutations characterized by pattern-avoidance in the symmetric group 𝔖_{n}. In the set of even (odd) permutations we identify classes of restricted even (odd) permutations with enumerative properties analogous to results on permutations. More precisely, we study generating functions for the number of even (odd) permutations avoiding 132 and avoiding (or containing exactly once) an arbitrary permutation τ ∈ 𝔖_{k}. Moreover we consider statistics of the increasing pattern. In the remainder of this section we present a brief account of earlier works which motivated our investigation, we give the basic definitions used throughout the paper, and the organization of this paper.

Let [p] = {1, …, p} denote a totally ordered alphabet on p letters, and let α = (α_{1}, …, α_{m}) ∈ [p_{1}]^{m}, β = (β_{1}, …, β_{m}) ∈ [p_{2}]^{m}. We say that α is order-isomorphic to β if for all 1 ≤ i < j ≤ m one has α_{i} < α_{j} if and only if β_{i} < β_{j}. For two permutations π ∈ 𝔖_{n} and τ ∈ 𝔖_{k}, an occurrence of τ in π is 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 the pattern. We say that π avoids τ, or is τ-avoiding, if there is no occurrence of τ in π, and we say that π contains τ exactly r times if there is r different occurrences of τ in π. For example, the permutation 598376412 ∈ 𝔖_{9} avoids 123 and contains 1432 exactly twice.

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} ∈ 𝔖_{3} (see [SimSch]), and for τ_{1} ∈ 𝔖_{3} and τ_{2} ∈ 𝔖_{4} (see [W]). Several recent papers [CW, MV1, Kr, MV2, MV3, MV4, BCS] deal with the case τ_{1} ∈ 𝔖_{3}, τ_{2} ∈ 𝔖_{k} for various pairs τ_{1}, τ_{2}. Another natural question is to study permutations avoiding τ_{1} and containing τ_{2} exactly t times. Such a problem for certain τ_{1}, τ_{2} ∈ 𝔖_{3} and t = 1 was investigated in [Ro], and for certain τ_{1} ∈ 𝔖_{3}, τ_{2} ∈ 𝔖_{k} in [RWZ, MV1, Kr, MV2, MV3, MV4]. For example, several authors [RWZ, MV1, Kr, BCS] have shown that generating functions for the number 132-avoiding permutations in 𝔖_{n} with respect to number of occurrences of the pattern 12 … k can be expressed as either continued fractions or Chebyshev polynomials of the second kind.

1Research financed by EC’s IHRP Programme, within the Research Training Network ”Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272

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. The Chebyshev polynomials satisfy the following recurrence U_{r}(t) = 2tU_{r−1}(t) − U_{r−2}(t) for r ≥ 2 together with U_{0}(t) = 1 and U_{1}(t) = 2t. Evidently, U_{r}(x) is a polynomial of degree r in x with integer coefficients. 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]). Apparently, for the first time the relation between restricted permutations and Chebyshev polynomials was discovered by Chow and West in [CW], and later by Mansour and Vainshtein [MV1, MV2, MV3, MV4] and Krattenthaler [Kr]. These results are related to a rational function

(1.1)  R_{k}(x) = \frac{U_{k−1} (\frac{1}{2\sqrt{x}})}{\sqrt{x}U_{k} (\frac{1}{2\sqrt{x}})}

for all k ≥ 1. 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 and satisfies the following equation (see [MV1, MV3, MV4]) for k ≥ 1,

(1.2)  R_{k}(x) = \frac{1}{1 − xR_{k−1}(x)}.

Let π ∈ 𝔖_{n}. The number of inversions of π is given by |{(i, j) : π_{i} > π_{j}, 1 ≤ i < j ≤ n}|. The sign of π, sign(π), is given by the number of inversions of π modulo 2 (equals 1 if the number inversions of π is given by even number, otherwise equals −1). We say π is an even permutation [respectively; odd permutation] if sign(π) = 1 [respectively; sign(π) = −1]. We say π is an involution if π = π^{−1}. We denote the set of all even [respectively; odd] permutations in 𝔖_{n} by 𝔈_{n} [respectively; 𝔒_{n}]. For example, if π = 4132 ∈ 𝔖_{4} then the number of inversions of π equals 4, so sign(π) = 1 and π ∈ 𝔈_{4}.

The paper of Simion and Schmidt [SimSch] generalized and considered for many directions. Here we give two examples. The first one is paper of Chow and West [CW], which had dealt with three cases of avoiding 132 or 123 and avoiding τ ∈ 𝔖_{k}. In particular, they found the generating function for the number of permutations in 𝔖_{n}(132, 12 … k) which given by R_{k}(x). The second one is papers of Guibert and Mansour [GM1, GM2], which had dealt with the cases of avoiding 132 (or containing exactly once) and avoiding τ ∈ 𝔖_{k} (or containing exactly once). More precisely, the paper [GM1] dealt with the case of the generating function for number of involutions in 𝔖_{n} avoiding 132 (or containing exactly once) and avoiding τ ∈ 𝔖_{k} (or containing exactly once). The paper [GM2] dealt with the case of the generating function for number of even (odd) involutions in 𝔖_{n} avoiding 132 (or containing exactly once) and avoiding τ ∈ 𝔖_{k} (or containing exactly once).

Theorem 1.1. (see [CW, GM1, GM2]) For all k ≥ 0,

(i) The generating function for the number of permutations in 𝔖_{n} avoiding both 132 and 12 … k is given by

R_{k}(x).

(ii) The generating function for the number of involutions in 𝔖_{n} avoiding both 132 and 12 … k is given by

I_{k}(x) = \frac{1}{xU_{k} (\frac{1}{2x})} ∑_{j=0}^{k−1} U_{j} (\frac{1}{2x}) .

(iii) The generating function for the number of even involutions in 𝔖_{n} avoiding both 132 and 12 … k is given by

∑_{j=0}^{k−1} (x^{j}(1 + \frac{x^{2}}{2} (R_{k−1−j}(x^{2}) + R_{k−1−j}(−x^{2}))I_{k−j}(x)) ∏_{i=k−j}^{k} R_{i}(−x^{2})) .

The above theorem invites the following question: Find explicitly the generating function for the number even (odd) permutations avoiding both 132 and 12 … k in terms of Chebyshev polynomials? In this paper we give a complete answer for this question (see Subsection 2.2).

As a consequence of [MV2, MV4], we present a general approach to the study of even (odd) permutations avoiding 132 and avoiding an arbitrary pattern τ of length k, or containing τ exactly once. We derive all the previously known results for this kind of problems, as well as many new results.

The paper is organized as follows. The case of even (odd) permutations avoiding both 132 and τ is treated in Section 2. We derive a simple recursion for the corresponding generating functions for general τ. This recursion can be solved explicitly for several interesting cases, including 12 … k, (d + 1)(d + 2) … k12 … d, and odd-wedge patterns defined below. In particularly, we prove the generating function for the number of even (odd) permutations avoiding both 132 and τ ∈ S_{k}(132) is a rational function for every nonempty pattern τ. Observe that if τ itself contains 132, then any 132-avoiding permutation avoids τ as well, so in what follows we always assume that τ ∈ S_{k}(132). The case of permutations avoiding 132 and containing τ exactly once is treated in Section 3. Here again we start from a general recursion, and then solve it for several particular cases. Finally, in Section 4 we describe several directions to extend and to generalize the results of the pervious sections.

Most of the explicit solutions obtained in the next sections involve Chebyshev polynomials of the second kind.

2. Avoiding an arbitrary pattern

Consider 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 m_{i+1} and all the entries of τ^{i+1}. This representation is called the canonical decomposition of τ. Given the canonical decomposition, we 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} = ∅. Strictly speaking, prefixes and suffices themselves are not patterns, since they are not permutations (except for π^{r} = σ^{0} = τ). However, any prefix or suffix is order-isomorphic to a unique permutation, and in what follows we do not distinguish between a prefix (or suffix) and the corresponding permutation.

The set of all T -avoiding even [respectively; odd] permutations in 𝔖_{n} we denote by 𝔈_{n}(T) [respectively; 𝔒_{n}(T)]. Let e_{τ} (n) [respectively; o_{τ} (n)] be the cardinality of the set 𝔈_{n}(132, τ) [respectively; 𝔒_{n}(132, τ)]. The corresponding generating function let us denote by 𝔈_{τ} (x) [respectively; 𝔒_{τ} (x)], that is,

𝔈_{τ} (x) = ∑_{n≥0} e_{τ} (n)x^{n} [respectively; 𝔒_{τ} (x) = ∑_{n≥0} o_{τ} (n)x^{n}] .

The generating function for the number of permutations avoiding both 132 and τ we denote by F_{τ} (x). Clearly,

(2.1)  F_{τ} (x) = 𝔈_{τ} (x) + 𝔒_{τ} (x).

The following proposition which is the base of all the results in this section. Proposition 2.1. Let k ≥ 1 and n ≥ 1, then

e_{τ} (2n + 1) = ∑_{d=0}^{r} ∑_{j=0}^{2n}(e_{π^{d}}(j) − e_{π^{d−1}}(j))e_{σ^{d}}(2n − j) + ∑_{d=0}^{r} ∑_{j=0}^{2n}(o_{π^{d}}(j) − o_{π^{d−1}}(j))o_{σ^{d}}(2n − j),

e_{τ} (2n) = ∑_{d=0}^{r} ∑_{j=0,2,4,...,2n−2}(e_{π^{d}}(j) − e_{π^{d−1}}(j))o_{σ^{d}}(2n − j − 1) + (o_{π^{d}}(j) − o_{π^{d−1}}(j))e_{σ^{d}}(2n − j − 1)

+ ∑_{d=0}^{r} ∑_{j=1,3,5,...,2n−1}(e_{π^{d}}(j) − e_{π^{d−1}}(j))e_{σ^{d}}(2n − j − 1) + (o_{π^{d}}(j) − o_{π^{d−1}}(j))o_{σ^{d}}(2n − j − 1).

Proof. We use induction. Clearly, the result holds for n = 1. Now let π ∈ 𝔖_{n}(132) such that π_{j+1} = n, 0 ≤ j ≤ n−1. Then β = (π_{1}, …, π_{j}) is a 132-avoiding permutation on the letters n−1, n−2, …, n−j and γ = (π_{j+1}, …, π_{n}) is a 132-avoiding permutation on the letters n − j − 1, n − j − 2, …, 1. If we assume that β avoids π^{d} and contains π^{d−1}, then γ avoids σ^{d}, where d = 0, 1, 2 …, r. Besides,

sign(π) = (−1)^{(j+1)(n−j−1)}sign(β)sign(γ) = (−1)^{(j+1)(n−1)}sign(β)sign(γ),

equivalently,

sign(π) = \{ \begin{matrix}sign(β) · sign(γ), & if n odd \\ (−1)^{j+1} · sign(β) · sign(γ), & if n even \end{matrix}

Hence, if summing over all d = 0, 1, …, r and j = 0, 1, 2 …, n together with use of the fact that the number of even [respectively; odd] permutations in 𝔈_{n} [respectively; 𝔒_{n}] avoiding β and containing γ is given by e_{β}(n) − e_{β,γ}(n) [respectively; o_{β}(n) − o_{β,γ}(n)] we get the desired result. □

Similarly to Proposition 2.1 we obtain the following result. Proposition 2.2. Let k ≥ 1 and n ≥ 1, then

o_{τ} (2n + 1) = ∑_{d=0}^{r} ∑_{j=0}^{2n}(e_{π^{d}}(j) − e_{π^{d−1}}(j))o_{σ^{d}}(2n − j) + ∑_{d=0}^{r} ∑_{j=0}^{2n}(o_{π^{d}}(j) − o_{π^{d−1}}(j))e_{σ^{d}}(2n − j),

o_{τ} (2n) = ∑_{d=0}^{r} ∑_{j=0,2,4,...,2n−2}(e_{π^{d}}(j) − e_{π^{d−1}}(j))e_{σ^{d}}(2n − j − 1) + (o_{π^{d}}(j) − o_{π^{d−1}}(j))o_{σ^{d}}(2n − j − 1)

+ ∑_{d=0}^{r} ∑_{j=1,3,5,...,2n−1}(e_{π^{d}}(j) − e_{π^{d−1}}(j))o_{σ^{d}}(2n − j − 1) + (o_{π^{d}}(j) − o_{π^{d−1}}(j))e_{σ^{d}}(2n − j − 1).

Our present aim is to find the generating functions 𝔈_{τ} (x) and 𝔒_{τ} (x); thus we need the following lemma which holds immediately by definitions.

Lemma 2.3. let {a_{n}}_{n≥0} and {b_{n}}_{n≥0} be two sequences, and the corresponding generating functions are a(x) and b(x); respectively. Then

(1) ∑_{n≥0} a_{2n}x^{2n} = \frac{1}{2}(a(x) + a(−x));

(2) ∑_{n≥1} a_{2n−1}x^{2n−1} = \frac{1}{2}(a(x) − a(−x));

(3) ∑_{n≥1} ∑_{j=0,2,4,...,2n−2} a_{j}b_{2n−1−j}x^{2n−1} = \frac{1}{4}(a(x) + a(−x))(b(x) − b(−x));

(4) ∑_{n≥1} ∑_{j=1,3,5,...,2n−1} a_{j}b_{2n−1−j}x^{2n−1} = \frac{1}{4}(a(x) − a(−x))(b(x) + b(−x)).

Theorem 2.4. For any nonempty pattern τ ∈ 𝔖_{k}(132), the generating functions 𝔈_{τ} (x) and 𝔒_{τ} (x) are a rational functions in x satisfying the relations

(2.2) \begin{matrix}𝔈_{τ} (x) − 𝔈_{τ} (−x) = x ∑_{d=0}^{r}(𝔈_{π^{d}}(x) − 𝔈_{π^{d−1}}(x))𝔈_{σ^{d}}(x) + (𝔈_{π^{d}}(−x) − 𝔈_{π^{d−1}}(−x))𝔈_{σ^{d}}(−x) \\ +x ∑_{d=0}^{r}(𝔒_{π^{d}}(x) − 𝔒_{π^{d−1}}(x))𝔒_{σ^{d}}(x) + (𝔒_{π^{d}}(−x) − 𝔒_{π^{d−1}}(−x))𝔒_{σ^{d}}(−x)), \end{matrix}

(2.3) \begin{matrix}𝔒_{τ} (x) − 𝔒_{τ} (−x) = x ∑_{d=0}^{r}(𝔈_{π^{d}}(x) − 𝔈_{π^{d−1}}(x))𝔒_{σ^{d}}(x) + (𝔈_{π^{d}}(−x) − 𝔈_{π^{d−1}}(−x))𝔒_{σ^{d}}(−x) \\ +x ∑_{d=0}^{r}(𝔒_{π^{d}}(x) − 𝔒_{π^{d−1}}(x))𝔈_{σ^{d}}(x) + (𝔒_{π^{d}}(−x) − 𝔒_{π^{d−1}}(−x))𝔈_{σ^{d}}(−x)), \end{matrix}

(2.4)  \begin{matrix}𝔈_{τ} (x) + 𝔈_{τ} (−x) − 2 = \\ = \frac{x}{2} ∑_{d=0}^{r}(𝔈_{π^{d}}(x) + 𝔈_{π^{d}}(−x) − 𝔈_{π^{d−1}}(x) − 𝔈_{π^{d−1}}(−x))(𝔒_{σ^{d}}(x) − 𝔒_{σ^{d}}(−x)) \\ +\frac{x}{2} ∑_{d=0}^{r}(𝔒_{π^{d}}(x) + 𝔒_{π^{d}}(−x) − 𝔒_{π^{d−1}}(x) − 𝔒_{π^{d−1}}(−x))(𝔈_{σ^{d}}(x) − 𝔈_{σ^{d}}(−x)) \\ +\frac{x}{2} ∑_{d=0}^{r}(𝔈_{π^{d}}(x) − 𝔈_{π^{d}}(−x) − 𝔈_{π^{d−1}}(x) + 𝔈_{π^{d−1}}(−x))(𝔈_{σ^{d}}(x) + 𝔈_{σ^{d}}(−x)) \\ +\frac{x}{2} ∑_{d=0}^{r}(𝔒_{π^{d}}(x) − 𝔒_{π^{d}}(−x) − 𝔒_{π^{d−1}}(x) + 𝔒_{π^{d−1}}(−x))(𝔒_{σ^{d}}(x) + 𝔒_{σ^{d}}(−x)), \end{matrix}

and

(2.5)  \begin{matrix}𝔒_{τ} (x) + 𝔒_{τ} (−x) = \\ = \frac{x}{2} ∑_{d=0}^{r}(𝔈_{π^{d}}(x) + 𝔈_{π^{d}}(−x) − 𝔈_{π^{d−1}}(x) − 𝔈_{π^{d−1}}(−x))(𝔈_{σ^{d}}(x) − 𝔈_{σ^{d}}(−x)) \\ +\frac{x}{2} ∑_{d=0}^{r}(𝔒_{π^{d}}(x) + 𝔒_{π^{d}}(−x) − 𝔒_{π^{d−1}}(x) − 𝔒_{π^{d−1}}(−x))(𝔒_{σ^{d}}(x) − 𝔒_{σ^{d}}(−x)) \\ +\frac{x}{2} ∑_{d=0}^{r}(𝔈_{π^{d}}(x) − 𝔈_{π^{d}}(−x) − 𝔈_{π^{d−1}}(x) + 𝔈_{π^{d−1}}(−x))(𝔒_{σ^{d}}(x) + 𝔒_{σ^{d}}(−x)) \\ +\frac{x}{2} ∑_{d=0}^{r}(𝔒_{π^{d}}(x) − 𝔒_{π^{d}}(−x) − 𝔒_{π^{d−1}}(x) + 𝔒_{π^{d−1}}(−x))(𝔈_{σ^{d}}(x) + 𝔈_{σ^{d}}(−x)). \end{matrix}

Proof. Using Propositions 2.1 and 2.2 together with Lemma 2.3 we get Equations 2.2-2.5. Rationalities of 𝔈_{τ} (x) and 𝔒_{τ} (x) for τ ≠ ∅ follows easily by induction. □

As a remark, the above theorem holds for the empty pattern without rationalities of 𝔈_{τ} (x) and 𝔒_{τ} (x).

Using Theorem 2.4 we get the main result of [MV2]. Corollary 2.5. (see Mansour and Vainshtein [MV2, Theorem 2.1]) For any nonempty pattern τ ∈ 𝔖_{k}(132), the generating function F_{τ} (x) is a rational function in x satisfying the relation

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

Proof. If adding Equations 2.2 and 2.3 we have

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

If adding Equations 2.4 and 2.5 we get

F_{τ} (x) + F_{τ} (−x) − 2 =

= \frac{x}{2} ∑_{d=0}^{r}(F_{π^{d}}(x) + F_{π^{d}}(−x) − F_{π^{d−1}}(x) − F_{π^{d−1}}(−x))(F_{σ^{d}}(x) − F_{σ^{d}}(−x))

+\frac{x}{2} ∑_{d=0}^{r}(F_{π^{d}}(x) − F_{π^{d}}(−x) − F_{π^{d−1}}(x) + F_{π^{d−1}}(−x))(F_{σ^{d}}(x) + F_{σ^{d}}(−x)).

equivalently,

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

Hence, if adding Equations 2.6 and 2.7 then we obtain that

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

Rationality of F_{τ} (x) for τ ≠ ∅ follows easily by rationalities of 𝔒_{τ} (x) and 𝔈_{τ} (x) (see Theorem 2.4 and Equation 2.1). □

Our present aim is to find explicitly the generating functions 𝔈_{τ} (x) and 𝔒_{τ} (x) for several cases of τ; thus we need the following notation. We denote the generating function 𝔈_{τ} (x) − 𝔒_{τ} (x) by 𝔐_{τ} (x) for any pattern τ. Theorem 2.6. For any τ ∈ 𝔖_{k}(132),

(2.8) 𝔐_{τ} (x) − 𝔐_{τ} (−x) = x ∑_{d=0}^{r}(𝔐_{π^{d}}(x) − 𝔐_{π^{d−1}}(x))𝔐_{σ^{d}}(x) + (𝔐_{π^{d}}(−x) − 𝔐_{π^{d−1}}(−x))𝔐_{σ^{d}}(−x),

and

(2.9) 𝔐_{τ} (x)+𝔐_{τ} (−x)−2 = x ∑_{d=0}^{r}(𝔐_{π^{d}}(x)−𝔐_{π^{d−1}}(x))𝔐_{σ^{d}}(−x)−(𝔐_{π^{d}}(−x)−𝔐_{π^{d−1}}(−x))𝔐_{σ^{d}}(x).

Proof. If subtracting Equation 2.3 from Equation 2.2 then we get Equation 2.8, and if subtracting Equation 2.5 from Equation 2.4 then we get Equation 2.9. □

Corollary 2.7. Let τ = (β, k) ∈ 𝔖_{k}(132). Then

𝔐_{τ} (x) = \frac{2(1 + x𝔐_{β}(−x))}{(1 − x𝔐_{β}(x))^{2} + (1 + x𝔐_{β}(−x))^{2}} .

Proof. Equation 2.8 for τ = (β, k) yields

(1 − x𝔐_{β}(x))𝔐_{τ} (x) − (1 + x𝔐_{β}(−x))𝔐_{τ} (−x) = 0,

and Equation 2.9 for τ = (β, k) yields

(1 + x𝔐_{β}(−x))𝔐_{τ} (x) + (1 − x𝔐_{β}(x))𝔐_{τ} (−x) = 2.

Hence, the rest is easy to check by the above two equations. □

Example 2.8. Let τ = 12 and β = 1. Since 𝔈_{β}(x) = 1 and 𝔒_{β}(x) = 0 we get that 𝔐_{β}(x) = 1. Corollary 2.7 for τ = 12 yields

𝔐_{12}(x) = 𝔈_{12}(x) − 𝔒_{12}(x) = \frac{2(1 + x)}{(1 − x)^{2} + (1 + x)^{2}} = \frac{1 + x}{1 + x^{2}} .

On the other hand, Corollary 2.5 together with Equation 2.1 we have

F_{12}(x) = 𝔈_{12}(x) + 𝔒_{12}(x) = \frac{1}{1 − x}.

Hence,

𝔈_{12}(x) = \frac{1 + x}{1 − x^{4}} and 𝔒_{12}(x) = \frac{x^{2}(1 + x)}{1 − x^{4}}.

2.1. Pattern τ = ∅. Let us consider the case τ = ∅ as the first case which examined by Simion and Schmidt [SimSch]. Theorem 2.9. We have

𝔈(x) = \frac{1}{2}(C(x) + 1) + \frac{x}{2}C(x^{2}) and 𝔒(x) = \frac{1}{2}(C(x) − 1) − \frac{x}{2}C(x^{2}).

In other words, for all n ≥ 1,

(1) |𝔈_{2n−2}(132)| = \frac{1}{2}C_{2n−2};
(2) |𝔒_{2n−2}(132)| = \frac{1}{2}C_{2n−2};
(3) |𝔈_{2n−1}(132)| = \frac{1}{2}(C_{2n−1} + C_{n−1});
(4) |𝔒_{2n−1}(132)| = \frac{1}{2}(C_{2n−1} − C_{n−1}).

Proof. First of all, let us define 𝔐(x) = 𝔐_{∅}(x), F(x) = F_{∅}(x), 𝔈(x) = 𝔈_{∅}(x), and 𝔒(x) = 𝔒_{∅}(x). Using the same arguments in the proof of Corollary 2.7 we get

\{ \begin{matrix}(1 − x𝔐(x))𝔐(x) − (1 + x𝔐(−x))𝔐(−x) = 0, \\ (1 + x𝔐(−x))𝔐(x) + (1 − x𝔐(x))𝔐(−x) = 2, \end{matrix}

therefore,

𝔐(x) = 𝔈(x) − 𝔒(x) = 1 + xC(x^{2}).

On the other hand, Corollary 2.5 for τ = ∅ yields F(x) = 1 + xF(x)^{2}, so by Equation 2.1 we have that

F(x) = 𝔈(x) + 𝔒(x) = C(x).

The rest is easy to check. □

2.2. Pattern τ = 12 … k. Let us start be the following example. Example 2.10. (see Simion and Schmidt [SimSch, Proposition 7]) Corollary 2.7 together with Example 2.8 yield

𝔐_{123}(x) = 1 + x.

On the other hand, using the fact that F_{123}(x) = 𝔈_{123}(x) + 𝔒_{123}(x) = \frac{1−x}{1−2x} (see [SimSch]) we get

𝔈_{123}(x) = 1 + x + \frac{x^{2}}{1 − 2x} and 𝔒_{123}(x) = \frac{x^{2}}{1 − 2x}.

The case of varying k is more interesting. As an extension of Example 2.10, let us consider the case τ = [k], where we define [k] = 12 … k. Theorem 2.11. For all k ≥ 1,

(i) 𝔈_{[2k−1]}(x) = \frac{1}{2}(R_{2k−1}(x) + xR_{k−1}(x^{2}) + 1) and 𝔈_{[2k]}(x) = \frac{1}{2} (R_{2k}(x) + \frac{(1 + xR_{k}(x^{2}))R_{k}(x^{2})}{1 + x^{2}R_{k}^{2}(x^{2})}),

(ii) 𝔒_{[2k−1]}(x) = \frac{1}{2}(R_{2k−1}(x) − xR_{k−1}(x^{2}) − 1) and 𝔒_{[2k]}(x) = \frac{1}{2} (R_{2k}(x) − \frac{(1 + xR_{k}(x^{2}))R_{k}(x^{2})}{1 + x^{2}R_{k}^{2}(x^{2})}).

Proof. We use induction on k. Using Example 2.8 we get that 𝔐_{1}(x) = 1 and 𝔐_{12}(x) = \frac{1+x}{1+x^{2}} . Now, let us fix k and assume that

𝔐_{[2k−1]}(x) = 1 + xR_{k−1}(x^{2}) and 𝔐_{[2k]}(x) = \frac{(1 + xR_{k}(x^{2}))R_{k}(x^{2})}{1 + x^{2}R_{k}^{2}(x^{2})}.

Therefore, by the hypothesis of the induction and Corollary 2.7 we get

\begin{matrix}𝔐_{[2k+1]} = \frac{2 (1 + \frac{x(1−xR_{k}(x^{2}))R_{k}(x^{2})}{1+x^{2}R_{k}^{2}(x^{2})})}{(1 − \frac{x(1+xR_{k}(x^{2}))R_{k}(x^{2})}{1+x^{2}R_{k}^{2}(x^{2})})^{2} + (1 + \frac{x(1−xR_{k}(x^{2}))R_{k}(x^{2})}{1+x^{2}R_{k}^{2}(x^{2})})^{2}} \\ = \frac{\frac{2(1+xR_{k}(x^{2}))}{1+x^{2}R_{k}^{2}(x^{2})}}{\frac{(1−xR_{k}(x^{2}))^{2}}{(1+x^{2}R_{k}^{2}(x^{2}))^{2}} + \frac{(1+xR_{k}(x^{2}))^{2}}{(1+x^{2}R_{k}^{2}(x^{2}))^{2}}} = 1 + xR_{k}(x^{2}). \end{matrix}

Also, by the induction hypothesis, Corollary 2.7, and Identity 1.2 we have that

𝔐_{[2k+2]} = \frac{2(1 + x(1 − xR_{k}(x^{2})))}{(1 − x(1 + xR_{k}(x^{2})))^{2} + (1 + x(1 − xR_{k}(x^{2})))^{2}}

= \frac{2 (x + \frac{1}{R_{k+1}(x^{2})})}{(\frac{1}{R_{k+1}(x^{2})} − x)^{2} + (\frac{1}{R_{k+1}(x^{2})} + x)^{2}}

= \frac{2(1 + xR_{k+1}(x^{2}))R_{k+1}(x^{2})}{(1 − xR_{k+1}(x^{2}))^{2} + (1 + xR_{k+1}(x^{2}))^{2}} = \frac{(1 + xR_{k+1}(x^{2}))R_{k+1}(x^{2})}{1 + x^{2}R_{k+1}^{2}(x^{2})}.

Hence, for all k ≥ 1,

𝔐_{[2k−1]}(x) = 1 + xR_{k−1}(x^{2}) and 𝔐_{[2k]}(x) = \frac{(1 + xR_{k}(x^{2}))R_{k}(x^{2})}{1 + x^{2}R_{k}^{2}(x^{2})}.

On the other hand, in [CW] (see also [MV1, Kr, MV2, MV4]) was proved

F_{[m]}(x) = 𝔈_{[m]}(x) + 𝔒_{[m]}(x) = R_{m}(x),

for all m ≥ 1. Hence, by the above two equations we get the desired result. □

Example 2.12. Theorem 2.11 for k = 3, 4, 5 yields e_{[5]}(n) − o_{[5]}(n) = \frac{1}{2} (1 + (−1)^{n+1});

e_{[7]}(n) − o_{[7]}(n) = \sqrt{2}^{n−5} (1 + (−1)^{n+1});
e_{[9]}(n) − o_{[9]}(n) = \frac{F_{n−3}}{2} (1 + (−1)^{n+1});

where F_{n−3} is the (n − 3)th Fibonacci number.

2.3. Pattern τ = 213 … k. Let us start by the following example. Example 2.13. (see Simion and Schmidt [SimSch, Proposition 7]) Corollary 2.7 for τ = 213 together with the fact that 𝔐_{21}(x) = 𝔈_{21}(x) = \frac{1}{1−x} and 𝔒_{21}(x) = 0 yield

𝔈_{213}(x) = \frac{(1 − x)(1 − 4x^{2} + 4x^{4})}{(1 − 2x)(1 − 3x^{2} + 4x^{4})}, 𝔒_{213}(x) = \frac{(1 − x)x^{2}}{(1 − 2x)(1 − 3x^{2} + 4x^{4})}.

The case of varying k is more interesting. As an extension of Example 2.13, by using Corollary 2.7, and induction on k (Similarly to Theorem 2.11) we get Theorem 2.14. For all k ≥ 1,

\begin{matrix}𝔐_{2134...(2k)}(x) = \frac{(1 + 2x) (U_{2k−1} (\frac{1}{2x}) − U_{2k} (\frac{1}{2x}) + \frac{x^{2}+2x−1}{1−3x^{2}})}{U_{2k} (\frac{1}{2x}) − 2xU_{2k+1} (\frac{1}{2x}) + \frac{4x^{4}}{1−3x^{2}}}, \\ 𝔐_{2134...(2k−1)}(x) = \frac{(1 + 2x) (U_{2k−2} (\frac{1}{2x}) − U_{2k−1} (\frac{1}{2x}) + \frac{x^{2}+2x−1}{1−3x^{2}})}{U_{2k−1} (\frac{1}{2x}) − 2xU_{2k} (\frac{1}{2x}) − \frac{2x(1−5x^{2})}{1−3x^{2}}}. \end{matrix}

By Theorem 2.14 together with use of the fact that F_{2134...k}(x) = R_{k}(x) (see [MV2, Theorem 2.6]) we get Corollary 2.15. For all k ≥ 1,

(i) 𝔈_{2134...(2k)}(x) = \frac{1}{2} [\frac{U_{2k−1}( \frac{1}{2\sqrt{x}} )}{\sqrt{x}U_{2k}( \frac{1}{2\sqrt{x}} )} + \frac{(1+2x)(U_{2k−1}(\frac{1}{2x})−U_{2k}(\frac{1}{2x})+ \frac{x^{2}+2x−1}{1−3x^{2}} )}{U_{2k}(\frac{1}{2x})−2xU_{2k+1}(\frac{1}{2x})+ \frac{4x^{4}}{1−3x^{2}}}];

(ii) 𝔒_{2134...(2k)}(x) = \frac{1}{2} [\frac{U_{2k−1}( \frac{1}{2\sqrt{x}} )}{\sqrt{x}U_{2k}( \frac{1}{2\sqrt{x}} )} − \frac{(1+2x)(U_{2k−1}(\frac{1}{2x})−U_{2k}(\frac{1}{2x})+ \frac{x^{2}+2x−1}{1−3x^{2}} )}{U_{2k}(\frac{1}{2x})−2xU_{2k+1}(\frac{1}{2x})+ \frac{4x^{4}}{1−3x^{2}}}];

(iii) 𝔈_{2134...(2k−1)}(x) = \frac{1}{2} [\frac{U_{2k−2}( \frac{1}{2\sqrt{x}} )}{\sqrt{x}U_{2k−1}( \frac{1}{2\sqrt{x}} )} + \frac{(1+2x)(U_{2k−2}(\frac{1}{2x})−U_{2k−1}(\frac{1}{2x})+ \frac{x^{2}+2x−1}{1−3x^{2}} )}{U_{2k−1}(\frac{1}{2x})−2xU_{2k}(\frac{1}{2x})− \frac{2x(1−5x^{2})}{1−3x^{2}}}];

(iv) 𝔒_{2134...(2k−1)}(x) = \frac{1}{2} [\frac{U_{2k−2}( \frac{1}{2\sqrt{x}} )}{\sqrt{x}U_{2k−1}( \frac{1}{2\sqrt{x}} )} − \frac{(1+2x)(U_{2k−2}(\frac{1}{2x})−U_{2k−1}(\frac{1}{2x})+ \frac{x^{2}+2x−1}{1−3x^{2}} )}{U_{2k−1}(\frac{1}{2x})−2xU_{2k}(\frac{1}{2x})− \frac{2x(1−5x^{2})}{1−3x^{2}}}].

2.4. Pattern (d + 1)(d + 2) … k12 … d. In this subsection we consider the case τ = [k, d] where [k, d] = (d + 1)(d + 2) … k12 … d. Following to Theorem 2.11, our present aim is to find explicitly the generating functions 𝔈_{τ} (x) and 𝔒_{τ} (x) where τ = [k, d]; thus we need to consider four cases either k even or odd, and either d even or odd. First of all, using Theorem 2.6 for τ = [k, d] we state the following fact. Lemma 2.16. Let k ≥ 2, 1 ≤ d ≤ k − 1, and τ = [k, d]. Then

\{ \begin{matrix}(1 + x𝔐_{[k−d−1]}(−x) − x𝔐_{[d]}(−x))𝔐_{τ} (x) + (1 − x𝔐_{[k−d−1]}(x) + x𝔐_{[d]}(x))𝔐_{τ} (−x) \\ = 2 + x𝔐_{[k−d−1]}(−x)𝔐_{[d]}(x) − x𝔐_{[k−d−1]}(x)𝔐_{[d]}(−x), \\ (1 − x𝔐_{[k−d−1]}(x) − x𝔐_{[d]}(x))𝔐_{τ} (x) − (1 + x𝔐_{[k−d−1]}(−x) + x𝔐_{[d]}(−x))𝔐_{τ} (−x) \\ = −x𝔐_{[k−d−1]}(x)𝔐_{[d]}(x) − x𝔐_{[k−d−1]}(−x)𝔐_{[d]}(−x). \end{matrix}

2.4.1. k and d are odd numbers. Now, we ready to consider the first case k and d are odd numbers. Theorem 2.17. Let 0 ≤ d ≤ k. Then

𝔐_{[2k+1,2d+1]}(x) = 1 + xR_{k}(x^{2}).

Proof. Theorem 2.11 yields 𝔐_{2k−2d−1}(x) = 1+xR_{k−d−1}(x^{2}) and 𝔐_{2d+1}(x) = 1+xR_{d}(x^{2}). Therefore, by use of Lemma 2.16 for τ = [2k + 1, 2d + 1] we get

\{ \begin{matrix}𝔐_{τ} (x) + 𝔐_{τ} (−x) = 2, \\ (1 − 2x − x^{2}R_{d}(x^{2}) − x^{2}R_{k−d−1}(x^{2}))𝔐_{τ} (x) − (1 + 2x − x^{2}R_{d}(x^{2}) − x^{2}R_{k−d−1}(x^{2}))𝔐_{τ} (−x) \\ = −2x − 2x^{3}R_{d}(x^{2})R_{k−d−1}(x^{2}), \end{matrix}

so,

𝔐_{τ} (x) = 1 + \frac{x(1 − x^{2}R_{d}(x^{2})R_{k−d−1}(x^{2}))}{1 − x^{2}(R_{d}(x^{2}) + R_{k−d−1}(x^{2}))}.

By using the following identities (see [MV2])

(2.10) 1 − x^{2}R_{p}(x^{2})R_{q}(x^{2}) = \frac{U_{p+q} (\frac{1}{2x})}{U_{p} (\frac{1}{2x}) U_{q} (\frac{1}{2x})} and 1 − x^{2}(R_{p}(x^{2}) + R_{q}(x^{2})) = \frac{xU_{p+q+1} (\frac{1}{2x})}{U_{p} (\frac{1}{2x}) U_{q} (\frac{1}{2x})},

we have

𝔐_{τ} (x) = 1 + \frac{U_{k−1} (\frac{1}{2x})}{U_{k} (\frac{1}{2x})},

and by Identity 1.1 we get the desired result. □

By Theorem 2.17 together with use of the equation F_{[k,d]}(x) = R_{k}(x) (see [MV2, Theorem 2.4]) we get Corollary 2.18. For all 0 ≤ d ≤ k,

𝔈_{[2k+1,2d+1]}(x) = \frac{1}{2}(R_{2k+1}(x) + xR_{k}(x^{2}) + 1) and 𝔒_{[2k+1,2d+1]}(x) = \frac{1}{2}(R_{2k+1}(x) − xR_{k}(x^{2}) − 1).

A comparison of Corollary 2.18 for values of d suggests that there should exist a bijection between the sets 𝔈_{n}(132, 2 … (2k + 1)1) and 𝔈_{n}(132, (2d + 2)(2d + 3) … (2k + 1)12 … (2d + 1)) for any d. However, we failed to produce such a bijection, and finding it remains a challenging open question.

2.4.2. k odd number and d even number. Now, let us consider the case where k odd number and d even number.

Theorem 2.19. Let 1 ≤ d ≤ k. Then

𝔐_{[2k+1,2d]}(x) = 1 + xR_{k}(x^{2}).

Proof. Let m = k − d; solving the system equations in Lemma 2.16 for τ = [2k + 1, 2d] together with use of Theorem 2.11 we get

𝔐_{[2k+1,2d]}(x) = 1 + \frac{x(R_{m}(x^{2}) + R_{d}(x^{2}) − R_{m}(x^{2})R_{d}(x^{2}))}{1 − x^{2}R_{m}(x^{2})R_{d}(x^{2})}.

Using Identities 2.10 we get the desired result. □

By Theorem 2.19 together with use of the equation F_{[k,d]}(x) = R_{k}(x) (see [MV2, Theorem 2.4]) we get

Corollary 2.20. For all 1 ≤ d ≤ k,

𝔈_{[2k+1,2d]}(x) = \frac{1}{2}(R_{2k+1} + 1 + xR_{k}(x^{2})) and 𝔒_{[2k+1,2d]}(x) = \frac{1}{2}(R_{2k+1} − 1 − xR_{k}(x^{2}).

A comparison of Corollary 2.18 with Corollary 2.20 suggests that there should exist a bijection between the sets 𝔈_{n}(132, 12 … (2k + 1)) and 𝔈_{n}(132, [2k + 1, d]) for any d. However, we failed to produce such a bijection, and finding it remains a challenging open question.

2.4.3. k even number and d odd number. Similarly as above subsections, we can consider the case where k even number and d odd number.

Theorem 2.21. Let 0 ≤ d ≤ k − 1 and m = k − d − 1. Then the generating function 𝔐_{[2k,2d+1]}(x) is given by

\frac{(1 − x^{2}(R_{m}(x^{2}) + R_{d}(x^{2})) + x(1 − x^{2}R_{m}(x^{2})R_{d}(x^{2})))(1 + x^{2}R_{m}(x^{2})R_{d}(x^{2}))}{1 − x^{2}(1 + R_{m}^{2}(x^{2}))(1 + x^{2}R_{m}^{2}(x^{2}))}.

By Theorem 2.21 together with use of the equation F_{[k,d]}(x) = R_{k}(x) (see [MV2, Theorem 2.4]) we get

Corollary 2.22. Let 0 ≤ d ≤ k − 1 and m = k − d − 1.

(i) The generating function 𝔈_{[2k,2d+1]}(x) is given by

\frac{1}{2} (R_{2k}(x) + \frac{(1 − x^{2}(R_{m}(x^{2}) + R_{d}(x^{2})) + x(1 − x^{2}R_{m}(x^{2})R_{d}(x^{2})))(1 + x^{2}R_{m}(x^{2})R_{d}(x^{2}))}{1 − x^{2}(1 + R_{m}^{2}(x^{2}))(1 + x^{2}R_{m}^{2}(x^{2}))}) .

(ii) The generating function 𝔒_{[2k,2d+1]}(x) is given by

\frac{1}{2} (R_{2k}(x) − \frac{(1 − x^{2}(R_{m}(x^{2}) + R_{d}(x^{2})) + x(1 − x^{2}R_{m}(x^{2})R_{d}(x^{2})))(1 + x^{2}R_{m}(x^{2})R_{d}(x^{2}))}{1 − x^{2}(1 + R_{m}^{2}(x^{2}))(1 + x^{2}R_{m}^{2}(x^{2}))}) .

2.4.4. k and d even numbers. Similarly as above subsections, we can consider the case where k and d even numbers. Theorem 2.23. Let 1 ≤ d ≤ k − 1 and m = k − d − 1. Then the generating function 𝔐_{[2k,2d]}(x) is given by

\frac{1}{x} − \frac{(1 − x^{2}(R_{m}(x^{2}) − R_{d}(x^{2})))(1 − x^{2}(R_{d}(x^{2}) + R_{m}(x^{2})) − x(1 − x^{2}R_{d}(x^{2})R_{m}(x^{2})))}{x + x^{3}(1 + x^{2}R_{d}^{2}(x^{2}))(1 − 2R_{m}(x^{2}) + x^{2}R_{m}^{2}(x^{2}))}.

By Theorem 2.23 together with use of the equation F_{[k,d]}(x) = R_{k}(x) (see [MV2, Theorem 2.4]) we get Corollary 2.24. Let 1 ≤ d ≤ k − 1 and m = k − d − 1.

(i) The generating function 𝔈_{[2k,2d+1]}(x) is given by

\frac{1}{2}(R_{2k}(x) + \frac{1}{x} − \frac{(1 − x^{2}(R_{m}(x^{2}) − R_{d}(x^{2})))(1 − x^{2}(R_{d}(x^{2}) + R_{m}(x^{2})) − x(1 − x^{2}R_{d}(x^{2})R_{m}(x^{2})))}{x + x^{3}(1 + x^{2}R_{d}^{2}(x^{2}))(1 − 2R_{m}(x^{2}) + x^{2}R_{m}^{2}(x^{2}))}.

(ii) The generating function 𝔒_{[2k,2d+1]}(x) is given by

\frac{1}{2}(R_{2k}(x)− \frac{1}{x} + \frac{(1 − x^{2}(R_{m}(x^{2}) − R_{d}(x^{2})))(1 − x^{2}(R_{d}(x^{2}) + R_{m}(x^{2})) − x(1 − x^{2}R_{d}(x^{2})R_{m}(x^{2})))}{x + x^{3}(1 + x^{2}R_{d}^{2}(x^{2}))(1 − 2R_{m}(x^{2}) + x^{2}R_{m}^{2}(x^{2}))}).

2.5. Wedge patterns. For a further generalization of the results in the pervious subsections, consider the following definition. 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 and 456378129 are wedge patterns. Evidently, [k, d] is a wedge pattern for any d. We say that τ ∈ 𝔖_{k} is an odd-wedge pattern if it a wedge pattern such that the length of (τ^{1}, ρ^{1}, …, τ^{p}, ρ^{p}) is given by odd number for all p = 1, 2, …, r. For example, 23145 and 34251 are odd-wedge patterns. Evidently, [2k + 1, d] is an odd-wedge pattern for any d. Theorem 2.25. 𝔐_{τ} (x) = 1 + xR_{k}(x^{2}) for any odd-wedge pattern τ ∈ 𝔖_{2k+1}(132).

Proof. We proceed by induction on r. If r = 1 then τ = [2k + 1, d] for some d, and the result is true by Theorems 2.17 and 2.19. For an arbitrary r > 1, τ looks like either

τ = (τ′, 2p + 2d + 2, 2p + 2d + 3, …, 2k + 1, 1, 2, …, 2d),

or

τ = (τ′, 2p + 2d + 3, 2p + 2d + 4, …, 2k + 1, 1, 2, …, 2d + 1),

for some d and p, where τ′ = (τ^{1}, ρ^{1}, …, τ^{r−1}, ρ^{r−1}).

The first case; τ′ contains 2p+1 elements and it is an odd-wedge pattern, so by induction 𝔐_{τ′}(x) = 1 + xR_{p}(x^{2}), so Corollary 2.7 gives

𝔐_{(τ′,2p+2d+2)}(x) = \frac{(1 + xR_{p+1}(x^{2}))R_{p+1}(x^{2})}{1 + x^{2}R_{p+1}^{2}(x^{2})},

and then

𝔐_{(τ′,2p+2d+2,2p+2d+3)}(x) = 1 + xR_{p+1}(x^{2}).

Therefore, by induction we have

𝔐_{(τ′,2p+2d+2,2p+2d+3,...,2k)}(x) = \frac{(1 + xR_{k−d}(x^{2}))R_{k−d}(x^{2})}{1 + x^{2}R_{k−d}^{2}(x^{2})}.

Hence, Theorem 2.6 for τ = (τ′, 2p + 2d + 2, 2p + 2d + 3, …, 2k + 1, 1, 2, …, 2d) yields (similarly as Theorem 2.19)

𝔐_{τ} (x) = 1 + \frac{x(R_{k−d}(x^{2}) + R_{d}(x^{2}) − R_{k−d}(x^{2})R_{d}(x^{2}))}{1 − x^{2}R_{k−d}(x^{2})R_{d}(x^{2})},

and using Identities 2.10 we have that 𝔐_{τ} (x) = 1 + xR_{k}(x^{2}).

The second case; similarly as the first case we have that

𝔐_{(τ′,2p+2d+3,2p+2d+4,...,2k)}(x) = 1 + xR_{k−d−1}(x^{2}).

Hence, Theorem 2.6 for τ = (τ′, 2p + 2d + 3, 2p + 2d + 4, …, 2k + 1, 1, 2, …, 2d + 1) yields (similarly as Theorem 2.17)

𝔐_{τ} (x) = 1 + \frac{x(1 − x^{2}R_{d}(x^{2})R_{k−d−1}(x^{2}))}{1 − x^{2}(R_{d}(x^{2}) + R_{k−d−1}(x^{2}))},

and using Identities 2.10 we have that 𝔐_{τ} (x) = 1 + xR_{k}(x^{2}). □

A comparison of Theorem 2.11 with Theorem 2.25 suggests that there should exist a bijection between the sets 𝔈_{n}(132, 12 … (2k + 1)) [respectively; 𝔒_{n}(132, 12 … (2k + 1))] and 𝔈_{n}(132, τ) [respectively; 𝔒_{n}(132, τ)] for any odd-wedge pattern τ. However, we failed to produce such a bijection, and finding it remains a challenging open question. Corollary 2.26. For any odd-wedge pattern τ ∈ 𝔖_{2k+1}(132),

𝔈_{τ} (x) = \frac{1}{2}(R_{2k+1}(x) + xR_{k}(x^{2}) + 1) and 𝔒_{τ} (x) = \frac{1}{2}(R_{2k+1}(x) − xR_{k}(x^{2}) − 1).

3. Containing a pattern exactly once

Let e_{τ;r}(n) [respectively; o_{τ;r}(n)] denote the number of even [respectively; odd] permutations in 𝔖_{n}(132) that contain τ ∈ 𝔖_{k}(132) exactly r times, and e_{τ;1}^{ρ}(n) [respectively; o_{τ;r}^{ρ}(n)] denote the number of even [respectively; odd] permutations in 𝔈_{n}(132, ρ) that contain τ ∈ 𝔖_{k}(132) exactly r times. We denote by 𝔈_{τ;r}(x) and 𝔈_{τ;r}^{ρ}(x) [respectively; 𝔒_{τ;r}(x) and 𝔒_{τ;r}^{ρ}(x)] the corresponding ordinary generating functions. Using the argument proof of Theorem 2.4 we get as follows. Theorem 3.1. For any τ = (τ^{0}, m_{0}, …, τ^{r}, m_{r}) be the canonical decomposition of nonempty τ ∈ S_{k}(132), then

(3.1)  \begin{matrix}𝔈_{τ;1}(x) − 𝔈_{τ;1}(−x) = x ∑_{d=0}^{r+1} 𝔈_{π^{d−1};1}^{π^{d}}(x)𝔈_{σ^{d};1}^{σ^{d−1}}(x) + 𝔈_{π^{d−1};1}^{π^{d}}(−x)𝔈_{σ^{d};1}^{σ^{d−1}}(−x)+ \\ +x ∑_{d=0}^{r+1} 𝔒_{π^{d−1};1}^{π^{d}}(x)𝔒_{σ^{d};1}^{σ^{d−1}}(x) + 𝔒_{π^{d−1};1}^{π^{d}}(−x)𝔒_{σ^{d};1}^{σ^{d−1}}(−x), \end{matrix}

(3.2)  \begin{matrix}𝔒_{τ;1}(x) − 𝔒_{τ;1}(−x) = x ∑_{d=0}^{r+1} 𝔈_{π^{d−1};1}^{π^{d}}(x)𝔒_{σ^{d};1}^{σ^{d−1}}(x) + 𝔈_{π^{d−1};1}^{π^{d}}(−x)𝔒_{σ^{d};1}^{σ^{d−1}}(−x)+ \\ +x ∑_{d=0}^{r+1} 𝔒_{π^{d−1};1}^{π^{d}}(x)𝔈_{σ^{d};1}^{σ^{d−1}}(x) + 𝔒_{π^{d−1};1}^{π^{d}}(−x)𝔈_{σ^{d};1}^{σ^{d−1}}(−x), \end{matrix}

(3.3)  \begin{matrix}𝔈_{τ;1}(x) + 𝔈_{τ;1}(−x) = \frac{x}{2} ∑_{d=0}^{r+1}(𝔈_{π^{d−1};1}^{π^{d}}(x) + 𝔈_{π^{d−1};1}^{π^{d}}(−x))(𝔒_{σ^{d};1}^{σ^{d−1}}(x) − 𝔒_{σ^{d};1}^{σ^{d−1}}(−x))+ \\ +\frac{x}{2} ∑_{d=0}^{r+1}(𝔒_{π^{d−1};1}^{π^{d}}(x) + 𝔒_{π^{d−1};1}^{π^{d}}(−x))(𝔈_{σ^{d};1}^{σ^{d−1}}(x) − 𝔈_{σ^{d};1}^{σ^{d−1}}(−x))+ \\ +\frac{x}{2} ∑_{d=0}^{r+1}(𝔈_{π^{d−1};1}^{π^{d}}(x) − 𝔈_{π^{d−1};1}^{π^{d}}(−x))(𝔈_{σ^{d};1}^{σ^{d−1}}(x) + 𝔈_{σ^{d};1}^{σ^{d−1}}(−x))+ \\ +\frac{x}{2} ∑_{d=0}^{r+1}(𝔒_{π^{d−1};1}^{π^{d}}(x) − 𝔒_{π^{d−1};1}^{π^{d}}(−x))(𝔒_{σ^{d};1}^{σ^{d−1}}(x) + 𝔒_{σ^{d};1}^{σ^{d−1}}(−x)), \end{matrix}

and

(3.4)  \begin{matrix}𝔒_{τ;1}(x) + 𝔒_{τ;1}(−x) = \frac{x}{2} ∑_{d=0}^{r+1}(𝔈_{π^{d−1};1}^{π^{d}}(x) + 𝔈_{π^{d−1};1}^{π^{d}}(−x))(𝔈_{σ^{d};1}^{σ^{d−1}}(x) − 𝔈_{σ^{d};1}^{σ^{d−1}}(−x))+ \\ +\frac{x}{2} ∑_{d=0}^{r+1}(𝔒_{π^{d−1};1}^{π^{d}}(x) + 𝔒_{π^{d−1};1}^{π^{d}}(−x))(𝔒_{σ^{d};1}^{σ^{d−1}}(x) − 𝔒_{σ^{d};1}^{σ^{d−1}}(−x))+ \\ +\frac{x}{2} ∑_{d=0}^{r+1}(𝔈_{π^{d−1};1}^{π^{d}}(x) − 𝔈_{π^{d−1};1}^{π^{d}}(−x))(𝔒_{σ^{d};1}^{σ^{d−1}}(x) + 𝔒_{σ^{d};1}^{σ^{d−1}}(−x))+ \\ +\frac{x}{2} ∑_{d=0}^{r+1}(𝔒_{π^{d−1};1}^{π^{d}}(x) − 𝔒_{π^{d−1};1}^{π^{d}}(−x))(𝔈_{σ^{d};1}^{σ^{d−1}}(x) + 𝔈_{σ^{d};1}^{σ^{d−1}}(−x)), \end{matrix}

Remark 3.2. Strictly speaking, Theorem 3.1, unlike Theorem 2.4, is not a recursion for 𝔈_{τ;1}(x) or 𝔒_{τ;1}(x), since it involves functions of type 𝔈_{τ;1}^{ρ}(x) and 𝔒_{τ;1}^{ρ}(x) (unless r = 0; see the next subsection). However, for these functions one can write further recursions involving similar objects. For example,

\begin{matrix}𝔈_{π^{j−1};1}^{pi^{j}}(x) − 𝔈_{π^{j−1};1}^{π^{j}}(−x) = x ∑_{i=0}^{j} 𝔈_{π^{i−1};1}^{π^{i}}(x)𝔈_{σ_{j−1}^{i};1}^{σ_{j−1}^{i−1}}(x) + 𝔈_{π^{i−1};1}^{π^{i}}(−x)𝔈_{σ_{j−1}^{i};1}^{σ_{j−1}^{i−1}}(−x)+ \\ +x ∑_{i=0}^{j} 𝔒_{π^{i−1};1}^{π^{i}}(x)𝔒_{σ_{j−1}^{i};1}^{σ_{j−1}^{i−1}}(x) + 𝔒_{π^{i−1};1}^{π^{i}}(−x)𝔒_{σ_{j−1}^{i};1}^{σ_{j−1}^{i−1}}(−x), \end{matrix}

and

\begin{matrix}𝔒_{π^{j−1};1}^{pi^{j}}(x) − 𝔒_{π^{j−1};1}^{π^{j}}(−x) = x ∑_{i=0}^{j} 𝔈_{π^{i−1};1}^{π^{i}}(x)𝔒_{σ_{j−1}^{i};1}^{σ_{j−1}^{i−1}}(x) + 𝔈_{π^{i−1};1}^{π^{i}}(−x)𝔒_{σ_{j−1}^{i};1}^{σ_{j−1}^{i−1}}(−x)+ \\ +x ∑_{i=0}^{j} 𝔒_{π^{i−1};1}^{π^{i}}(x)𝔈_{σ_{j−1}^{i};1}^{σ_{j−1}^{i−1}}(x) + 𝔒_{π^{i−1};1}^{π^{i}}(−x)𝔈_{σ_{j−1}^{i};1}^{σ_{j−1}^{i−1}}(−x), \end{matrix}

where σ_{j−1}^{i} is the ith suffix of π^{j−1}. Though we have not succeeded to write down a complete set of equations in the general case (for 𝔈_{τ}^{ρ}(x) and 𝔒_{τ}^{ρ}(x)), it is possible to do this in certain particular cases.

As a corollary of Theorem 3.1 we obtain the main result of [MV2]. Corollary 3.3. (see Mansour and Vainshtein [MV2, Theorem 3.1]) Let τ = (τ^{0}, m_{0}, …, τ^{r}, m_{r}) be the canonical decomposition of τ ∈ S_{k}(132), then for all r ≥ 0,

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

where G_{τ} (x) is the generating function for the number of permutations in 𝔖_{n}(132) containing τ exactly once, and G_{τ}^{ρ}(x) is the generating function for the number of permutations in 𝔖_{n}(132, ρ) containing τ exactly once.

Proof. If adding Equations 3.1 and 3.2 together with use of the fact that G_{τ}^{ρ}(x) = 𝔈_{τ}^{ρ}(x) + 𝔒_{τ}^{ρ}(x) for any τ and ρ, we get

(3.5)  G_{τ} (x) − G_{τ} (−x) = x ∑_{d=0}^{r+1} G_{π^{d−1}}^{π^{d}}(x)G_{σ^{d}}^{σ^{d−1}}(x) + G_{π^{d−1}}^{π^{d}}(−x)G_{σ^{d}}^{σ^{d−1}}(−x),

and if adding Equations 3.3 and 3.4 we have

(3.6)  G_{τ} (x) + G_{τ} (−x) = x ∑_{d=0}^{r+1} G_{π^{d−1}}^{π^{d}}(x)G_{σ^{d}}^{σ^{d−1}}(x) − G_{π^{d−1}}^{π^{d}}(−x)G_{σ^{d}}^{σ^{d−1}}(−x).

Hence, by adding the Equations 3.5 and 3.6 we get the desired result. □

Our present aim is to find explicitly the generating functions 𝔈_{τ;1}(x) and 𝔒_{τ;1}(x) for several patterns τ, thus we the following notations. We define 𝔐_{τ;r}(x) = 𝔈_{τ;r}(x) − 𝔒_{τ;r}(x) and 𝔐_{τ;r}^{ρ}(x) = 𝔈_{τ;r}^{ρ}(x) − 𝔒_{τ;r}^{ρ}(x) for any τ and ρ, and 𝔐_{∅;r}^{ρ}(x) = 𝔐_{ρ}(x) for any ρ.

Theorem 3.4. For any τ = (τ^{0}, m_{0}, …, τ^{r}, m_{r}) be the canonical decomposition of nonempty τ ∈ S_{k}(132), then

(3.7)  𝔐_{τ;1}(x) − 𝔐_{τ;1}(−x) = x ∑_{d=0}^{r+1} 𝔐_{π^{d−1};1}^{π^{d}}(x)𝔐_{σ^{d};1}^{σ^{d−1}}(x) + 𝔐_{π^{d−1};1}^{π^{d}}(−x)𝔐_{σ^{d};1}^{σ^{d−1}}(−x),

and

(3.8)  𝔐_{τ;1}(x) + 𝔐_{τ;1}(−x) = x ∑_{d=0}^{r+1} 𝔐_{π^{d−1};1}^{π^{d}}(x)𝔐_{σ^{d};1}^{σ^{d−1}}(−x) − 𝔐_{π^{d−1};1}^{π^{d}}(−x)𝔐_{σ^{d};1}^{σ^{d−1}}(x).

Proof. If subtracting Equation 3.2 from Equation 3.1 then we get Equation 3.7, and if subtracting Equation 3.4 from Equation 3.3 then we get Equation 3.8. □

3.1. Pattern τ = [k]. One can try to obtain results similar to Theorems 2.11, 2.14, and 2.17-2.23, but expressions involved become extremely cumbersome. So we just consider a simplest wedge pattern, which is the pattern [k]. Theorem 3.5. For all m ≥ 0,

(i) 𝔐_{[2m+1];1}(x) = \frac{x}{U_{m}^{2} (\frac{1}{2x})},

(ii) 𝔐_{[2m+2];1}(x) = \frac{x^{2}R_{m+1}^{2}(x^{2})}{(1 + x^{2}R_{m+1}^{2}(x^{2}))^{2}U_{m}^{2} (\frac{1}{2x})}(1 + 2xR_{m+1}(x^{2}) − x^{2}R_{m+1}^{2}(x^{2})).

Proof. Let τ = [k], then r = 0, and it follows from Theorem 3.4 that

(3.9)  \begin{matrix}𝔐_{[k];1}(x) − 𝔐_{[k];1}(−x) = x𝔐_{[k−1]}(x)𝔐_{[k];1}(x) + x𝔐_{[k−1]}(−x)𝔐_{[k];1}(−x) \\ +x𝔐_{[k−1];1}(x)𝔐_{[k]}(x) + x𝔐_{[k−1];1}(−x)𝔐_{[k]}(−x), \\ 𝔐_{[k];1}(x) + 𝔐_{[k];1}(−x) = x𝔐_{[k−1]}(x)𝔐_{[k];1}(−x) − x𝔐_{[k−1]}(−x)𝔐_{[k];1}(x) \\ +x𝔐_{[k−1];1}(x)𝔐_{[k]}(−x) − x𝔐_{[k−1];1}(−x)𝔐_{[k]}(x). \end{matrix}

Now, let us consider two cases either k = 2m or k = 2m + 1 as follows. (i) Let k = 2m, Equation 3.9 for k = 2m and Theorem 2.11 together with Identity 1.2 we get

(1 − xR_{m}(x^{2}))𝔐_{[2m];1}(x) − (1 + xR_{m}(x^{2}))𝔐_{[2m];1}(−x) =

= \frac{x(1 + xR_{m}(x^{2}))R_{m}^{2}(x^{2})}{1 + x^{2}R_{m}^{2}(x^{2})}𝔐_{[2m−1];1}(x) + \frac{x(1 − xR_{m}(x^{2}))R_{m}^{2}(x^{2})}{1 + x^{2}R_{m}^{2}(x^{2})}𝔐_{[2m−1];1}(−x)

(1 + xR_{m}(x^{2}))𝔐_{[2m];1}(x) + (1 − xR_{m}(x^{2}))𝔐_{[2m];1}(−x) =

= \frac{x(1 − xR_{m}(x^{2}))R_{m}^{2}(x^{2})}{1 + x^{2}R_{m}^{2}(x^{2})}𝔐_{[2m−1];1}(x) − \frac{x(1 + xR_{m}(x^{2}))R_{m}^{2}(x^{2})}{1 + x^{2}R_{m}^{2}(x^{2})}𝔐_{[2m−1];1}(−x).

If solving the above system of Equations, then using Identity 1.2 we have

(3.10) 𝔐_{[2m];1}(x) = \frac{xR_{m}^{2}(x^{2})}{(1 + x^{2}R_{m}^{2}(x^{2}))^{2}} ((1 − x^{2}R_{m}^{2}(x^{2}))𝔐_{[2m−1];1}(x) − 2xR_{m}(x^{2})𝔐_{[2m−1];1}(−x)).

(ii) Let k = 2m + 1, similarly as first case (i) we get

(3.11)  𝔐_{[2m+1];1}(x) = x((1 − x^{2}R_{m}^{2}(x^{2}))𝔐_{[2m];1}(x) − 2xR_{m}(x^{2})𝔐_{[2m];1}(−x)).

If using Equations 3.10 and 3.11, then we have that for m ≥ 1,

𝔐_{[2m+1];1}(x) = x^{2}R_{m}^{2}(x^{2})𝔐_{[2m−1];1}(x).

Besides, by definitions we have that 𝔐_{[1];1}(x) = x, hence 𝔐_{[2m+1];1}(x) = _{\frac{x}{U_{m}^{2}(\frac{1}{2x})}}. Using Equation 3.10

together with the property U_{p}^{2}(t) = U_{p}^{2}(−t) for all p, we get the desired result. □

Theorem 3.5 together with the fact that the generating function for the number permutations in 𝔖_{n}(132) containing [k] exactly once is given by _{\frac{1}{U_{k}^{2}( \frac{1}{2\sqrt{x}} )}} (see [MV1]) we have

Corollary 3.6. For all m ≥ 0,

(i) 𝔈_{[2m+1];1}(x) = \frac{1}{2} (_{\frac{1}{U_{2m+1}^{2}( \frac{1}{2\sqrt{x}} )}} + _{\frac{x}{U_{m}^{2}(\frac{1}{2x})}}),

(ii) 𝔒_{[2m+1];1}(x) = \frac{1}{2} (_{\frac{1}{U_{2m+1}^{2}( \frac{1}{2\sqrt{x}} )}} − _{\frac{x}{U_{m}^{2}(\frac{1}{2x})}}),

(iii) 𝔈_{[2m+2];1}(x) = \frac{1}{2} (_{\frac{1}{U_{2m+2}^{2}( \frac{1}{2\sqrt{x}} )}} + \frac{x^{2}R_{m+1}^{2}(x^{2})}{(1+x^{2}R_{m+1}^{2}(x^{2}))^{2}U_{m}^{2}(\frac{1}{2x})}(1 + 2xR_{m+1}(x^{2}) − x^{2}R_{m+1}^{2}(x^{2}))),

(iv) 𝔒_{[2m+2];1}(x) = \frac{1}{2} (_{\frac{1}{U_{2m+2}^{2}( \frac{1}{2\sqrt{x}} )}} − \frac{x^{2}R_{m+1}^{2}(x^{2})}{(1+x^{2}R_{m+1}^{2}(x^{2}))^{2}U_{m}^{2}(\frac{1}{2x})}(1 + 2xR_{m+1}(x^{2}) − x^{2}R_{m+1}^{2}(x^{2}))).

4. Furthermore results

In this section, we present several directions to generalize and to extend the results of the previous sections.

4.1. Statistics on the set 𝔈_{n}(132) and on the set 𝔒_{n}(132). The first of these directions is to consider statistics on the set 𝔈_{n}(132) (or on the set 𝔒_{n}(132)). First of all, let us define

F(x_{1}, x_{2}, …) = ∑_{n≥0} ∑_{π∈𝔖_{n}(132)} ∏_{j≥1} x_{j}^{12...j(π)},
𝔈(x_{1}, x_{2}, …) = ∑_{n≥0} ∑_{π∈𝔈_{n}(132)} ∏_{j≥1} x_{j}^{12...j(π)},
𝔒(x_{1}, x_{2}, …) = ∑_{n≥0} ∑_{π∈𝔒_{n}(132)} ∏_{j≥1} x_{j}^{12...j(π)},

where 12 … j(π) is the number occurrences of the pattern 12 … j in π. We denote the function 𝔈(x_{1}, x_{2}, …) − 𝔒(x_{1}, x_{2}, …) by 𝔐(x_{1}, x_{2}, …). Using the same arguments in the proof Corollary 2.7 together with the main result of [BCS] we get as follows. Theorem 4.1. We have

𝔐(x_{1}, x_{2}, …) = \frac{2(1 + x_{1}𝔐(−x_{1}x_{2}, x_{2}x_{3}, …))}{(1 − x_{1}𝔐(x_{1}x_{2}, x_{2}x_{3}, …))^{2} + (1 + x_{1}𝔐(−x_{1}x_{2}, x_{2}x_{3}, …))^{2}} ,

and

F(x_{1}, x_{2}, …) = 𝔈(x_{1}, x_{2}, …) + 𝔒(x_{1}, x_{2}, …) = \frac{1}{1 − x_{1}F(x_{1}x_{2}, x_{2}x_{3}, …)}.

An application for Theorem 4.1 we get the distribution of the number right to left maxima on the set 𝔈_{n}(132) or on the set 𝔒_{n}(132). Let π ∈ 𝔖_{n}; we say π_{j} is right to left maxima of π if π_{j} > π_{i} for all j < i. The number of right to left maxima of π we denote by rlm_{π}. Corollary 4.2. We have

(i) ∑_{n≥0} ∑_{π∈𝔈_{n}(132)} x^{n}y^{rlm_{π}} = \frac{1}{2} (\frac{1}{1 − xyC(x)} + \frac{1 + xy − x^{2}yC(x^{2})}{1 − 2x^{2}yC(x^{2}) + x^{2}y^{2}C(x^{2})}) ,

(ii) ∑_{n≥0} ∑_{π∈𝔒_{n}(132)} x^{n}y^{rlm_{π}} = \frac{1}{2} (\frac{1}{1 − xyC(x)} − \frac{1 + xy − x^{2}yC(x^{2})}{1 − 2x^{2}yC(x^{2}) + x^{2}y^{2}C(x^{2})}) .

Proof. Using Theorem 2.9 together with definitions we have 𝔐(x, 1, 1, …) = 1 + xC(x^{2}). So, Theorem 4.1 yields

𝔐(xy, y^{−1}, y, …) = 𝔈(xy, y^{−1}, y, …) − 𝔒(xy, y^{−1}, y, …) = \frac{1 + xy − x^{2}yC(x^{2})}{1 − 2x^{2}yC(x^{2}) + x^{2}y^{2}C(x^{2})},

and

F(xy, y^{−1}, y, y^{−1}, …) = 𝔈(xy, y^{−1}, y, y^{−1}, …) + 𝔒(xy, y^{−1}, y, y^{−1}, …) = \frac{1}{1 − xyC(x)}.

On the other hand, using [BCS, Proposition 5] we get

∑_{n≥0} ∑_{π∈𝔖_{n}(132)} x^{n}y^{rlm_{π}} = F(xy, y^{−1}, y, y^{−1}, …),

∑_{n≥0} ∑_{π∈𝔈_{n}(132)} x^{n}y^{rlm_{π}} = 𝔈(xy, y^{−1}, y, y^{−1}, …),

∑_{n≥0} ∑_{π∈𝔒_{n}(132)} x^{n}y^{rlm_{π}} = 𝔒(xy, y^{−1}, y, y^{−1}, …).

By combining all these equations we get the desired result. □

An another application for Theorem 4.1 we get an explicit expressions for the generating function ∑_{n≥0} ∑_{π∈𝔈_{n}(132)} x^{n}y^{12...k(π)} for given k and 12 … k(π). The following result is true by using Theorem 4.1. Theorem 4.3. Let k ≥ 1; we have

(i) 𝔐_{[2k+1];0}(x) = 1 + xR_{k}(x^{2}) = \frac{U_{k}(\frac{1}{2x})+U_{k−1}(\frac{1}{2x})}{U_{k}(\frac{1}{2x})};

(ii) 𝔐_{[2k+1];1}(x) = _{\frac{x}{U_{k}^{2}(\frac{1}{2x})}};

(iii) 𝔐_{[2k+1];2}(x) = \frac{x^{2}}{U_{k}^{2}(\frac{1}{2x})}(xR_{k}(x^{2}) − 1) = \frac{x^{2}(U_{k−1}(\frac{1}{2x})−U_{k}(\frac{1}{2x}))}{U_{k}^{3}(\frac{1}{2x})}.

Therefore, by [MV1, Theorem 4.1] together with the above theorem we get the number of even (or odd) permutations avoiding 132 and containing [2k + 1] exactly r = 0, 1, 2. For example, for r = 2 we get (for r = 1 see Corollary 3.6) Corollary 4.4. Let k ≥ 1. Then

(i) the generating function for the number 132-avoiding even permutations containing 12 … (2k +1) exactly twice is given by

\frac{1}{2} (\frac{\sqrt{x}U_{k−1} (\frac{1}{2\sqrt{x}})}{U_{k}^{3} (\frac{1}{2\sqrt{x}})} + \frac{x^{2}(U_{k−1} (\frac{1}{2x}) − U_{k} (\frac{1}{2x}))}{U_{k}^{3} (\frac{1}{2x})}) ,

(ii) the generating function for the number 132-avoiding odd permutations containing 12 … (2k +1) exactly twice is given by

\frac{1}{2} (\frac{\sqrt{x}U_{k−1} (\frac{1}{2\sqrt{x}})}{U_{k}^{3} (\frac{1}{2\sqrt{x}})} − \frac{x^{2}(U_{k−1} (\frac{1}{2x}) − U_{k} (\frac{1}{2x}))}{U_{k}^{3} (\frac{1}{2x})}) ,

4.2. Two restrictions. The second of these directions is to consider more than one additional restriction. For example, the following results is true. Let B_{τ^{1},τ^{2}}(x) be the generating function for the number of even permutations in 𝔈_{n}(132, τ^{1}, τ^{2}). Assume τ^{1} = 12 … k and τ^{2} = 2134 … k, then we get as follows. Theorem 4.5. Let V_{m}(x) = (1 − xW_{m}(x))W_{m+1}(x) such that

W_{m}(x) = \frac{(1 − x^{2}R_{m−2}(x)R_{m−3}(x))R_{m−1}(x)}{1 − x^{2}R_{m−1}(x)R_{m−2}(x)}.

Then, for all k ≥ 2,

(1) The generating function 𝔈_{12...2k,2134...2k}(x) is given by

\frac{1}{2} (W_{2k}(x) + 1 + xR_{k}(x^{2})) .

(2) The generating function 𝔒_{12...2k,2134...2k}(x) is given by

\frac{1}{2} (W_{2k}(x) − 1 − xR_{k}(x^{2})) .

(3) The generating function 𝔈_{12...(2k+1),2134...(2k+1)}(x) is given by

\frac{1}{2} (\frac{2(1 + xR_{k+1}(x^{2})) − V_{2k}(x) − xR_{k+1}(x^{2})V_{2k}(−x)}{1 + x^{2}R_{k+1}^{2}(x^{2})} · R_{k+1}(x^{2}) + W_{2k+1}(x)) .

(4) The generating function 𝔒_{12...(2k+1),2134...(2k+1)}(x) is given by

\frac{1}{2} (W_{2k+1}(x) − \frac{2(1 + xR_{k+1}(x^{2})) − V_{2k}(x) − xR_{k+1}(x^{2})V_{2k}(−x)}{1 + x^{2}R_{k+1}^{2}(x^{2})} · R_{k+1}(x^{2})) .

Another example to consider the case of avoiding τ^{1} and counting occurrences of τ^{2}. For example, the following result is true. Let 𝔈_{τ^{1}}^{τ^{2}}(x, y) [respectively; 𝔒_{τ^{1}}^{τ^{2}}(x, y)] be the generating function for the number of even [respectively; odd] permutations in 𝔖_{n}(132, τ^{2}) containing τ^{1} exactly r times.

Theorem 4.6. Let G_{k}(x, y) = 𝔈_{[k]}^{[k+1]}(x, y) − 𝔒_{[k]}^{[k+1]}(x, y). For all k ≥ 1,

G_{k}(x, y) = 1 + x\frac{D_{k−1}(x) − x^{k} + B_{k}(x)(1 − y) + x^{2}(D_{k−3}(x) − x^{k−2})(1 − y)^{2}}{D_{k}(x) + E_{k}(x)(1 − y) + x^{2}D_{k−2}(x)(1 − y)^{2}} ,

where E_{m}(x) = ((−1)^{m} − 1)x^{m+1}; B_{2m}(x) = −x^{2m−1} and B_{2m+1} = −x^{2m} + 2x^{2m+1}; and

\begin{matrix}D_{2m}(x) = \frac{x^{2m+1}}{1−4x^{2}} (U_{2m+1} (\frac{1}{2x}) − 2xU_{2m} (\frac{1}{2x}) − 2x), \\ D_{2m+1}(x) = \frac{x^{2m+3}}{1−4x^{2}} (U_{2m+3} (\frac{1}{2x}) − U_{2m+1} (\frac{1}{2x}) − 4x), \end{matrix}

for all m ≥ 0.

Acknowledgments. The final version of this paper was written while the author was visiting University of Haifa, Israel in January 2003. He thanks the HIACS Research Center and the Caesarea Edmond Benjamin de Rothschild Foundation Institute for Interdisciplinary Applications of Computer Science for financial support, and professor Alek Vainshtein for his generosity.

References

[BS] E. Babson and E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Séminaire Lotharingien de Combinatoire 44 (2000) Article B44b.

[Bo] M. Bóna, The permutation classes equinumerous to the smooth class, Electron. J. Combin. 5 (1998) #R31.

[BCS] P. Br”andén, A. Claesson, and E. Steingrímsson, Catalan continued fractions and increasing subsequences in permutations, Discr. Math. 258 (2002) 275–287.

[C] A. Claesson, Generalised pattern avoidance, European Journal of Combinatorics, 22 (2001) 961–973.

[Kn] D. Knuth, The Art of Computer Programming, vol. 1, Addison Wesley, Reading, MA, 1968.

[LS] V. Lakshmibai and B. Sandhya, Criterion for smoothness of Schubert varieties in Sl(n)/B, Proc. Indian Acad. Sci. 100 (1990) 45–52.

[Ta] R. Tarjan, Sorting using networks of queues and stacks, J. Assoc. Comput. Mach. 19 (1972) 341–346.

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

[GM1] O. Guibert and T. Mansour, Restricted 132-involutions and Chebyshev polynomials, Séminaire Lotharingien de Combinatoire 48 (2002) Article B48a.

[GM2] O. Guibert and T. Mansour, Some statistics on restricted 132 involutions, Annals of Combinatorics, to appear, Preprint CO/0206169.

[Km] D. Kremer, Permutations with forbidden subsequences and a generalized Schröder number, Discr. Math. 218 (2000) 121–130.

[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 5 (2001) 451–458.

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

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

[Ro] 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 continuous fractions Electron. J. Combin. 6 (1999) #R38.

[SimSch] R. Simion and F. Schmidt, Restricted permutations European J. Combin. 6 (1985) 383–406.

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