COUNTING OCCURRENCES OF 132 IN AN EVEN PERMUTATION

Toufik Mansour ^{1}

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

                        toufik@math.chalmers.se

Abstract

We study the generating function for the number of even (or odd) permutations on n letters containing exactly r ≥ 0 occurrences of a 132 pattern. It is shown that finding this function for a given r amounts to a routine check of all permutations in 𝔖_{2r}.

Nous tudions la fonction gnratrice pour le nombre de permutations paires (ou impaires) ayant n lettres contenant exactement r ≥ 0 occurrences du motif 132. Nous montrons que trouver cette fonction pour r donn revient vrifier une routine pour toutes les permutations dans 𝔖_{2r}.

2000 Mathematics Subject Classification: Primary 05A05, 05A15; Secondary 05C90

1. Introduction

Let [n] = {1, 2, …, n} and 𝔖_{n} denote the set of all permutations of [n]. We shall view permutations in 𝔖_{n} as words with n distinct letters in [n]. A pattern is a permutation σ ∈ 𝔖_{k}, and an occurrence of σ in a permutation π = π_{1}π_{2} ⋯ π_{n} ∈ 𝔖_{n} is a subsequence of π that is order equivalent to σ. For example, an occurrence of 132 is a subsequence π_{i}π_{j}π_{k} (1 ≤ i < j < k ≤ n) of π such that π_{i} < π_{k} < π_{j}. We denote by τ(π) the number of occurrences of τ in π, and we denote by s_{σ}^{r}(n) the number of permutations π ∈ 𝔖_{n} such that σ(π) = r.

In the last decade much attention has been paid to the problem of finding the numbers s_{σ}^{r}(n) for a fixed r ≥ 0 and a given pattern τ (see [1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 16, 17, 18, 19]). Most of the authors consider only the case r = 0, thus studying permutations avoiding a given pattern. Only a few papers consider the case r > 0, usually restricting themselves to patterns of length 3. Using two simple involutions (reverse and complement) on 𝔖_{n} it is immediate that with respect to being equidistributed, the six patterns of length three fall into the two classes {123, 321} and {132, 213, 231, 312}. Noonan [13] proved that

s_{123}^{1}(n) = \frac{3}{n}\binom{2n}{n − 3}.

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

A general approach to the problem was suggested by Noonan and Zeilberger [14]; they gave another proof of Noonan’s result, and conjectured that

s_{123}^{2}(n) = \frac{59n^{2} + 117n + 100}{2n(2n − 1)(n + 5)}\binom{2n}{n − 4}

and

s_{132}^{1}(n) = \binom{2n − 3}{n − 3}.

The first conjecture was proved by Fulmek [8] and the latter conjecture was proved by Bóna in [6]. A conjecture of Noonan and Zeilberger states that s_{σ}^{r}(n) is P -recursive in n for any r and τ. It was proved by Bóna [4] for σ = 132. Mansour and Vainshtein [11] suggested a new approach to this problem in the case σ = 132, which allows one to get an explicit expression for s_{132}^{r}(n) for any given r. More precisely, they presented an algorithm that computes the generating function ∑_{n≥0} s_{132}^{r}(n)x^{n} for any r ≥ 0. To get the result for a given r, the algorithm performs certain routine checks for each element of the symmetric group 𝔖_{2r}. The algorithm has been implemented in C and yields explicit results for 1 ≤ r ≤ 6.

Let π be any permutation. The number of inversions of π is given by i_{π} = |{(i, j) : π_{i} > π_{j}, i < j}|. The signature of π is given by sign(π) = (−1)^{i_{π}}. We say π is an even permutation (respectively; odd permutation) if sign(π) = 1 (respectively; sign(π) = −1). We denote by E_{n} (respectively; O_{n}) the set of all even (respectively; odd) permutations in 𝔖_{n}. Clearly, |E_{n}| = |O_{n}| = \frac{1}{2}n! for all n ≥ 2. The following lemma holds immediately by definitions.

Lemma 1.1. For any permutation π, sign(π) = (−1)^{21(π)}.

We denote by e_{σ}^{r}(n) (respectively; o_{σ}^{r}(n)) the number of even (respectively; odd) permutations π ∈ E_{n} (respectively; π ∈ O_{n}) such that σ(π) = r.

Apparently, for the first time the relation between even (odd) permutations and pattern avoidance problem was suggested by Simion and Schmidet in [16] for σ ∈ 𝔖_{3}. In particularly, Simion and Schmidt [16] proved that

e_{132}^{0}(n) = \frac{1}{2(n + 1)}\binom{2n}{n} + \frac{1}{n + 1}\binom{n − 1}{(n − 1)/2},

and

o_{132}^{0}(n) = \frac{1}{2(n + 1)}\binom{2n}{n} − \frac{1}{n + 1}\binom{n − 1}{(n − 1)/2}.

In this paper, as a consequence of [12], we suggest a new approach to this problem in the case of even (or odd) permutations where σ = 132, which allows one to get an explicit expression for e_{132}^{r}(n) for any given r. More precisely, we present an algorithm that computes the generating functions E_{r}(x) = ∑_{n≥0} e_{132}^{r}(n)x^{n} and O_{r}(x) = ∑_{n≥0} o_{132}^{r}(n)x^{n} for any r ≥ 0. To get the result for a given r, the algorithm performs certain routine checks for each element of the symmetric group 𝔖_{2r}. The algorithm has been implemented in C, and yields explicit results for 0 ≤ r ≤ 6.

2. Definitions and preliminary results

In this section, we recall the definitions and the preliminary results of counting occurrences of the pattern 132 in a permutation, see [12]. Then, as a consequence of these results, we get the preliminary results of counting occurrences of the pattern 132 in an even (odd) permutation.

To any π ∈ 𝔖_{n} we assign a bipartite graph G_{π} in the following way. The vertices in one part of G_{π}, denoted V_{1}, are the entries of π, and the vertices of the second part, denoted V_{3}, are the occurrences of 132 in π. Entry i ∈ V_{1} is connected by an edge to occurrence j ∈ V_{3} if i enters j. For example, let π = 57614283, then π contains 5 occurrences of 132, and the graph G_{π} is presented on Figure 1.

Figure 1. Graph G_{π} for π = 57614283

We denote by G_{π}^{n} the connected component of G_{π} containing the last entry n. Let π(i_{1}), …, π(i_{s}) be the entries of π belonging to G_{π}^{n}, and let σ = σ_{π} ∈ 𝔖_{s} be the corresponding pattern permutation. We say that π(i_{1}), …, π(i_{s}) is the kernel of π and denote it ker π and σ is called the shape of the kernel, or the kernel shape. Let s = s(σ_{π}) be the size of the kernel, and the number of occurrences of 132 in ker π is called the capacity of the kernel. For example, for π = 57614283 as above, the kernel equals 14283, its shape is 14253, the size equals 5, and the capacity equals 4. Theorem 2.1. (Mansour and Vainshtein [12, Theorem 1]) Let π ∈ 𝔖_{n} such that 132(π) = r, then the size of the kernel of π is at most 2r + 1.

We say that ρ is a kernel permutation if it is the kernel shape for some permutation π. Evidently ρ is a kernel permutation if and only if σ_{ρ} = ρ. Let ρ ∈ 𝔖_{s} be an arbitrary kernel permutation. We denote by 𝔖(ρ) the set of all the permutations of all possible sizes whose kernel shape equals ρ. For any π ∈ 𝔖(ρ) we define the kernel cell decomposition as follows. The number of cells in the decomposition equals s(s + 1). Let ker π = π(i_{1}), …, π(i_{s}); the cell C_{ml} = C_{ml}(π) for 1 ≤ l ≤ s + 1 and 1 ≤ m ≤ s is defined by C_{ml}(π) = (π(j_{1}), π(j_{2}), …, π(j_{d})) such that j_{p} ≠ j_{q} if and only if p ≠ q, and

{j_{1}, j_{2}, …, j_{d}} = {j : i_{l−1} < j < i_{l}, π(i_{ρ^{−1}(m−1)}) < π(j) < π(i_{ρ^{−1}(m)})},

where i_{0} = 0, i_{s+1} = n + 1, ρ^{−1}(0) = 0, and π(0) = 0 for any π. If π coincides with ρ itself, then all the cells in the decomposition are empty. An arbitrary permutation in 𝔖(ρ) is obtained by filling in some of the cells in the cell decomposition. A cell C is called infeasible if the existence of an entry a ∈ C would imply an occurrence of 132 that contains a and two other entries x, y ∈ ker π′ for some π′. Clearly, all infeasible cells are empty for any π ∈ 𝔖(ρ). All the remaining cells are called feasible; a feasible cell may, or may not, be empty. Consider the permutation π = 67382451. The kernel of π equals 3845, its shape is 1423. The cell decomposition of π contains four feasible cells: C_{13} = (2), C_{14} = ∅, C_{15} = (1), and C_{41} = (6, 7) (see Figure 2). All the other cells are infeasible; for example, C_{32} is infeasible, since if a ∈ C_{32}, then aπ′(i_{2})π′(i_{4}) is an occurrence of 132 for some ker π′.

Figure 2. Kernel cell decomposition for π = 67382451 ∈ 𝔖(1423)

As another example, permutation π̃ = 11 10 7 12 4 6 5 8 2 9 3 1 belongs to 𝔖(364152). Its kernel is 7 12 8 2 9 3, and the feasible cells are C_{33} = (4, 6, 5), C_{17} = (1), C_{61} = (11, 10).

Given a cell C_{ij} in the kernel cell decomposition, all the kernel entries can be positioned with respect to C_{ij}. We say that x = π(i_{k}) ∈ ker π lies below C_{ij} if ρ(k) < i, and above C_{ij} if ρ(k) ≥ i. Similarly, x lies to the left of C_{ij} if k < j, and to the right of C_{ij} if k ≥ j. As usual, we say that x lies to the southwest of C_{ij} if it lies below C_{ij} and to the left of it; the other three directions, northwest, southeast, and northeast, are defined similarly. Let us define a partial order ≺ on the set of all feasible cells by saying that C_{ml} ≺ C_{m′l′} ≠ C_{ml} if m ≥ m′ and l ≤ l′. Theorem 2.2. (Mansour and Vainshtein [12])

(i) ≺ is a linear order.

(ii) Let C_{ml} and C_{ml′} be two nonempty feasibly cells such that l < l′. Then for any pair of entries a ∈ C_{ml}, b ∈ C_{ml′}, one has a > b.

(iii) Let C_{ml} and C_{m′l} be two nonempty feasibly cells such that m < m′. Then any entry a ∈ C_{ml} lies to the right of any entry b ∈ C_{m′l} (π^{−1}(b) < π^{−1}(a)).

Let π be any permutation with a kernel permutation ρ, and assume that the feasible cells of the kernel cell decomposition associated with ρ are ordered linearly according to ≺, C^{1}, C^{2}, …, C^{f(ρ)}. Let d_{j} be the size of C^{j}. For example, let π = 67382451 with kernel permutation ρ = 1423, as on Figure 2, then d_{1} = 2, d_{2} = 1, d_{3} = 0, and d_{4} = 1. We denote by l_{j}(ρ) the number of the entries of ρ that lie to the north-west from C^{j} or lie to the south-east from C^{j}. For example, let ρ = 1423, as on Figure 2, then l_{1}(ρ) = 3, l_{2}(ρ) = 2, l_{3}(ρ) = 3, and l_{4}(ρ) = 4. Clearly, l_{1}(ρ) = s(ρ) − 1 and l_{f(ρ)} = s(ρ) for any nonempty kernel permutation ρ. We denote by sign(C^{j}) the number of occurrences of a 21 pattern in C^{j}. Lemma 2.3. For any permutation π with a kernel permutation ρ,

sign(π) = (−1)^{(∑_{1≤i≤j≤f(ρ)} d_{i}d_{j}+∑_{j=1}^{f(ρ)} d_{j}l_{j}(ρ))} · sign(ρ) · ∏_{j=1}^{f(ρ)} sign(C^{j}).

Proof. To verify this formula, let us count the number of occurrences of the pattern 21 in π. There four possibilities for an occurrence of 21 in π. The first possibility is an occurrence occurs in one of the cells C^{j}, so in this case there are ∑_{j=1}^{f(ρ)} 21(C^{j}) occurrences. The second possibility is an occurrence occurs in ker π, so there are 21(ρ) occurrences. The third possibility is an occurrence of two elements which the first belongs to ker π and the second belongs to C^{i}, so there are ∑_{j=1}^{f(ρ)} d_{j}l_{j}(ρ) (see Theorem 2.2) occurrences. The fourth possibility is an occurrence of two elements which the first belongs to C^{i} and the second belongs to C^{j} where i < j (Theorem 2.2 yields every entry of C^{i} is greater than every entry of C^{j} for all i < j), so there are ∑_{1≤i<j≤f(ρ)} d_{i}d_{j} occurrences. Therefore, by Lemma 1.1 we have

sign(π) = (−1)^{∑_{j=1}^{f(ρ)} 21(C^{j})}(−1)^{21(ρ)}(−1)^{∑_{j=1}^{f(ρ)} d_{j}l_{j}(ρ)}(−1)^{∑_{1≤i<j≤f(ρ)} d_{i}d_{j}},

equivalently, sign(π) = (−1)^{(∑_{1≤i≤j≤f(ρ)} d_{i}d_{j}+∑_{j=1}^{f(ρ)} d_{j}l_{j}(ρ))} · sign(ρ) · ∏_{j=1}^{f(ρ)} sign(C^{j}). □

We say the vector v = (v_{1}, v_{2}, …, v_{n}) is a binary vector if v_{i} ∈ {0, 1} for all i, 1 ≤ i ≤ n. We denote the set of all binary vectors of length n by B^{n}. For any v ∈ B^{n}, we define |v| = v_{1} + v_{2} + ⋯ + v_{n}. For example, B^{2} = {(0, 0), (0, 1), (1, 0), (1, 1)} and |(1, 1, 0, 0, 1)| = 3.

Let ρ be any kernel permutations; we denote by X_{a}(ρ) (respectively; Y_{a}^{ρ}) the set of all the binary vectors v ∈ B^{f(ρ)} such that (−1)^{|v|+s(ρ)} = a (respectively; (−1)^{|v|} = a). For any v ∈ B^{f(ρ)}, we define

z_{ρ}(v) = (−1)^{∑_{1≤i<j≤f(ρ)} v_{i}v_{j}+∑_{j=1}^{f(ρ)} l_{j}(ρ)v_{j}}sign(ρ).

Letting ρ be any kernel permutations and v = (v_{1}, v_{2}, …, v_{f(ρ)}) ∈ B^{f(ρ)}, we denote by 𝔖(ρ; v) the set of all permutations of all sizes with kernel permutation ρ such that the corresponding cells C^{j} satisfy (−1)^{d_{j}} = (−1)^{v_{j}}; in such a context v is called a length argument vector of ρ. By definitions, the following result holds immediately. Lemma 2.4. For any kernel permutation ρ,

𝔖(ρ) = ⋃_{v∈B^{f(ρ)}} 𝔖(ρ; v).

Letting ρ be any kernel permutations and letting

v = (v_{1}, v_{2}, …, v_{f(ρ)}), u = (u_{1}, u_{2}, …, u_{f(ρ)}) ∈ B^{f(ρ)},

we denote by 𝔖(ρ; v, u) the set of all permutations in 𝔖(ρ; v) such that the corresponding cells C^{j} satisfy sign(C^{j}) = 1 if and only if u_{j} = 0; in such a context u is called a signature argument vector of ρ. By Lemma 2.4, the following result holds immediately. Lemma 2.5. For any kernel permutation ρ,

𝔖(ρ) = ⋃_{v∈B^{f(ρ)}} 𝔖(ρ; v) = ⋃_{v∈B^{f(ρ)}} ⋃_{u∈B^{f(ρ)}} 𝔖(ρ; v, u).

For any a, b ∈ {0, 1} we define

H_{r}(a, b) = \{ \begin{matrix}\frac{1}{2}(E_{r}(x) + (−1)^{a}E_{r}(−x)), & if b = 0 \\ \frac{1}{2}(O_{r}(x) + (−1)^{a}O_{r}(−x)), & if b = 1 \end{matrix} .

By definitions, the following result holds immediately. Lemma 2.6. Let a, b ∈ {0, 1}. Then the generating function for all permutations π such that 132(π) = r, (−1)^{|π|} = (−1)^{a}, and sign(π) = (−1)^{b} is given by H_{r}(a, b), where we denote by |π| the length of the permutation π.

3. Main Theorem

The main result of this note can be formulated as follows. Denote by K the set of all kernel permutations, and by K_{t} the set of all kernel shapes for permutations in 𝔖_{t}. Letting ρ be any kernel permutation, for any a, b ∈ {0, 1} and any r_{1}, …, r_{f(ρ)}, we define

L_{r_{1},...,r_{f(ρ)}}^{ρ}(a, b) = ∑_{v∈X_{(−1)^{a}}^{ρ}} ∑_{u∈Y_{(−1)^{b}zρ(v)}^{ρ}} ∏_{j=1}^{f(ρ)} H_{r_{j}}(v_{j}, u_{j}).

Remark 3.1. The product ∏_{j=1}^{s} H_{r_{j}}(v_{j}, u_{j}) gives the generating function for the number of s permutations π^{1}, …, π^{s} such that π^{j} contains 132 exactly r_{j} times, the modulo 2 of the length of π^{j} is v_{j}, and π^{j} is even (respectively; odd) permutation if and only if u_{j} = 1 (respectively; u_{j} = 0). Theorem 3.2. Let r ≥ 1. For any a, b ∈ {0, 1},

(3.1)  H_{r}(a, b) = ∑_{ρ∈K_{2r+1}} ∑_{r_{1}+···+r_{f(ρ)}=r−c(ρ), r_{j}≥0} L_{r_{1},...,r_{f(ρ)}}^{ρ}(a, b).

Proof. Let us fix a kernel permutation ρ ∈ K_{2r+1}, a length argument vector v = (v_{1}, …, v_{f(ρ)}) ∈ X_{(−1)^{a}}(ρ), and a signature argument vector u = (u_{1}, …, u_{f(ρ)}) ∈ Y_{(−1)^{b}z_{ρ}(v)}^{f(ρ)}. Recall that the kernel ρ of any π contains exactly c(ρ) occurrences of 132. The remaining r − c(ρ) occurrences of 132 are distributed among the feasible cells of the kernel cell decomposition of π. By Theorem 2.2, each occurrence of 132 belongs entirely to one feasible cell, and the occurrences of 132 in different cells do not influence one another.

Let π be any permutation such that 132(π) = r, sign(π) = (−1)^{b} and (−1)^{|π|} = (−1)^{a} together with a kernel permutations ρ, length argument vector v, and signature argument vector u. Then by Lemma 2.5, the cells C^{j} satisfy the following conditions:

(1) v_{j} = 0 if and only if d_{j} is an even number,

(2) u_{j} = 0 if and only if sign(C^{j}) = 1,

(3) (−1)^{v_{1}+...+v_{f(ρ)}+s(ρ)} = (−1)^{a}, and

(4) (−1)^{u_{1}+...+u_{f(ρ)}}z_{ρ}(v) = (−1)^{b}.

Therefore, by Remark ?? and Lemma 2.6 this contribution gives

x^{s(ρ)} ∑_{r_{1}+···+r_{f(ρ)}=r−c(ρ), r_{j}≥0} ∏_{j=1}^{f(ρ)} H_{r_{j}}(v_{j}, u_{j}).

Hence by Lemma 2.5 and Theorem 2.1, if summing over all the kernel permutations ρ ∈ K_{2r+1}, length argument vectors v ∈ X_{(−1)^{a}}(ρ), and signature argument vectors u ∈ Y_{(−1)^{b}z_{ρ}(v)}^{f(ρ)} then we get the desired result. □

Proposition 3.3. (see Mansour and Vainshtein [12, Proposition]) The only kernel permutation of capacity r ≥ 1 and size 2r + 1 is

ρ = 2r − 1, 2r + 1, 2r − 3, 2r, …, 2r − 2j − 3, 2r − 2j, …, 1, 4, 2.

Theorem 3.2 provides a finite algorithm for finding E_{r}(x) and O_{r}(x) for any given r ≥ 0, since we only have to consider all permutations in 𝔖_{2r+1}, and to perform certain routine operations with all shapes found so far. Moreover, the amount of search can be decreased substantially due to the following theorem. Theorem 3.4. The only kernel permutation of capacity r ≥ 1 and size 2r + 1 is

ρ = 2r − 1, 2r + 1, 2r − 3, 2r, …, 2r − 2j − 3, 2r − 2j, …, 1, 4, 2.

Its parameters are given by s(ρ) = 2r + 1, c(ρ) = r, f(ρ) = r + 2, sign(ρ) = −1, and z_{ρ}(v_{1}, …, v_{r+2}) = (−1)^{(1+v_{r+2}+∑_{1≤i<j≤r+2} v_{i}v_{j})}.

Proof. The first part of the proposition holds by Proposition 3.3. Besides, by using the form of ρ we get s(ρ) = 2r + 1, c(ρ) = r, f(ρ) = r + 2; sign(ρ) = −1, and l_{j}(ρ) = 2r for all j = 1, 2, …, r + 1 and l_{r+2}(ρ) = 2r + 1. Therefore, z_{ρ}(v_{1}, …, v_{r+2}) = (−1)^{(1+v_{r+2}+∑_{1≤i<j≤r+2} v_{i}v_{j})}. □

By this proposition, it suffices to search only permutations in 𝔖_{2r}. Below we present several explicit calculations.

3.1. The case r = 0. Let us start from the case r = 0. Observe that Theorem 3.2 remains valid for r = 0, provided the left hand side of Equation 3.1 for a = b = 0 is replaced by H_{r}(0, 0) − 1 = \frac{1}{2}(E_{r}(x) + E_{r}(−x)) − 1; subtracting 1 here accounts for the empty permutation. So, we begin with finding kernel shapes for all permutations in 𝔖_{1}. The only shape obtained is ρ_{1} = 1, and it is easy to see that s(ρ_{1}) = 1, c(ρ_{1}) = 0, f(ρ_{1}) = 2,

X_{1}(ρ_{1}) = Y_{−1} = {(1, 0), (0, 1)}, X_{−1}(ρ_{1}) = Y_{1} = {(0, 0), (1, 1)},

and

z_{ρ_{1}}(0, 0) = z_{ρ_{1}}(1, 0) = z_{ρ_{1}}(1, 1) = −z_{ρ_{1}}(0, 1) = 1.

Therefore, Equation 3.1 for a = b = 0 gives (3.2)

\begin{matrix}\frac{1}{2}(E_{0}(x) + E_{0}(−x)) − 1 = \\ = xH_{0}(1, 0)H_{0}(0, 0) + xH_{0}(1, 1)H_{0}(0, 1) + xH_{0}(1, 0)H_{0}(0, 1) + xH_{0}(1, 1)H_{0}(0, 0), \end{matrix}

Equation 3.1 for a = 1 and b = 0 gives

(3.3)  \frac{1}{2}(E_{0}(x) − E_{0}(−x)) = xH_{0}^{2}(0, 0) + xH_{0}^{2}(0, 1) + xH_{0}^{2}(1, 0) + xH_{0}^{2}(1, 1),

Equation 3.1 for a = 0 and b = 1 gives (3.4)

\begin{matrix}\frac{1}{2}(O_{0}(x) + O_{0}(−x)) = \\ = xH_{0}(1, 1)H_{0}(0, 0) + xH_{0}(1, 0)H_{0}(0, 1) + xH_{0}(0, 0)H_{0}(1, 0) + xH_{0}(0, 1)H_{0}(1, 1), \end{matrix}

and Equation 3.1 for a = b = 1 gives

(3.5)  \frac{1}{2}(O_{0}(x) − O_{0}(−x)) = 2xH_{0}(0, 1)H_{0}(0, 0) + 2xH_{0}(1, 1)H_{0}(1, 0).

Our present aim to find explicitly E_{0}(x) and O_{0}(x), thus we need the following notation. We define

M_{r}(x) = E_{r}(x) − O_{r}(x) and F_{r}(x) = E_{r}(x) + O_{r}(x)

for all r ≥ 0. Clearly,

\begin{matrix}H_{r}(0, 0) − H_{r}(0, 1) = \frac{1}{2}(M_{r}(x) + M_{r}(−x)), H_{r}(0, 0) + H_{r}(0, 1) = \frac{1}{2}(F_{r}(x) + F_{r}(−x)), \\ H_{r}(1, 0) − H_{r}(1, 1) = \frac{1}{2}(M_{r}(x) − M_{r}(−x)), H_{r}(1, 0) + H_{r}(1, 1) = \frac{1}{2}(F_{r}(x) − F_{r}(−x)), \end{matrix}

for all r ≥ 0. Therefore, by subtracting (respectively; adding) Equation 3.4 and Equation 3.2, and by subtracting (respectively; adding) Equation 3.5 and Equation 3.3 we get

\{ \begin{matrix}M_{0}(x) + M_{0}(−x) = 2 \\ M_{0}(x) − M_{0}(−x) = x(M_{0}^{2}(x) + M_{0}^{2}(−x)) \end{matrix}

and

\{ \begin{matrix}F_{0}(x) + F_{0}(−x) = 2 + x(F_{0}^{2}(x) − F_{0}^{2}(−x)) \\ F_{0}(x) − F_{0}(−x) = x(F_{0}^{2}(x) + F_{0}^{2}(−x)). \end{matrix}

Hence,

M_{0}(x) = 1 + \frac{1 − \sqrt{1 − 4x^{2}}}{2x} and F_{0}(x) = \frac{1 − \sqrt{1 − 4x}}{2x}.

Theorem 3.5. (i) The generating function for the number of even permutations avoiding 132 is given by (see [16])

E_{0}(x) = \frac{1}{2} (\frac{1 − \sqrt{1 − 4x}}{2x} + 1 + \frac{1 − \sqrt{1 − 4x^{2}}}{2x} ) .

(ii) The generating function for the number of odd permutations avoiding 132 is given by (see [16])

O_{0}(x) = \frac{1}{2} (\frac{1 − \sqrt{1 − 4x}}{2x} − 1 − \frac{1 − \sqrt{1 − 4x^{2}}}{2x} ) .

(iii) The generating function for the number of permutations avoiding 132 is given by (see [9])

F_{0}(x) = \frac{1 − \sqrt{1 − 4x}}{2x}.

3.2. The Case r = 1. Since permutations in 𝔖_{2} do not exhibit kernel shapes distinct from ρ_{1}, the only possible new shape is the exceptional one, ρ_{2} = 132. Calculation of the parameters of ρ_{2} gives s(ρ_{2}) = 3, c(ρ_{2}) = 1, f(ρ_{2}) = 3,

\begin{matrix}X_{1}(ρ_{2}) = Y_{−1} = \{(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1)\}, \\ X_{−1}(ρ_{2}) = Y_{1} = \{(0, 0, 0), (1, 1, 0), (1, 0, 1), (1, 1, 0)\}, \end{matrix}

and

\begin{matrix}z_{ρ_{2}}(0, 0, 0) = z_{ρ_{2}}(1, 0, 0) = z_{ρ_{2}}(0, 1, 0) = −z_{ρ_{2}}(1, 1, 0) = 1, \\ −z_{ρ_{2}}(0, 0, 1) = z_{ρ_{2}}(1, 0, 1) = z_{ρ_{2}}(0, 1, 1) = z_{ρ_{2}}(1, 1, 1) = 1. \end{matrix}

Therefore, by Theorem 3.2 we have

\{ \begin{matrix}2(H_{1}(0, 0) − H_{1}(0, 1)) = \\ = M_{1}(x) + M_{1}(−x) = \frac{x^{3}}{2} (M_{0}(−x) − M_{0}(x))(M_{0}^{2}(−x) + M_{0}^{2}(x)) \\ 2(H_{1}(1, 0) − H_{1}(1, 1)) = \\ = M_{1}(x) − M_{1}(−x) = 2x(M_{0}(x)M_{1}(x) + M_{0}(−x)M_{1}(−x)) \\ −\frac{x^{3}}{2} (M_{0}(−x) + M_{0}(x))(M_{0}^{2}(−x) + M_{0}^{2}(x))), \end{matrix}

Using the expression for M_{0}(x) (see the case r = 0) we get

M_{1}(x) = \frac{1}{2}(−1 + 3x + 2x^{2}) + \frac{1 − 3x − 4x^{2} + 4x^{3}}{2} (1 − 4x^{2})^{−1/2}.

Similarly, if considering the expressions for H_{1}(0, 0) + H_{1}(0, 1) and H_{1}(1, 0) + H_{1}(1, 1) we get

F_{1}(x) = \frac{1}{2}(x − 1) + \frac{1 − 3x}{2}(1 − 4x)^{−1/2}.

Theorem 3.6. (i) The generating function for the number of even permutations containing 132 exactly once is given by

E_{1}(x) = −\frac{1}{2}(1 − 2x − x^{2}) + \frac{1 − 3x}{4}(1 − 4x)^{−1/2} + \frac{1 − 3x − 4x^{2} + 4x^{3}}{4} (1 − 4x^{2})^{−1/2}.

(ii) The generating function for the number of odd permutations containing 132 exactly once is given by

O_{1}(x) = −\frac{1}{2}(x + x^{2}) + \frac{1 − 3x}{4}(1 − 4x)^{−1/2} − \frac{1 − 3x − 4x^{2} + 4x^{3}}{4} (1 − 4x^{2})^{−1/2}.

(iii) The generating function for the number of permutations containing 132 exactly once is given by (see [6])

F_{1}(x) = \frac{1}{2}(x − 1) + \frac{1 − 3x}{2}(1 − 4x)^{−1/2}.

3.3. The case r = 2. We have to check the kernel shapes of permutations in 𝔖_{4}. Exhaustive search adds four new shapes to the previous list; these are 1243, 1342, 1423, and 2143; besides, there is the exceptional 35142 ∈ 𝔖_{5}. Calculation of the parameters s, c, f, z, X_{a}, Y_{a} is straightforward, and we get Theorem 3.7. (i) The generating function for the number of even permutations containing 132 exactly twice is given by

\begin{matrix}E_{2}(x) = \frac{1}{2}x(x^{3} + 3x^{2} − 4x − 1) + \frac{1}{4}(2x^{4} − 4x^{3} + 29x^{2} − 15x + 2)(1 − 4x)^{−3/2} \\ −\frac{1}{4}(16x^{7} − 48x^{6} − 76x^{5} + 64x^{4} + 36x^{3} − 21x^{2} − 5x + 2)(1 − 4x^{2})^{−3/2}. \end{matrix}

(ii) The generating function for the number of odd permutations containing 132 exactly once is given by

\begin{matrix}O_{2}(x) = −\frac{1}{2}(x^{4} + 3x^{3} − 5x^{2} − 4x + 2) + \frac{1}{4}(2x^{4} − 4x^{3} + 29x^{2} − 15x + 2)(1 − 4x)^{−3/2} \\ +\frac{1}{4}(16x^{7} − 48x^{6} − 76x^{5} + 64x^{4} + 36x^{3} − 21x^{2} − 5x + 2)(1 − 4x^{2})^{−3/2}. \end{matrix}

(iii) The generating function for the number of permutations containing 132 exactly twice is given by (see [12])

F_{2}(x) = \frac{1}{2}(x^{2} + 3x − 2) + \frac{1}{2}(2x^{4} − 4x^{3} + 29x^{2} − 15x + 2)(1 − 4x)^{−3/2}.

3.4. The cases r = 3, 4, 5, 6. Let r = 3, 4, 5, 6; exhaustive search in 𝔖_{6}, 𝔖_{8}, 𝔖_{10}, and 𝔖_{12} reveals 20, 104, 503, and 2576 new nonexceptional kernel shapes, respectively, and we get Theorem 3.8. Let r = 3, 4, 5, 6, then

M_{r}(x) = \frac{1}{2} (A_{r}(x) + B_{r}(x)(1 − 4x^{2})^{−r+1/2})

and

F_{r}(x) = \frac{1}{2} (C_{r}(x) + D_{r}(x)(1 − 4x)^{−r+1/2}) ,

where

A_{3}(x) = 2x^{6} + 10x^{5} − 24x^{4} − 30x^{3} + 23x^{2} + 7x − 2,

A_{4}(x) = 2x^{8} + 14x^{7} − 46x^{6} − 90x^{5} + 117x^{4} + 85x^{3} − 42x^{2} − 8x + 1,

A_{5}(x) = 2x^{10} + 18x^{9} − 76x^{8} − 198x^{7} + 360x^{6} + 440x^{5} − 355x^{4} − 171x^{3} + 62x^{2} +10x − 2,

A_{6}(x) = 256x^{13} − 446x^{12} − 618x^{11} + 194x^{10} − 140x^{9} + 798x^{8} + 1404x^{7} − 1702x^{6} −1430x^{5} + 815x^{4} + 302x^{3} − 88x^{2} − 15x + 4, B_{3}(x) = 64x^{11} − 320x^{10} − 800x^{9} + 1216x^{8} + 1124x^{7} − 972x^{6} − 524x^{5} + 312x^{4}

+100x^{3} − 43x^{2} − 7x + 2, B_{4}(x) = −256x^{15} + 1792x^{14} + 6112x^{13} − 13120x^{12} − 19840x^{11} + 22224x^{10}

+19054x^{9} − 14780x^{8} − 8328x^{7} + 4772x^{6} + 1840x^{5} − 775x^{4} − 197x^{3} + 56x^{2} +8x − 1,

B_{5}(x) = 1024x^{19} − 9216x^{18} − 40064x^{17} + 111744x^{16} + 228896x^{15} − 343264x^{14} −404056x^{13} + 398712x^{12} + 321058x^{11} − 234686x^{10} − 137468x^{9} + 78480x^{8} +33896x^{7} − 15400x^{6} − 4780x^{5} + 1723x^{4} + 351x^{3} − 98x^{2} − 10x + 2,

B_{6}(x) = 524288x^{24} + 1175552x^{23} − 1593344x^{22} − 2324992x^{21} + 1162752x^{20} +298112x^{19} + 2696448x^{18} + 4856864x^{17} − 7020288x^{16} − 7464568x^{15} +6981056x^{14} + 5445696x^{13} − 3868942x^{12} − 2335450x^{11} + 1324884x^{10} +627306x^{9} − 290536x^{8} − 106510x^{7} + 40772x^{6} + 11046x^{5} − 3543x^{4} −632x^{3} + 176x^{2} + 15x − 4,

C_{3}(x) = 2x^{3} − 5x^{2} + 7x − 2,
C_{4}(x) = 5x^{4} − 7x^{3} + 2x^{2} + 8x − 3,
C_{5}(x) = 14x^{5} − 17x^{4} + x^{3} − 16x^{2} + 14x − 2,
C_{6}(x) = 42x^{6} − 44x^{5} + 5x^{4} + 4x^{3} − 20x^{2} + 19x − 4,

and D_{3}(x) = −22x^{6} − 106x^{5} + 292x^{4} − 302x^{3} + 135x^{2} − 27x + 2, D_{4}(x) = 2x^{9} + 218x^{8} + 1074x^{7} − 1754x^{6} + 388x^{5} + 1087x^{4}, D_{5}(x) = −50x^{11} − 2568x^{10} − 10826x^{9} + 16252x^{8} − 12466x^{7} + 16184x^{6} − 16480x^{5}

+9191x^{4} − 2893x^{3} + 520x^{2} − 50x + 2, D_{6}(x) = 4x^{14} + 820x^{13} + 32824x^{12} + 112328x^{11} − 205530x^{10} + 141294x^{9}

−30562x^{8} − 67602x^{7} + 104256x^{6} − 74090x^{5} + 30839x^{4} − 7902x^{3} + 1230x^{2} −107x + 4.

Moreover, for r = 3, 4, 5, 6,

E_{r}(x) = \frac{1}{4} (A_{r}(x) + C_{r}(x) + D_{r}(x)(1 − 4x)^{−r+1/2} + B_{r}(x)(1 − 4x^{2})^{−r+1/2})

and

O_{r}(x) = \frac{1}{4} (A_{r}(x) − C_{r}(x) + D_{r}(x)(1 − 4x)^{−r+1/2} − B_{r}(x)(1 − 4x^{2})^{−r+1/2}) .

4. Further results and open questions

First of all, let us simplify the expression

L_{r_{1},...,r_{f(ρ)}}^{ρ}(a, 0) − L_{r_{1},...,r_{f(ρ)}}^{ρ}(a, 1),

where a = 0, 1, r_{j} ≥ 0 for all j. Lemma 4.1. Let v ∈ {0, 1}^{n} be any vector, and let a ∈ {1, −1}. Then

∑_{x∈Y_{a}} ∏_{j=1}^{n} H_{r}(v_{j}, x_{j}) − ∑_{y∈Y_{−a}} ∏_{j=1}^{n} H_{r}(v_{j}, y_{j}) = a ∏_{j=1}^{n} g_{r}(j),

where g_{r}(j) = H_{r}(v_{j}, 0) − H_{r}(v_{j}, 1) = \frac{1}{2}(M_{r}(x) + (−1)^{v_{j}}M_{r}(−x)) for all j.

Proof. Let us define an order on the set B^{n}, we say the vector v < u if there exists j such that u_{j} + v_{j} = 1, and u_{i} = v_{i} for all i ≠ j. We say the 2^{n} vectors u^{1}, ⋯, u^{2^{n}} of B^{n} are satisfy the ℓ-property if

0 = (0, 0, …, 0) = u^{1} < u^{2} < ⋯ < u^{2^{n}},

and we say the 2^{n} vectors u^{1}, ⋯, u^{2^{n}} are satisfy the c-property if the vectors

(u_{1}^{1}, …, u_{m}^{1}), …, (u_{1}^{2^{m}}, …, u_{m}^{2^{m}})

are satisfy the ℓ-property for all m = 1, 2, …, n. For example, the vectors of B^{3} are satisfy the c-property by

(0, 0, 0) < (1, 0, 0) < (1, 1, 0) < (0, 1, 0) < (0, 1, 1) < (1, 1, 1) < (1, 0, 1) < (0, 0, 1).

First of all, let us prove by induction on n that there exists an order of the vectors of B^{n} with c-property, for all n ≥ 1. For n = 1 the c-property holds with (0) < (1). Suppose that there exists an order of the vector of B^{m} with the c-property. Let v^{j} = (u_{1}^{j}, …, u_{m}^{j}, 0) for all j = 1, 2, …, 2^{m} and v^{2^{m}+j} = (u_{1}^{2^{m}+1−j}, …, u_{m}^{2^{m}+1−j}, 1) for all j = 1, 2, …, 2^{m}. By definitions, v^{1} = (0, 0, …, 0) and v^{1} < ⋯ < v^{2^{m+1}}, so the ℓ-property holds for m + 1. Hence, by induction on m we get that there exists an order of the vector of B^{n} with the c-property.

Now we are ready to prove the lemma. Without loss of generality we can assume that (0, 0, …, 0) ∈ Y_{a}^{n} (which means a = 1); otherwise it is enough to replace a by −a. Let x^{1}, …, x^{2^{n}} all the vectors of B^{n} with the c-property. Using (0, 0, …, 0) ∈ Y_{a}^{n} together with the c-property we get that x^{2i−1} ∈ Y_{a}^{n} and x^{2i} ∈ Y_{−a}^{n} for all i = 1, 2, …, 2^{n−1}. Therefore, for all i = 1, 2, …, 2^{n−1},

∑_{i=1}^{2^{n−1}} ( ∏_{j=1}^{n} H_{r}(v_{j}, x_{j}^{2i−1}) − ∏_{j=1}^{n} H_{r}(v_{j}, x_{j}^{2i}))

= ∑_{i=1}^{2^{n−1}} ((−1)^{i−1}g_{r}(1) ∏_{j=2}^{n} H_{r}(v_{j}, x_{j}^{2i−1}))

= g_{r}(1) ∑_{i=1}^{2^{n−2}} ( ∏_{j=1}^{n−1} H_{r}(ṽ_{j}, y_{j}^{2i−1}) − ∏_{j=1}^{n−1} H_{r}(ṽ_{j}, y_{j}^{2i})) ,

where y^{p} = (x_{2}^{2p}, …, x_{n}^{2p}) for all p = 1, 2, …, 2^{n−1}, and ṽ = (v_{2}, v_{3}, …, v_{n}). Using the c-property for x^{1}, …, x^{2^{n}} we get that the vectors y^{1}, …, y^{2^{n−1}} are satisfy the cproperty in B^{n−1}. Hence by induction on n (by definitions, the lemma holds for n = 1), we get that the expression equals to a ∏_{j=1}^{n} g_{r}(j). □

As a remark, the vector (0, 0, …, 0) ∈ Y_{z_{ρ}(v)}^{ρ} if and only if z_{ρ}(v) = 1 for any kernel permutation ρ and vector v. Therefore, by Theorem 3.2 and Lemma 4.1 we get the following result. Theorem 4.2. Let a ∈ {0, 1} and r ≥ 0. Then

\begin{matrix}\frac{1}{2}(M_{r}(x) + (−1)^{a}M_{r}(−x)) − δ_{r+a,0} = \\ = ∑_{ρ∈K_{2r+1}} x^{s(ρ)} ∑_{r_{1},...,r_{f(ρ)}=r−c(ρ)} ( ∑_{v∈X_{(−1)^{a}}(ρ)} 2^{−f(ρ)}z_{ρ}(v) ∏_{j=1}^{f(ρ)}(M_{r_{j}}(x) + (−1)^{v_{j}}M_{r_{j}}(−x))) . \end{matrix}

As a remark, the above theorem yields two equations (for a = 0 and a = 1) that are linear on M_{r}(x) and M_{r}(−x). So, Theorem 4.2 provides a finite algorithm for finding M_{r}(x) for any given r ≥ 0, since we have to consider all permutations in 𝔖_{2r+1}, and to perform certain routine operations with all shapes found so far. Moreover, the amount of search can be decreased substantially due to the following proposition which holds immediately by Theorem 3.4 and Theorem 4.2. Proposition 4.3. Let r ≥ 1, a ∈ {0, 1}, and

ρ = 2r − 1, 2r + 1, 2r − 3, 2r, …, 2r − 2j − 3, 2r − 2j, …, 1, 4, 2.

Then the expression

x^{s(ρ)} ∑_{r_{1},...,r_{f(ρ)}=r−c(ρ), r_{j}≥0} ( ∑_{v∈X_{(−1)^{a}}(ρ)} 2^{−f(ρ)}z_{ρ}(v) ∏_{j=1}^{f(ρ)}(M_{r_{j}}(x) + (−1)^{v_{j}}M_{r_{j}}(−x)))

is given by

∑_{j=a}^{[(r+2)/2]}(−1)^{j−a+1}2^{−r−2}\binom{r + 2}{2j + 1 − a}x^{2r+1}(M_{0}(x) − M_{0}(−x))^{j}(M_{0}(x) + M_{0}(−x))^{r+2−j}.

By this proposition, it is sufficient to search only permutations in 𝔖_{2r}. Besides, using Theorem 4.2 and the case r = 0 together with induction on r we get the following result. Theorem 4.4. M_{r}(x) is a rational function on x and \sqrt{1 − 4x^{2}} for any r ≥ 0.

In view of our explicit results, we have even a stronger conjecture. Conjecture 4.5. For any r ≥ 1, there exist polynomials A_{r}(x), B_{r}(x), C_{r}(x), and D_{r}(x) with integer coefficients such that

E_{r}(x) = \frac{1}{4}(A_{r}(x) + B_{r}(x)) + \frac{1}{4}C_{r}(x)(1 − 4x)^{−r+1/2} + \frac{1}{4}D_{r}(x)(1 − 4x^{2})^{−r+1/2},

and

O_{r}(x) = \frac{1}{4}(A_{r}(x) − B_{r}(x)) + \frac{1}{4}C_{r}(x)(1 − 4x)^{−r+1/2} − \frac{1}{4}D_{r}(x)(1 − 4x^{2})^{−r+1/2}.

References

[1] N. Alon and E. Friedgut. On the number of permutations avoiding a given pattern. J. Combin. Theory Ser. A, 89(1):133–140, 2000.

[2] M. D. Atkinson. Restricted permutations. Discrete Math., 195(1-3):27–38, 1999.

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

[4] M. Bóna. The number of permutations with exactly r 132-subsequences is P -recursive in the size! Adv. in Appl. Math., 18(4):510–522, 1997.

[5] M. Bóna. Permutations avoiding certain patterns: the case of length 4 and some generalizations. Discrete Math., 175(1-3):55–67, 1997.

[6] M. Bóna. Permutations with one or two 132-subsequences. Discrete Math., 181(1-3):267–274, 1998.

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

[8] M. Fulmek. Enumeration of permutations containing a presribed number of occurrences of a pattern of length three. Adv. Appl. Math., to appear, math.CO/0112092.

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

[10] T. Mansour. Permutations containing and avoiding certain patterns. In Formal power series and algebraic combinatorics (Moscow, 2000), 704–708. Springer, Berlin, 2000.

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

[12] T. Mansour and A. Vainshtein. Counting occurrences of 132 in a permutation. Adv. Appl. Math., 28(2):185–195, 2002.

[13] J. Noonan. The number of permutations containing exactly one increasing subsequence of length three. Discrete Math., 152(1-3):307–313, 1996.

[14] J. Noonan and D. Zeilberger. The enumeration of permutations with a prescribed number of “forbidden” patterns. Adv. in Appl. Math., 17(4):381–407, 1996.

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

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

[17] Z. Stankova. Forbidden subsequences. Discrete Math., 132(1-3):291–316, 1994.

[18] Z. Stankova. Classification of forbidden subsequences of length 4. European J. Combin., 17(5):501– 517, 1996.

[19] J. West. Generating trees and the Catalan and Schröder numbers. Discrete Math., 146(1-3):247– 262, 1995.