Séminaire Lotharingien de Combinatoire 48 (2002), Article B48a

RESTRICTED 132-INVOLUTIONS

O. GUIBERT AND T. MANSOUR

LABRI (UMR 5800), Université Bordeaux 1, 351 cours de la Libération, 33405 Talence

Cedex, France

                   guibert@labri.fr, toufik@labri.fr

Abstract. We study generating functions for the number of involutions of length n avoiding (or containing exactly once) 132 and avoiding (or containing exactly once) an arbitrary permutation τ of length k. In several interesting cases these generating functions depend only on k and can be expressed via Chebyshev polynomials of the second kind. In particular, we show that involutions of length n avoiding both 132 and 12 … k are equinumerous with involutions of length n avoiding both 132 and any extended double-wedge pattern of length k. We use combinatorial methods to prove several of our results.

1. Introduction

The main goal of this paper is to give analogues of enumerative results on certain classes of permutations characterized by pattern-avoidance in the symmetric group 𝔖_{n}. In ℑ_{n} = {π ∈ 𝔖_{n} : π = π^{−1}} we identify classes of restricted involutions with enumerative properties analogous to results on permutations. More precisely, we study generating functions for the number of n-involutions (that is, involutions of length n) avoiding (or containing exactly once) 132, and avoiding (or containing exactly once) an arbitrary pattern τ ∈ 𝔖_{k}. 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 we summarize our main results.

Let π ∈ 𝔖_{n} and τ ∈ 𝔖_{k} be two permutations. We say that π contains τ whenever there exists a subsequence 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n such that (π_{i_{1}}, π_{i_{2}}, …, π_{i_{k}}) is orderisomorphic to τ; in such a context τ is usually called a pattern. We say that π avoids τ, or is τ-avoiding, whenever no such subsequence exists. The set of all τ-avoiding n-permutations is denoted 𝔖_{n}(τ). For an arbitrary finite collection of patterns T, we say that π avoids T whenever π avoids every τ ∈ T; the corresponding subset of 𝔖_{n} is denoted 𝔖_{n}(T). For example, 562314 ∈ 𝔖_{6}(132) whereas 51243 ∉ 𝔖_{5}(132) because it contains two subsequences (which are 143 and 243) order-isomorphic to 132; moreover, 453612 ∈ 𝔖_{6}(132, 1234).

While the case of permutations avoiding a single pattern has attracted much attention, the case of multiple pattern avoidance remains less investigated. In particular, a natural next step is to consider permutations avoiding pairs of patterns τ_{1}, τ_{2}. This problem has been solved completely for τ_{1}, τ_{2} ∈ 𝔖_{3} (see [SS]), for τ_{1} ∈ 𝔖_{3} and τ_{2} ∈ 𝔖_{4} (see [W2]), and for τ_{1}, τ_{2} ∈ 𝔖_{4} (see [B1, Km] and references therein). Several recent papers [CW, MV1, Kt, MV2, MV3, MV4] 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 r times. This problem has been investigated for certain τ_{1}, τ_{2} ∈ 𝔖_{3} and r = 1 in [Ro], and for certain τ_{1} ∈ 𝔖_{3}, τ_{2} ∈ 𝔖_{k} in [RWZ, MV1, Kt, MV3, MV4]. The tools involved in these papers include continued fractions, Chebyshev polynomials, and Dyck words. We now recall some of these tools in more detail, along with the method of generating trees.

Chebyshev polynomials of the second kind (or Chebyshev polynomials, for short) are defined by

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

for r ≥ 0. The Chebyshev polynomials satisfy the recurrence

(1.2)  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 to meet the needs of approximation theory, but are also widely used in various other branches of mathematics, including algebra, combinatorics, and number theory (see [Ri]). The relationship between restricted permutations and Chebyshev polynomials was first discovered by Chow and West [CW], and later by Mansour and Vainshtein [MV1, MV2, MV3, MV4] and Krattenthaler [Kt]. These results are related to the rational function

(1.3)  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])

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

Following [CGHK] (see also the Ph.D.-theses [Gi, Gu, P, W1]), a generating tree for a set of objects is a tree subject to the conditions that each object of length n appears once and only once on a vertex of level n, and that the edges correspond to the manner in which the objects increase. In order to characterize a generating tree by a succession system, we associate to each object a label such that any two nodes have the same label if and only if their subtrees are isomorphic. Therefore to characterize a generating tree it suffices to specify the label of the root and a set of succession rules explaining how to derive from the label of a parent the labels of all of its children.

Example 1.1. (see [W2]) The generating tree of 132-avoiding permutations can be characterized by the following succession system:

Root: (2)

Succession rule: (t) ⇝ (2), (3), …, (t + 1).

Here t = 1 + |{π_{i}, 1 ≤ i ≤ n : π_{i} > π_{j}, ∀i < j ≤ n}| for any π ∈ 𝔖_{n}(132), and the children of a given permutation of length n are the permutations obtained by inserting an n + 1 in all locations which do not result in a forbidden pattern.

The Catalan sequence is the sequence \{C_{n}\}_{n≥0}, where C_{n} = \frac{1}{n+1} \binom{2n}{n} is called the nth Catalan number. The generating function for the Catalan numbers is given by

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

The Catalan numbers provide a complete answer to the problem of counting more than 66 different families of combinatorial structures (see Stanley [S, Page 219 and Exercise 6.19]). As an example, we consider Dyck words and 132-avoiding permutations.

Let L be a set of letters; we write L^{∗} to denote the set of all words on L. We write |w| to denote the length of a word w, which is the number of letters in w. We write |w|_{l} to denote the number of occurences of a given letter l ∈ L in w. We write ϵ to denote the empty word (which has length 0).

Let P_{x,\overline{x}} = \{w ∈ \{x, \overline{x}\}^{∗} : for all w = w′w′′, |w′|_{x} ≥ |w′|\overline{x}\} be the set of all Dyck word prefixes. For example, xxxx, xxx\overline{x}, xx\overline{x}x, xx\overline{x}\overline{x}, x\overline{x}xx, and x\overline{x}x\overline{x} are the Dyck word prefixes of length 4. Dyck word prefixes in P_{x,\overline{x}} of length n are enumerated by the central binomial coefficient \binom{n}{[n/2]} for all n ≥ 0. Dyck words are Dyck word prefixes w in \{x, \overline{x}\}^{∗} such that |w|_{x} = |w|\overline{x}. For example, xx\overline{x}\overline{x} and x\overline{x}x\overline{x} are the two Dyck words of length 4. Dyck words of length 2n are enumerated by C_{n}, the nth Catalan number.

One of the numerous bijections between 132-avoiding permutations and Dyck words can be obtained by characterizing the generating tree for Dyck words by the same succession system given in Example 1.1. Guibert [Gu, Example 2.1] has exhibited such a characterization, in which the label t of any Dyck word w satisfies w = xw_{1}\overline{x}xw_{2}\overline{x} … xw_{t−1}\overline{x}, where w_{i} is a Dyck word for all 1 ≤ i < t.

We also consider words in {a, b^{2}}^{∗} of length n, which are enumerated by the nth Fibonacci number F_{n}. Recall that the Fibonacci numbers are given by F_{0} = F_{1} = 1 and F_{n} = F_{n−1} + F_{n−2}, and have the generating function F (x) = \frac{1}{1−x−x^{2}} .

An involution π is a permutation such that π = π^{−1}; let ℑ_{n} denote the set of all n-involutions. Several authors have given enumerations of sets of involutions which avoid certain patterns. In [Re] Regev provided an asymptotic formula for ℑ_{n}(12 … k) and showed that ℑ_{n}(1234) is enumerated by the nth Motzkin number ∑_{i=0}^{[n/2]} \binom{n}{2i}C_{i}. In [Ge] Gessel enumerated ℑ_{n}(12 … k). In [G-B] Gouyou–Beauchamps gave an entirely bijective proof of some very nice exact formulas for ℑ_{n}(12345) and ℑ_{n}(123456).

Pattern-avoiding involutions have also been linked with other combinatorial objects. Gire [Gi] has established a one-to-one correspondence between 1-2 trees having n edges and 𝔖_{n}(321, 3\overline{1}42) (this is the set of n-permutations avoiding patterns 321 and 231, except that the latter is allowed when it is a subsequence of the pattern 3142). On the other hand, Guibert [Gu] has established bijections between 1-2 trees having n edges and each of the sets 𝔖_{n}(231, 4\overline{1}32), ℑ_{n}(3412), and ℑ_{n}(4321) (and therefore with ℑ_{n}(1234), by transposing the corresponding Young tableaux obtained by applying the Robinson-Schensted algorithm). In addition, Guibert [Gu] has established a bijection between ℑ_{n}(2143) (these involutions are sometimes called vexillary involutions) and ℑ_{n}(1243). More recently, Guibert, Pergola, and Pinzani [GPP] have given a one-to-one correspondence between 1-2 trees having n edges and vexillary n-involutions. It follows that all these sets are enumerated by the nth Motzkin number. It remains an open problem to prove the conjecture of Guibert (in [Gu]) that ℑ_{n}(1432) is also enumerated by the nth Motzkin number.

In this paper we present a general approach to the study of n-involutions avoiding 132 (or containing 132 exactly once), and avoiding (or containing exactly once) an arbitrary pattern τ ∈ 𝔖_{k}. As a consequence, we derive all of the previously known results for this kind of problem, as well as many new results. We also prove many of our results using combinatorial (sometimes entirely bijective) methods.

The paper is organized as follows. The case of involutions avoiding both 132 and τ is treated in Section 2, where we derive a simple structure for any given 132avoiding involution. This structure gives a complete answer for several interesting cases of τ, including the cases τ = 12 … k (see Subsection 2.2), τ = 2134 … k (see Subsection 2.3), τ is an extended double-wedge pattern (see Subsection 2.4), and τ = (d+1)(d+2) … k12 … d (see Subsection 2.5). In particular, we give a bijection between involutions avoiding both 132 and 12 … k and involutions avoiding both 132 and 2134 … k (see Subsection 2.3). We also show that involutions avoiding both 132 and any extended double-wedge pattern of length k (see Subsection 2.4) are equinumerous with involutions avoiding 132 and 12 … k.

We treat the case of involutions avoiding 132 and containing τ exactly once in Section 3. Here again we start with a general structure for 132-avoiding involutions, and then obtain a complete answer for several particular cases. For instance, we find a recurrence relation for the generating function for the number of involutions avoiding 132 and containing 12 … k exactly r times (see Theorem 3.4).

In Sections 4 and 5 we consider those involutions which contain 132 exactly once. In particular, we establish by bijective arguments that n-involutions containing 132 exactly once and having p fixed points are equinumerous with (n − 2)-involutions avoiding 132 and having p fixed points (see Theorem 4.1).

2. Avoiding 132 and another pattern

Let ℑ_{T} (n) = |ℑ_{n}(132, T)|, and let ℑ_{T} (x) = ∑_{n≥0} ℑ_{T} (n)x^{n} be the corresponding generating function. The following proposition is the basis for all of the other results in this section; it follows immediately from our definitions.

Proposition 2.1. For any π ∈ ℑ_{n}(132) such that π_{j} = n, exactly one of the following holds:

(1) if 1 ≤ j ≤ [n/2] then π = (β, n, γ, δ, j), where (1.1) β is a 132-avoiding permutation of the numbers n − j + 1, …, n − 2, n − 1, (1.2) δ ∈ 𝔖_{j−1}(132) such that δ · β = 12 … (j − 1); sometimes we will write

δ^{−1} + n − j for β, (1.3) γ is a 132-avoiding involution of the numbers j + 1, …, n − j − 1, n − j;

(2) if j = n then π = (β, n) where β ∈ ℑ_{n−1}(132).

For example, π = 18 16 17 19 12 13 10 9 8 7 11 5 6 14 15 2 3 1 4 is a 132avoiding involution for which case (1) occurs: n = 19, j = 4, β = 18 16 17, γ = 12 13 10 9 8 7 11 5 6 14 15 and δ = 2 3 1. In particular, β = δ^{−1} + 15 = (3+15) (1+15) (2+15).

Observe that applying Proposition 2.1 repeatedly leads to the following decomposition of a given 132-avoiding involution:

π = (β_{1}, n_{1}, β_{2}, n_{2}, …, β_{k}, n_{k}, α_{k+1}, δ_{k}, j_{k}, α_{k}, …, δ_{2}, j_{2}, α_{2}, δ_{1}, j_{1}, α_{1}).

Here n_{i} and j_{i} form a cycle for all 1 ≤ i ≤ k, the elements of β_{i} form cycles with the elements of δ_{i} for all 1 ≤ i ≤ k, and the elements of α_{i} are fixed points for 1 ≤ i ≤ k + 1. For the permutation π given in the previous example we find that β_{1} = 18 16 17, n_{1} = 19, β_{2} = 12, n_{2} = 13, β_{3} = ε, n_{3} = 10, β_{4} = ε, n_{4} = 9, α_{5} = ε, δ_{4} = ε, j_{4} = 8, α_{4} = ε, δ_{3} = ε, j_{3} = 7, α_{3} = 11, δ_{2} = 5, j_{2} = 6, α_{2} = 14 15, δ_{1} = 2 3 1, j_{1} = 4, and α_{1} = ε.

2.1. Avoiding 132. We will use the following remark.

Remark 2.2. Let {y_{n}}_{n≥0} and {z_{n}}_{n≥0} be two sequences, and denote the corresponding generating functions by y(x) and z(x) respectively. Then

\begin{matrix}∑_{n≥0} ∑_{j=0}^{n} y_{j}z_{2n−2j}x^{2n} = \frac{1}{2}y(x^{2})(z(x) + z(−x)); \\ ∑_{n≥0} ∑_{j=0}^{n} y_{j}z_{2n+1−2j}x^{2n+1} = \frac{1}{2}y(x^{2})(z(x) − z(−x)). \end{matrix}

As a corollary of Proposition 2.1, we obtain the generating function for |ℑ_{n}(132)|.

Theorem 2.3. (see [SS, Proposition 5]) The generating function for the number of 132-avoiding n-involutions is given by

ℑ_{∅}(x) = \frac{1}{1 − x − x^{2}C(x^{2})}.

Proof. Knuth [Kn] proved that |𝔖_{n}(132)| = C_{n}, where C_{n} is the nth Catalan number, and by Proposition 2.1 we find that for all n ≥ 1,

ℑ_{∅}(n) = ∑_{j=1}^{[n/2]} C_{j−1}ℑ_{∅}(n − 2j) + ℑ_{∅}(n − 1).

Moreover, ℑ_{∅}(0) = 1. Restating this in terms of generating functions and using Remark 2.2, we find that

ℑ_{∅}(x) = 1 + x^{2}C(x^{2})ℑ_{∅}(x) + xℑ_{∅}(x).
□

We can also prove this result bijectively. The number of Dyck word prefixes of length n is the central binomial coefficient \binom{n}{[n/2]} when n ≥ 0. Indeed, for any Dyck word prefix w ∈ P_{x,\overline{x}} there exist unique Dyck words w_{i} such that w = w_{0}xw_{1}x … xw_{p}, and w is in bijection (see the Catalan factorization of any word in \{x, \overline{x}\}^{∗} due to Chottin and Cori [CC]) with w_{0}\overline{x}w_{1}\overline{x} … \overline{x}w_{[(p−1)/2]}\overline{x}w_{[(p+1)/2]}xw_{[(p+3)/2]}x … xw_{p}. Therefore Dyck word prefixes of length n are in bijection with bilateral words of length n in

\{w ∈ \{x, \overline{x}\}^{∗} : |w|_{x} = |w|\overline{x} or |w|_{x} = |w|\overline{x} − 1\},

which are trivially enumerated by \binom{n}{[n/2]}.

Theorem 2.4. There is a bijection Φ between 132-avoiding n-involutions and Dyck word prefixes in P_{x,\overline{x}} of length n. Moreover, the number of fixed points of the involution corresponds to the difference between the number of letters x and \overline{x} in the Dyck word prefix.

Proof. Let π ∈ ℑ_{n}(132) have p fixed points. By Proposition 2.1 (and the associated remark), we have π = π′π′′xπ′′′ with |π′| = \frac{n−p}{2} (π′ has no fixed points and consists of cycles with π′′ or π′′′), π′′ does not contain a fixed point and π(x) = x (x is the first fixed point). We obtain two 132-avoiding (n + 1)-involutions from π. The first one is given by inserting a fixed point between π′ and π′′, and the second one (if and only if π has at least one fixed point) is given by modifying the first fixed point x by a cycle between π′ and π′′. All 132-avoiding involutions can be obtained exactly once by applying this rule, starting from ϵ.

Let w ∈ P_{x,\overline{x}} have length n and satisfy |w|_{x} − |w|\overline{x} = p. Then w = w_{0}xw_{1}x … xw_{p} where w_{i} are Dyck words for all 0 ≤ i ≤ p. We obtain two Dyck word prefixes of length n + 1 from w: xw and xw_{0}\overline{x}w_{1}x ⋯ xw_{p} (if and only if p > 0). All Dyck word prefixes can be obtained exactly once by applying this rule, starting from ϵ. □

Clearly, these two generating trees for the 132-avoiding involutions and the Dyck word prefixes can be characterized by the following succession system:

(2.1)  \{ \begin{matrix}(0) \\ (0) & ⇝ & (1) \\ (p) & ⇝ & (p + 1), (p − 1) & if p ≥ 1 \end{matrix}

Figure 1 shows the bijection Φ between 132-avoiding involutions and Dyck word prefixes (and the labels of the succession system which characterizes them) for the first values.

Corollary 2.5. The number of 132-avoiding n-involutions is given by

\binom{n}{[n/2]}.

Moreover, the number of 132-avoiding n-involutions having exactly p fixed points with 0 ≤ p ≤ n (and p is odd if and only if n is odd) is given by the ballot number

\binom{n}{\frac{n+p}{2}} − \binom{n}{\frac{n+p}{2} + 1}.

Proof. Indeed, the number of Dyck word prefixes w of length n with |w|_{x} − |w|\overline{x} = p is given by the ballot number (or Delannoy number [E], or distribution α of the Catalan number [Kw]). □

Figure 1. The generating trees of the 132-avoiding involutions and the Dyck word prefixes, with the labels of the succession system which characterizes them.

In particular, the number of 132-avoiding 2n-involutions without fixed points is given by C_{n}, the nth Catalan number.

The following theorem is the basis for all of the other results in this section.

Theorem 2.6. Let T be a set of patterns, T′ = {(τ_{1}, …, τ_{k}, k + 1) : (τ_{1}, …, τ_{k}) ∈ T }, and let 𝔖_{T} (x) be the generating function for |𝔖_{n}(132, T)|. Then

(2.2)  ℑ_{T′}(x) = \frac{1}{1 − x^{2}𝔖_{T} (x^{2})} + \frac{x}{1 − x^{2}𝔖_{T} (x^{2})}ℑ_{T} (x).

Proof. Proposition 2.1, together with the definition of T′, yields for n ≥ 1

ℑ_{T′}(n) = ℑ_{T} (n − 1) + ∑_{j=1}^{[n/2]} 𝔖_{T} (j − 1)ℑ_{T′}(n − 2j),

where 𝔖_{T} (j −1) = |𝔖_{j−1}(132, T)|. Hence, in terms of generating functions, Remark 2.2 yields

ℑ_{T′}(x) − 1 = xℑ_{T} (x) + x^{2}𝔖_{T} (x^{2})\frac{ℑ_{T′}(x) + ℑ_{T′}(−x)}{2} + x^{2}𝔖_{T} (x^{2})\frac{ℑ_{T′}(x) − ℑ_{T′}(−x)}{2},

which is equivalent to Equation 2.2. □

2.2. Avoiding 132 and 12 … k. In this subsection we consider involutions which avoid both 132 and 12 … k. We start with an example.

Example 2.7. (see [SS]) Let T′ = {123} and T = {12}. Equation 2.2 gives

ℑ_{123}(x) = \frac{1}{1 − x^{2}𝔖_{12}(x^{2})} + \frac{x}{1 − x^{2}𝔖_{12}(x^{2})}ℑ_{12}(x),

and by definition we have 𝔖_{12}(x) = ℑ_{12}(x) = \frac{1}{1−x}; hence

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

It follows that |ℑ_{123}(n)| = 2^{[n/2]} for all n ≥ 0. Similarly, ℑ_{1234}(x) = \frac{1}{1−x−x^{2}} , which means that |ℑ_{1234}(n)| = F_{n}, the nth Fibonacci number.

As an extension of Example 2.7, we consider the case T = {12 … k}.

Theorem 2.8. For all k ≥ 1,

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

Proof. The theorem is immediate for k = 1. Let k ≥ 2; Theorem 2.6 gives

ℑ_{12...k}(x) = \frac{1}{1 − x^{2}𝔖_{12...(k−1)}(x^{2})} + \frac{x}{1 − x^{2}𝔖_{12...(k−1)}(x^{2})}ℑ_{12...(k−1)}(x).

On the other hand, the generating function for |𝔖_{n}(132, 12 … (k − 1))| is R_{k−1}(x) (see [CW, Theorem 1]); combining this with Identity 1.4, we have

ℑ_{12...k}(x) = R_{k}(x^{2}) + xR_{k}(x^{2})ℑ_{12...(k−1)}(x).

Clearly ℑ_{1}(x) = R_{0}(x) = 1, so by induction on k and Identity 1.3, we get the desired result. □

We now give a combinatorial explanation for this result. Let π be a 132-avoiding involution. Observe that if π avoids 12 … k then π has less than k fixed points. Moreover, if π (of length n) has less than k fixed points and is obtained from a 132-avoiding involution σ of length less than n having k fixed points (taking σ as large as possible) by applying the rules described for the bijection Φ given in Theorem 2.4, then π contains a subsequence 12 … k. This is because the first fixed points of σ become cycles in π such that the beginning of these cycles and the last remaining fixed points of σ in π constitute a subsequence of type 12 … k. It follows that the succession system

(2.3)  \{ \begin{matrix}(0) \\ (0) & ⇝ & (1) \\ (p) & ⇝ & (p + 1), (p − 1) & 1 ≤ p ≤ k − 2 \\ (k − 1) & ⇝ & (k − 2) \end{matrix}

characterizes the generating tree for the involutions which avoid both 132 and 12 … k.

It is easy to see that |ℑ_{2n}(132, 12 … k)| = 2|ℑ_{2n−1}(132, 12 … k)| for any odd k. Moreover, observe that the set of labels of succession system 2.3 is finite, so the corresponding generating function is rational. More precisely, we immediately deduce from the succession system 2.3 that the number of n-involutions avoiding both 132 and 12 … k having p fixed points is given by the (p+1)th component of the vector given by V_{k}.M_{k}^{n}, where V_{k} = ( 1 0 0 … 0 ) is a vector of k elements and

M_{k} = ( \begin{matrix}0 & 1 & 0 & 0 & 0 & ⋯ & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & ⋯ & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & ⋯ & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & ⋯ & 0 & 0 & 0 \\ . & . & . \\ 0 & 0 & 0 & 0 & 0 & ⋯ & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & ⋯ & 0 & 1 & 0 \end{matrix} )

is a k×k matrix. This is equivalent to an automaton in which the states are 0, 1, …, k− 1 and the transitions are arrows from i to i + 1 for 0 ≤ i < k − 1 and from i to i − 1 for 0 < i ≤ k − 1.

The bijection Φ establishes a one-to-one correspondence between n-involutions avoiding both 132 and 12 … k having p fixed points and Dyck word prefixes w = w_{0}xw_{1}x … xw_{p} of length n such that w_{i} is a Dyck word of height less than k − p + i (that is, w_{i} ∈ P_{x,\overline{x}}, |w_{i}|_{x} = |w_{i}|\overline{x}, and for all w_{i} = w′w′′, |w′|_{x} − |w′|\overline{x} < k − p + i) for all 0 ≤ i ≤ p. In particular, 2n-involutions avoiding both 132 and 12 … k without fixed points are in bijection by Φ with Dyck words of length 2n of height less than k.

These Dyck words of bounded height were considered by Kreweras [Kw] and Viennot [V]. In particular, Dyck words of length 2n with height less than 1, 2, 3, 4, 5 are enumerated by 0, 1, 2^{n−1}, F_{n−2}, \frac{3^{n−1}+1}{2} respectively. We provide some simple bijections for special cases k = 3, 4, 5 (related to Example 2.7) by generating some well known words in the same way as involutions which avoid both 132 and 12 … k.

First we consider the case k = 3. The words of the form {a, b}^{∗} or a{a, b}^{∗}, which are enumerated by the powers of 2, can be generated from the empty word (labeled (0)) by the rules:

(2.4)  \{ \begin{matrix}w(0) & ⇝ & aw(1) \\ aw(1) & ⇝ & aw(2), bw(0) \\ w(2) & ⇝ & aw(1) \end{matrix}

Here the words labeled (0) start with b and the words labeled (1) or (2) start with a. It follows that {a, b}^{n} (respectively a{a, b}^{n}) is in bijection with ℑ_{2n}(132, 123) (respectively ℑ_{2n+1}(132, 123)), which is therefore enumerated by 2^{n} (respectively 2^{n}).

Next we consider the case k = 4 and the words of the form {a, b^{2}}^{∗} enumerated by the Fibonacci numbers. We can generate these from the empty word (labeled (0)) by the rules:

(2.5)  \{ \begin{matrix}w(0) & ⇝ & aw(1) \\ aw(1) & ⇝ & aaw(2), b^{2}w(0) \\ aw(2) & ⇝ & b^{2}w(3), aaw(1) \\ w(3) & ⇝ & aw(2) \end{matrix}

Here the words labeled (0) or (3) start with b^{2} and the words labeled (1) or (2) start with a. It follows that {a, b^{2}}^{n} is in bijection with ℑ_{n}(132, 1234), which is therefore enumerated by F_{n}, the nth Fibonacci number.

Finally, let us consider the case k = 5 and the words of the form {a, b, c}^{∗}a or {a, b, c}^{∗}a ∪ b{a, b, c}^{∗}a, which are enumerated by the powers of 3. We can generate these words from the empty word (labeled (0)) by the rules:

(2.6)  \{ \begin{matrix}w(0) & ⇝ & aw(1) \\ w(1) & ⇝ & bw(2), w(0) \\ w = bw′ = bb^{∗}cw(2) & ⇝ & w(3), aw′(1) \\ w = bw′ = bb^{∗}aw(2) & ⇝ & cw′(3), w(1) \\ w(3) & ⇝ & w(4), bw(2) \\ w(4) & ⇝ & cw(3) \end{matrix}

Here the words labeled (0) or (1) start with b^{∗}a, the words labeled (3) or (4) start with b^{∗}c, and the words labeled (2) start with b (and have one letter more than words labeled (0) or (4) at the same level). It follows that {a, b, c}^{n}a (respectively {a, b, c}^{n}a∪ b{a, b, c}^{n}a) is in bijection with ℑ_{2n+1}(132, 12345) (respectively ℑ_{2n+2}(132, 12345)), which is therefore enumerated by 3^{n} (respectively 2 · 3^{n}).

Figure 2 (which is output of the software forbid [Gu]) shows the first values of |ℑ_{n}(132, 12 … k)| for 3 ≤ k ≤ 5 according to the number p of fixed points.

Some of the integer sequences we have considered also appear in [SP]. In particular, the entry M1458 corresponds to involutions avoiding both 132 and 12345 having exactly one fixed point whereas the entry M2847 corresponds to involutions avoiding both 132 and 1234567 of odd length. Moreover, these two entries refer to [HM, Tables I and III]; it will be interesting to relate 132-involutions to order-consecutive partitions.

2.3. Avoiding 132 and 2134 … k. In this subsection we consider involutions which avoid both 132 and 2134 … k. We begin with an example.

Example 2.9. Let T′ = {213} and T = {21}. Equation 2.2 gives

ℑ_{213}(x) = \frac{1}{1 − x^{2}𝔖_{21}(x^{2})} + \frac{x}{1 − x^{2}𝔖_{21}(x^{2})}ℑ_{21}(x).

Clearly 𝔖_{21}(x) = ℑ_{21}(x) = \frac{1}{1−x}; hence

ℑ_{213}(x) = \frac{1 + x}{1 − 2x^{2}} .

Involutions π ∈ ℑ_{n}(132, 123) according to |{π(x) = x}| = p for 1 ≤ n ≤ 13

p \ n 1 2 3 4 5 6 7 8 9 10 11 12 13
2  1  2  4  8  16  32
1  1  2  4  8  16  32  64
0  1  2  4  8  16  32
1 2 2 4 4 8 8 16 16 32 32 64 64

Involutions π ∈ ℑ_{n}(132, 1234) according to |{π(x) = x}| = p for 1 ≤ n ≤ 13

p \ n 1 2 3 4 5 6 7 8 9 10 11 12 13
3  1  3  8  21  55  144
2  1  3  8  21  55  144
1  1  2  5  13  34  89  233
0  1  2  5  13  34  89
1 2 3 5 8 13 21 34 55 89 144 233 377

Involutions π ∈ ℑ_{n}(132, 12345) according to |{π(x) = x}| = p for 1 ≤ n ≤ 15

p \ n 1 2 3 4 5 6 7 8 9 10 11 12 13
4  1  4  13  40  121
3  1  4  13  40  121  364
2  1  3  9  27  81  243
1  1  2  5  14  41  122  365
0  1  2  5  14  41  122
1 2 3 6 9 18 27 54 81 162 243 486 729

Figure 2. |ℑ_{n}(132, 12 … k)| for 3 ≤ k ≤ 5 according to the number p of fixed points.

Therefore |ℑ_{213}(n)| = 2^{[n/2]} for all n ≥ 0. Similarly, ℑ_{2134}(x) = \frac{1}{1−x−x^{2}} , so |ℑ_{2134}(n)| = F_{n}, the nth Fibonacci number.

We can easily give a bijective proof of the fact that |ℑ_{213}(n)| = 2^{[n/2]}. Any π ∈ ℑ_{n}(132, 213) is either 12 … n or (n + 1 − i)(n + 2 − i) … nπ′12 … i (i ≥ 1), where π′ is (upon subtracting i from each element) also an involution avoiding both 132 and 213. We map this recursive decomposition of an involution π avoiding both 132 and 213 to a word of nonnegative integers formed by the successive positive numbers i (first we treat π which gives i, next we consider the same decomposition for π′ − i, and so on) and whose last nonnegative integer is [p/2], where p is the number of the fixed points in π. We also add a symbol ˜ to the word when n is odd. This mapping is clearly bijective.

For example, the involutions ϵ, 1, 12, 21, 123, 321, 1234, 4231, 3412 and 4321 are mapped to 0, 0˜ , 1, 10, 1˜ , 10˜ , 2, 11, 20 and 110 respectively. Moreover, the involution 21 19 20 16 17 18 15 14 9 10 11 12 13 8 7 4 5 6 2 3 1 in ℑ_{21}(132, 213) is mapped to 123112˜ , because we first successively consider the element 1 (with 21), the elements 2 and 3 (with 19 and 20), the elements 4, 5 and 6 (with 16, 17 and 18), the element 7 (with 15), the element 8 (with 14) which give us the letters 1, 2, 3, 1, 1, respectively.

The five remaining fixed points (the elements 9, 10, 11, 12 and 13) give us the last letter 2. Since the length of π is odd, we add the symbol ˜ to the end.

Thus, involutions in ℑ_{n}(132, 213) are mapped onto words w = w_{1}w_{2} … w_{l−1}w_{l} (with an extra symbol ˜ if n is odd), where l ≥ 1, w_{j} ≥ 1 for all 1 ≤ j < l, w_{l} ≥ 0 and ∑_{j=1}^{l} w_{j} = [n/2]. Trivially, these words are in bijection with words of the form w_{1}w_{2} … w_{l−1}(w_{l} + 1), which are compositions of [n/2] + 1 into l positive parts, which are enumerated by 2^{[n/2]}.

The case of varying k is more interesting. As an extension of Example 2.9, we consider the case T = {2134 … k}. As with Theorem 2.8, we have

Theorem 2.10. For all k ≥ 1,

ℑ_{2134...k}(x) = \frac{1}{x · U_{k} (\frac{1}{2x})} ∑_{j=0}^{k−1} U_{j} (\frac{1}{2x}) .

Therefore, Theorems 2.8 and 2.10 yield ℑ_{12...k}(n) = ℑ_{2134...k}(n). We give a bijective proof of this result.

Theorem 2.11. There is a bijection between n-involutions avoiding both 132 and 12 … k and n-involutions avoiding both 132 and 2134 … k, for any k ≥ 3. Moreover, two involutions in bijection have the same number of fixed points p for all 0 ≤ p ≤ k−3. Involutions which avoid both 132 and 12 … k and have k −2 or k −1 fixed points correspond to involutions which avoid both 132 and 2134 … k and have k − 2 or more fixed points.

Proof. To prove this result, we characterize the generating tree for the involutions avoiding both 132 and 2134 … k by the same succession system 2.3 established for a generating tree for the involutions avoiding both 132 and 12 … k.

If π ∈ ℑ_{n}(132, 2134 … k) and q is the number of fixed points of π, then the label (p) of π is given by

(2.7)  p = \{ \begin{matrix}q & if q ≤ k − 3 \\ k − 2 & if q ≥ k − 2 and (n + k) mod 2 = 0 \\ k − 1 & if q ≥ k − 2 and (n + k) mod 2 = 1 \end{matrix} .

The empty involution has label (0). We obtain σ ∈ ℑ_{n+1}(132, 2134 … k) by applying the following rules:

(i) If 0 ≤ p ≤ k − 3, we have π = π′π′′ with |π′| = \frac{n−p}{2}, and then σ is obtained by inserting a fixed point between π′ and π′′; observe σ has label (p + 1).

(ii) If p = k − 2, we have π = π′xπ′′ with π(x) = x = \frac{n+4−k}{2}, and then σ is obtained

by inserting a fixed point between π′ and x; observe σ has label (k − 1). (iii) If 1 ≤ p ≤ k − 3, we have π = π′π′′xπ′′′ with |π′| = \frac{n−p}{2}, π(x) = x and π(y) ≠ y

for all 1 ≤ y < x. Then σ is obtained by modifying the first fixed point x by a cycle starting between π′ and π′′ (and ending in x); observe σ has label (p − 1).

(iv) If p = k − 1, we have π = π′x(x + 1)π′′ with π(x) = x = \frac{n+3−k}{2}, and then σ is obtained by inserting a fixed point between π′ and x; observe σ has label (k − 2).

(v) If p = k − 2, we have π = π′(x − j)(x − j + 1) … (x + j)π′′ with j ≥ 0, π(x) = x = \frac{n+4−k}{2}, |π′| = \frac{n−k}{2} + 1 − j and e > x for all e ∈ π′. Then σ is obtained by modifying the 2j + 1 fixed points between π′ and π′′ by j + 1 consecutive cycles each of difference (between the index and the value) j + 1 that is (π′_{1}+1)(π′_{2}+1) … (π′_{\frac{n−k}{2} +1−j} +1)(\frac{n−k}{2} +3)(\frac{n−k}{2} +4) … (\frac{n−k}{2} +3+j)(\frac{n−k}{2} −

j + 2)(\frac{n−k}{2} − j + 3) … (\frac{n−k}{2} + 2)π′′; observe σ has label (k − 3).

Thus we obtain the following succession system:

(2.8)  \{ \begin{matrix}(0) \\ (0) & ⇝ & (1) by (i) \\ (p) & ⇝ & (p + 1) by (i) , (p − 1) by (iii) & 1 ≤ p ≤ k − 3 \\ (k − 2) & ⇝ & (k − 1) by (ii) , (k − 3) by (v) \\ (k − 1) & ⇝ & (k − 2) by (iv) \end{matrix}

This is equivalent to succession system 2.3. □

Corollary 2.12. There is a bijection between 𝔖_{n}(132, 12 … k) and 𝔖_{n}(132, 2134 … k) for any k ≥ 3.

Proof. By Proposition 2.1, we deduce that n-permutations π avoiding both 132 and 12 … k (respectively 2134 … k) are in bijection with 2n-involutions without fixed points (π^{−1}+n)π = (π_{1}^{−1}+n, π_{2}^{−1}+n, …, π_{n}^{−1}+n, π_{1}, π_{2}, …, π_{n}) avoiding both 132 and 12 … k (respectively 2134 … k). Moreover, a particular case of Theorem 2.11 establishes a oneto-one correspondence between involutions avoiding both 132 and 12 … k without fixed points and involutions avoiding both 132 and 2134 … k without fixed points. □

2.4. Avoiding 132 and an extended double-wedge pattern. In this subsection we construct a wide class of patterns which are equinumerous with involutions which avoid 132 and either 12 … k or 2134 … k, which we studied in Subsections 2.2 and 2.3 respectively. Following [MV2], we say that τ ∈ 𝔖_{k} is a wedge pattern whenever it can be represented as τ = (τ^{1}, ρ^{1}, …, τ^{r}, ρ^{r}), where each of τ^{i} is nonempty, ρ^{j} is an increasing subsequence such every element of ρ^{j} is greater than every element of ρ^{j+1} for all j, and (τ^{1}, τ^{2}, …, τ^{r}) = (s + 1, s + 2, …, k). For example, 645783912 and 456378129 are wedge patterns.

For a further generalization of Theorem 2.8, Theorem 2.10, and [MV2, Theorem 2.6], we consider the following definition. We say that τ ∈ ℑ_{2l} is a double-wedge pattern whenever there exists a wedge pattern σ ∈ 𝔖_{l−1} such that

τ = (σ^{−1} + l, 2l, σ, l) or τ = (σ + l, 2l, σ^{−1}, l).

For example, the double-wedge patterns in 𝔖_{10} are 6789(10)12345, 7689(10)21345, 7869(10)31245, 7896(10)41235, 8679(10)23145, 8796(10)42135, 8967(10)34125, 9678(10)23415, and 9768(10)32415.

Theorem 2.13. For any double-wedge pattern τ ∈ ℑ_{2l}(132),

ℑ_{τ}(x) = ℑ_{12...(2l)}(x) = \frac{R_{l}(x^{2})}{1 − xR_{l}(x^{2})}.

Proof. By Proposition 2.1 we have two possibilities for the block decomposition of an arbitrary π ∈ ℑ_{n}(132). Let us write an equation for ℑ_{ρ}(x) where ρ = (σ^{−1}, 2l, σ, l). The contribution of the first decomposition above (using Remark 2.2) is given by xℑ_{ρ}(x). The contribution of the second decomposition above (using Remark 2.2) is given by x^{2}𝔖_{σ}(x^{2})ℑ_{ρ}(x) where 𝔖_{σ}(x^{2}) is the generating function for |𝔖_{n}(132, σ)|. Therefore (with a 1 for the empty permutation),

ℑ_{ρ}(x) = 1 + xℑ_{ρ}(x) + x^{2}𝔖_{σ}(x^{2})ℑ_{ρ}(x).

On the other hand, Mansour and Vainshtein [MV2, Theorem 2.6] have shown that 𝔖_{σ}(x) = R_{l−1}(x) for any wedge pattern σ, so

ℑ_{ρ}(x) = \frac{1}{1 − x − x^{2}R_{l−1}(x^{2})},

and using Identity 1.4 we have

ℑ_{ρ}(x) = \frac{R_{l}(x)}{1 − xR_{l}(x^{2})}.

Using the identity

∑_{j=0}^{2l} U_{j}(t) = \frac{U_{2l}(t)U_{l−1}(t)}{U_{l}(t) − U_{l−1}(t)}

together with Theorem 2.8, we now obtain ℑ_{ρ}(x) = ℑ_{12...(2l)}(x). □

We say that τ ∈ ℑ_{k} is an extended double-wedge pattern whenever τ = τ′τ′′ ,where τ′ is a double-wedge pattern and τ′′ = (|τ′| + 1, |τ′| + 2, …, k).

Theorem 2.14. For any extended double-wedge pattern τ of length k, where k ≥ 2l, the generating function for |𝔖_{n}(132, τ)| is given by R_{k}(x).

Proof. By definition we have either τ = (σ^{−1} + l, 2l, σ, l, 2l + 1, 2l + 2, …, k) or τ = (σ + l, 2l, σ^{−1}, l, 2l + 1, 2l + 2, …, k) where σ is a wedge pattern in 𝔖_{l−1}(132). Suppose τ = (σ^{−1} + l, 2l, σ, l) and let 𝔖_{τ}(x) be the generating function for |𝔖_{n}(132, τ)|. By [MV2, Theorem 1] we have

𝔖_{τ}(x) = 1 + x(𝔖_{τ}(x) − 𝔖_{σ^{−1}}(x))𝔖_{σ}(x) + x𝔖_{σ^{−1}}(x)𝔖_{τ}(x).

On the other hand, by [MV2, Theorem 2.6], and since σ is a wedge pattern in 𝔖_{l−1}(132), we have 𝔖_{σ^{−1}}(x) = 𝔖_{σ}(x) = R_{l−1}(x). Therefore, by use of Identity 1.4 we get

𝔖_{τ}(x) = \frac{R_{l}(x)(1 − xR_{l−1}(x)R_{l}(x))}{1 − xR_{l}^{2}(x)},

and use of the identity

\frac{R_{l}(x)(1 − xR_{l−1}(x)R_{l}(x))}{1 − xR_{l}^{2}(x)} = R_{2l}(x)

together with [MV2, Theorem 1], we have 𝔖_{(τ,2l+1,...,k)}(x) = R_{k}(x). The proof in the other case is similar. □

As a corollary of Theorem 2.13 we have the following result.

Theorem 2.15. For any extended double-wedge pattern τ ∈ ℑ_{k}(132),

ℑ_{τ}(x) = ℑ_{12...k}(x).

Proof. Observe that if 𝔖_{β}(x) = 𝔖_{γ}(x) and ℑ_{β}(x) = ℑ_{γ}(x) then Theorem 2.6 yields ℑ_{τ′}(x) = ℑ_{β′}(x) and [MV2, Theorem 1] yields 𝔖_{τ′}(x) = 𝔖_{ρ′}(x), where τ′ = (τ_{1}, …, τ_{p}, p + 1) and ρ′ = (ρ_{1}, …, ρ_{p}, p + 1) are two patterns in 𝔖_{p+1}. Arguing by induction on p and using Theorems 2.13 and 2.14, we obtain the desired result. □

It would be interesting to find bijective proofs of Theorems 2.13 and 2.15.

2.5. Avoiding 132 and (d + 1)(d + 2) … k12 … d. In this subsection we consider involutions which avoid 132 and (d + 1)(d + 2) … k12 … d.

Example 2.16. By Proposition 2.1 we find that for n ≥ 1,

ℑ_{231}(n) = n; ℑ_{321}(n) = [n/2] + 1.

We remark that the n-involutions which avoid both 132 and 231 are the permutations of the form i(i − 1) … 1(i + 1)(i + 2) … n, 1 ≤ i ≤ n, and that the n-involutions which avoid both 132 and 321 are the permutations of the form (i+1)(i+2) … (2i)12 … i(2i+ 1)(2i + 2) … n, 0 ≤ i ≤ [n/2].

As an extension of Example 2.16, we consider the case T = {< k, d >}, where < k, d >= (d + 1, d + 2, …, k, 1, 2, …, d).

Theorem 2.17. For any k ≥ 2, k/2 ≥ d ≥ 1,

ℑ_{<k,d>}(x) = \frac{1}{x(U_{d}(t) − U_{d−1}(t))} [U_{d−1}(t) + \frac{U_{k−2d−1}(t)}{U_{k−d}(t)U_{k−d−1}(t)} ∑_{j=0}^{k−d−1} U_{j}(t)] , t = \frac{1}{2x}.

Proof. By Proposition 2.1, we have two possibilities for the block decomposition of an arbitrary π ∈ ℑ_{n}(132). Let us use Remark 2.2 to write an equation for ℑ_{<k,d>}(x). The contribution of the second decomposition above is xℑ_{<k,d>}(x). The contribution of the first decomposition above is given in two cases. First, if γ avoids 12 … (k − d), then β and δ avoid 12 … (k − d − 1), so we have x^{2}R_{k−d−1}(x^{2})ℑ_{12...(k−d)}(x), as in Theorem 2.8. Second, if γ contains 12 … (k − d) at least once then β and δ avoid 12 … (d − 1), so we have x^{2}R_{d−1}(x^{2})(ℑ_{<k,d>}(x) − ℑ_{12...(k−d)}(x)). Here we have used the fact that the generating function for those permutations in ℑ_{n}(132, < k, d >) which contain 12 … (k − d) at least once is given by ℑ_{<k,d>}(x) − ℑ_{12...(k−d)}(x). We now have

ℑ_{<k,d>}(x) = 1 + xℑ_{<k,d>}(x) + x^{2}R_{k−d−1}(x^{2})ℑ_{12...(k−d)}(x)

+ x^{2}R_{d−1}(x^{2})(ℑ_{<k,d>}(x) − ℑ_{12...(k−d)}(x)),

which means that

ℑ_{<k,d>}(x) = \frac{1}{1 − x − x^{2}R_{k−d−1}(x^{2})} · (1 + x^{2}ℑ_{12...(k−d)}(x)(R_{k−d−1}(x^{2}) − R_{d−1}(x^{2}))).

Hence, by Identity 1.4 together with the identity R_{a}(x) − R_{b}(x) = \frac{U_{a−b−1}(t)}{\sqrt{x}U_{a}(t)U_{b}(t)}, we get the desired result. □

Example 2.18. For all n ≥ 1, |ℑ_{3412}(n)| = F_{n}, the nth Fibonacci number.

We now give a bijective proof of Example 2.18. Any π ∈ 𝔖_{n}(132, 3412) can be written iπ′1(i+1)(i+2) ⋯ n, where 1 ≤ i ≤ n and π′ is (upon subtracting 1 from each element) also an involution avoiding both 132 and 3412. We map π to a word in {a, b^{2}}^{∗} of length n in the following way: a if π_{i} = i, b^{2} if π_{i} < i and nothing if π_{i} > i for all 1 ≤ i ≤ n. This mapping is clearly bijective.

2.6. Avoiding 132 and two other patterns. In this subsection we consider involutions which avoid 132 and two other patterns. We begin with an example.

Example 2.19. Let T′ = {123, 213} and T = {12, 21}. Equation 2.2 gives

ℑ_{123,213}(x) = \frac{1}{1 − x^{2}𝔖_{12,21}(x^{2})} + \frac{x}{1 − x^{2}𝔖_{12,21}(x^{2})}ℑ_{12,21}(x),

and 𝔖_{12,21}(x) = ℑ_{12,21}(x) = 1 + x; hence

ℑ_{123,213}(x) = \frac{1 + x + x^{2}}{1 − x^{2} − x^{4}}

which means that ℑ_{123,213}(2n) = F_{n+1} and ℑ_{123,213}(2n + 1) = F_{n} for all n ≥ 0, where F_{m} is the mth Fibonacci number.

We prove Example 2.19 by a bijective argument, in which we distinguish the cases of odd length from those of even length.

Any π ∈ ℑ_{2n+1}(132, 123, 213) can be written either (2n+1)π′1 or (2n)(2n+1)π′′21 or 1 (if n = 0), where π′ (upon subtracting 1 from each element) and π′′ (upon subtracting 2 from each element) are also involutions avoiding 132, 123 and 213 . We map π to a word of {a, b^{2}}^{∗} of length n in the following way: a if π_{i} = 2n+2−i, b^{2} if π_{i} = 2n+1−i, and nothing if π_{i} = 2n + 3 − i for all 1 ≤ i ≤ n. This mapping is clearly bijective.

Any π ∈ ℑ_{2n}(132, 123, 213) can be written either (2n)π′1 (this case includes 21, when n = 1) or (2n−1)(2n)π′′21 or 12 (if n = 1) or the empty involution (if n = 0), where π′ (upon subtracting 1 from each element) and π′′ (upon subtracting 2 from each element) are also involutions avoiding 132, 123 and 213. We map π to a word of {a, b^{2}}^{∗} of length n + 1 in the following way: a if π_{i} = 2n + 1 − i for all 1 ≤ i ≤ n − 1, b^{2} if π_{n} = n + 1, b^{2} if π_{i} = 2n − i for all 1 ≤ i ≤ n − 2, b^{2}a if π_{n−1} = n + 1, and aa if π_{n} = n. Moreover, the empty involution is mapped to a. This mapping is clearly bijective.

Using Proposition 2.1 and Theorem 2.6 it is easy to see the following.

Corollary 2.20. For all k ≥ 1,

ℑ_{12...k,213}(x) = ℑ_{(k−1)...21k,123}(x) = \frac{1 + x + x^{2} + ⋯ + x^{k−1}}{1 − x^{2} − x^{4} − ⋯ − x^{2(k−1)}} .

Example 2.21. Using Proposition 2.1 it is easy to see, for all n ≥ 1,

ℑ_{213,321}(n) = \frac{1}{2}(3 + (−1)^{n})  and  ℑ_{213,4321}(n) = [n/2] + 1.

Observe that the n-involutions avoiding 132, 213, and 321 which are not equal to 12 … n are the permutations of the form (m+1)(m+2) … n12 … m, where n = 2m and m ≥ 1. Similarly, the n-involutions avoiding 132, 213, and 4321 are the permutations of the form (n + 1 − i)(n + 2 − i) … n(i + 1)(i + 2) … (n − i)12 … i, where 0 ≤ i ≤ [n/2].

3. Avoiding 132 and containing another pattern

Let ℑ_{τ}^{r}(n) = |{π ∈ ℑ_{n}(132) : π contains τ exactly r times}| and let

ℑ_{τ}^{r}(x) = ∑_{n≥0} ℑ_{τ}^{r}(n)x^{n}

be the corresponding generating function. We begin with an example.

Example 3.1. By Proposition 2.1 it is easy to see

ℑ_{12}^{1}(x) = xℑ_{1}^{1}(x) + x^{2}ℑ_{12}^{1}(x),

which means that ℑ_{12}^{1}(x) = \frac{x^{2}}{1−x^{2}} .

As extension of Example 3.1, we consider the case τ = 12 … k.

Theorem 3.2. For all k ≥ 1,

ℑ_{12...k}^{1} = \frac{1}{U_{k} (\frac{1}{2x})}.

Proof. By Proposition 2.1, for all n ≥ k we have

ℑ_{12...k}^{1}(n) = ℑ_{12...(k−1)}^{1}(n − 1) + ∑_{j=1}^{[n/2]} 𝔖_{12...(k−1)}(j − 1)ℑ_{12...k}^{1}(n − 2j),

where 𝔖_{12...k}(j − 1) = |𝔖_{j−1}(132, 12 … k)|. Moreover, ℑ_{12...k}^{1}(n) = 0 for all n ≤ k − 1, and ℑ_{12...k}^{1}(k) = 1. As in the proof of Theorem 2.8, we have

ℑ_{12...k}^{1}(x) = xR_{k}(x^{2})ℑ_{12...(k−1)}^{1}(x).

Now the result follows by induction on k, with the initial condition ℑ_{1}^{1}(x) = x. □

We also have explicit formulas for the cases τ = 2134 … k and τ = 23 … k1.

Theorem 3.3. For all k ≥ 2,

ℑ_{2134...k}^{1} = \frac{1 − x^{2}}{U_{k} (\frac{1}{2x})}, ℑ_{23...k1}^{1}(x) = \frac{x^{3}}{(1 − x)U_{k−2} (\frac{1}{2x})}.

More generally, using Proposition 2.1 and an argument similar to that given in the proof of Theorem 2.8, we obtain the following result.

Theorem 3.4. For any k, r ≥ 1,

ℑ_{12...k}^{r}(x) = xℑ_{12...(k−1)}^{r}(x) + x^{2} ∑_{2a+b=r} 𝔖_{12...(k−1)}^{a}(x^{2})ℑ_{12...k}^{b}(x),

where 𝔖_{12...(k−1)}^{a}(x) is the generating function for the number of n-permutations containing 12 … (k − 1) exactly a times.

Krattenthaler [Kt] has found an explicit formula for the generating function 𝔖_{12...k}^{r}(x) for the number of 132-avoiding n-permutations containing 12 … k exactly r times, so Theorem 3.4 yields a recurrence for ℑ_{12...k}^{r}(x). Using Krattenthaler’s result [Kt] (see also [MV1, Theorem 3.1]), we obtain the following recurrence for ℑ_{12...k}^{r}(x) where r = 1, 2, …, 2k.

Theorem 3.5. Let k ≥ 1; for all r = 1, 2, …, 2k,

ℑ_{12...k}^{r}(x) = xℑ_{12...(k−1)}^{r}(x) + x^{2}R_{k−1}(x^{2})ℑ_{12...k}^{r}(x) + ∑_{2a+b=r, a>0} x^{a+1}ℑ_{12...k}^{b}(x)\frac{U_{k−1}^{a−1} (\frac{1}{2x})}{U_{k}^{a+1} (\frac{1}{2x})}.

When r = 2, the above Theorem yields an explicit formula for ℑ_{12...k}^{2}(x).

Corollary 3.6. For all k ≥ 1,

ℑ_{12...k}^{2}(x) = \frac{1}{U_{k} (\frac{1}{2x})} ∑_{i=1}^{k} \frac{∑_{j=0}^{k−i} U_{j} (\frac{1}{2x})}{U_{k+1−i} (\frac{1}{2x}) U_{k−i} (\frac{1}{2x})}.

4. Containing 132 once and avoiding another pattern

In this section we consider involutions which contain 132 exactly once and avoid another pattern. We first relate involutions containing 132 exactly once to 132-avoiding involutions.

Theorem 4.1. There is a bijection Ψ between n-involutions containing 132 exactly once having p fixed points (1 ≤ p ≤ n) and 132-avoiding (n − 2)-involutions having p fixed points.

Proof. Let π = π′xzπ′′yπ′′′ with π(x) = x, π(y) = z and 1 + x = y < z be an ninvolution containing 132 exactly once, where the subsequence xzy is of type 132 and π has p fixed points. We replace the subsequence xzy with a fixed point between π′′ and π′′′ in order to obtain a 132-avoiding (n−2)-involution having p fixed points. Note that the only way to have exactly one 132 subsequence in π is to have a cycle with a fixed point just to its left. Moreover, we must have y = x+1 in order to forbid another 132 subsequence, cycles are only allowed from π′ to π′′ and from π′ to π′′′ (and not from π′′, π′, π′′, π′′′ respectively to π′′′, π′, π′′, π′′′) and fixed points can only be into π′′′. Clearly the involution we obtain avoids 132 and in particular, the fixed point z − 2 cannot be a part of a 132-subsequence because it cannot be the 3 or 2 (all the elements on its left are greater than it) and it cannot be the 1 (there is no cycle starting on its right).

Let σ = σ′σ′′σ′′′tσ′′′′ be an involution with p fixed points, where σ(t) = t and σ(i) ≠ i for all 1 ≤ i < t (that is, t is the first fixed point), σ′(i) > t for all 1 ≤ i ≤ |σ′| (all the elements of σ′ are cycles ending within σ′′′′), σ′′(i) ∈ [|σ′σ′′|+1, t−1] for all 1 ≤ i ≤ |σ′′| and σ′′′(i) ∈ [|σ′| + 1, |σ′σ′′|] for all 1 ≤ i ≤ |σ′′′| (σ′′σ′′′ consists entirely of cycles from σ′′ to σ′′′). We modify the fixed point t by inserting a cycle starting between σ′′ and σ′′′ (and ending between σ′′′ and σ′′′′) and by adding a fixed point just to the right of σ′′ in order to obtain an involution of length n containing 132 once and having p fixed points. Proposition 2.1 leads immediately to the decomposition of σ. The involution we obtain contains 132 exactly once, in the form of the subsequence we modify and insert. There is no other 132-subsequence and in particular, the fixed point inserted and the start of the new cycle cannot be the 3 or 2 of another 132-subsequence (all the elements on their left are greater than them), the fixed point inserted and the start of the new cycle and the end of the new cycle cannot be the 1 of another 132-subsequence (there is no cycle starting on their right), the end of the new cycle cannot be the 3 of another 132-subsequence (because in that case the 2 must be connected to σ′ and the 1 must be the fixed point inserted or an element of σ′′′ that forms a 231-subsequence), and the end of the new cycle cannot be the 2 of another 132-subsequence (because in that case the 1 must be an element of σ′σ′′ or the start of the new cycle and the 3 must be the fixed point inserted or an element of σ′′′ that forms a 312-subsequence). So we have established a bijection between an involution π containing 132 once and a 132-avoiding involution σ of the forms given above, where t = z − 2, π′ corresponds to σ′σ′′, π′′ = σ′′′ and π′′′ corresponds to σ′′′′. □

For example, the involution 22 19 17 18 16 12 11 13 9 14 7 6 8 10 15 5 3 4 2 20 21 1 23, which contains 132 exactly once (the subsequence 9 14 10), corresponds to the 132-avoiding involution 20 17 15 16 14 10 9 11 7 6 8 12 13 5 3 4 2 18 19 1 21.

Corollary 4.2. The number of n-involutions containing 132 exactly once which have p fixed points, 1 ≤ p ≤ n, is the ballot number

\binom{n − 2}{\frac{n+p}{2} − 1} − \binom{n − 2}{\frac{n+p}{2}}.

Moreover, the number of n-involutions containing 132 exactly once is given by

\binom{n − 2}{[\frac{n−3}{2}]}.

Proof. This result is immediate from the bijection Ψ of Theorem 4.1 and Corollary 2.5. In fact, the number of n-involutions containing 132 exactly once is |ℑ_{n−2}(132)| if n is odd and |{π ∈ ℑ_{n−2}(132) having more than one fixed point }| if n is even. □

Of course, some of the following results can immediately be obtained from the bijection Ψ of Theorem 4.1 and the results of Section 2. Let 𝔏_{τ}(n) be the number of τ-avoiding n-involutions containing 132 exactly once, and let 𝔏_{τ}(x) = ∑_{n≥0} 𝔏_{τ}(n)x^{n} be the corresponding generating function. The following proposition, which is immediate from our definitions, is the basis for all of the other results in this section.

Proposition 4.3. Suppose π ∈ ℑ_{n} contains 132 exactly once and has π_{j} = n. Then exactly one of the following holds.

(1) π = (α, n) where α ∈ ℑ_{n−1} contains 132 exactly once;

(2) π = (α, n, β, γ, j) where 1 ≤ j ≤ n/2, γ = α^{−1}, α is an 132-avoiding permutation of the numbers n − 1, n − 2, …, n − j + 1, and β is an involution of the numbers j + 1, j + 2, …, n − j which contains 132 exactly once;

(3) π = (α, m, 2m + 1, γ, m + 1) where n = 2m + 1, γ = α^{−1} + m + 1, and γ ∈ 𝔖_{m−1}(132).

For example, for n = 5, the only three involutions containing 132 exactly once are 13245, 52431 and 42513. These illustrate the cases (1), (2) and (3) of Proposition 4.3, respectively. We can use Proposition 4.3 to find the generating function for the number of ninvolutions containing 132 exactly once.

Theorem 4.4. The generating function for the number of n-involutions containing 132 exactly once is given by

𝔏_{∅}(x) = \frac{x^{3}C(x^{2})}{1 − x − x^{2}C(x^{2})}.

Proof. By Proposition 4.3, we have three possibilities for the block decomposition of an arbitrary π ∈ ℑ_{n} containing 132 exactly once. Let us use Remark 2.2 to write an equation for 𝔏_{∅}(x). The contribution of the first decomposition above is x𝔏_{∅}(x), the contribution of the second decomposition above is x^{2}C(x^{2})𝔏_{∅}(x), and the contribution of the third decomposition above is x^{3}C(x^{2}). Hence 𝔏_{∅}(x) = x𝔏_{∅}(x)+x^{2}C(x^{2})𝔏_{∅}(x)+ x^{3}C(x^{2}). □

Example 4.5. By Proposition 4.3, |𝔏_{123}(n)| = 2^{(n−3)/2} when n is odd and |𝔏_{123}(n)| = 0 otherwise. In addition, |𝔏_{1234}(n)| = F_{n−3}, the (n − 3)th Fibonacci number, and 𝔏_{12345}(n) = 3^{[(n−3)/2]}.

Again, the case of varying k is more interesting. As an extension of Example 4.5, we consider the case τ = 12 … k.

Theorem 4.6. For all k ≥ 1,

𝔏_{12...k}(x) = \frac{x}{U_{k} (\frac{1}{2x})} ∑_{j=1}^{k−2} U_{j} (\frac{1}{2x}) .

Proof. By Proposition 4.3 and Remark 2.2 (as in the proof of Theorem 4.4), together with the fact that the generating function for |𝔖_{n}(132, 12 … k)| is given by R_{k}(x) (see [CW]), we have

𝔏_{12...k}(x) = x𝔏_{12...(k−1)} + x^{2}R_{k−1}(x^{2})𝔏_{12...k}(x) + x^{3}R_{k−1}(x^{2}).

By Identity 1.4, we get

𝔏_{12...k}(x) = xR_{k}(x^{2})𝔏_{12...(k−1)}(x) + x^{3}R_{k−1}(x^{2})R_{k}(x^{2}).

Hence, by induction on k together with Example 4.5, we get the desired result. □

The case τ = 2134 … k is similar to the case τ = 12 … k.

Theorem 4.7. For all k ≥ 3,

𝔏_{2134...k}(x) = \frac{x}{U_{k} (\frac{1}{2x})} [xU_{2} (\frac{1}{2x}) + ∑_{j=2}^{k−2} U_{j} (\frac{1}{2x})] .

Proof. Arguing as in the proof of Theorem 4.6, we use the fact that the generating function for |𝔖_{n}(132, 2134 … k)| is given by R_{k}(x) (see [MV2]) to obtain

𝔏_{2134...k}(x) = xR_{k}(x^{2})𝔏_{2134...(k−1)}(x) + x^{3}R_{k−1}(x^{2})R_{k}(x^{2}).

Hence, by induction on k with the initial value 𝔏_{213}(x) = x^{4}R_{3}(x^{2}), we easily have the desired result. □

Example 4.8. Theorem 4.7 yields 𝔏_{2134}(2n + 3) = 𝔏_{2134}(2n + 4) = F_{2n}, the (2n)th Fibonacci number, for all n ≥ 0.

Example 4.9. Proposition 4.3 yields 𝔏_{231}(n) = 1 and 𝔏_{2341}(n) = 2^{[(n−1)/2]} − 1 for all n ≥ 1.

As an extension of Example 4.9, we consider the case τ = 23 … k1.

Theorem 4.10. For all k ≥ 3,

𝔏_{23...k1}(x) = \frac{x^{2}U_{k−3} (\frac{1}{2x})}{(1 − x)U_{k−2} (\frac{1}{2x})} [1 + \frac{1}{U_{k−1} (\frac{1}{2x})} ∑_{j=1}^{k−3} U_{j} (\frac{1}{2x})] .

Proof. As in the proof of Theorem 4.6, we have

𝔏_{23...k1}(x) = x𝔏_{23...k1}(x) + x^{2}R_{k−2}(x^{2})𝔏_{12...(k−1)}(x) + x^{3}R_{k−2}(x^{2}).

By using Theorem 4.6 we get the desired result. □

More generally, we present the following explicit expression when τ =< k, d >.

Theorem 4.11. For k ≥ 4 and 2 ≤ d ≤ k/2 we have

𝔏_{<k,d>}(x)

= \frac{R_{d}(x^{2})}{1 − xR_{d}(x^{2})} [x^{2}R_{k−d−1}(x^{2}) + \frac{x^{2}(R_{k−d−1}(x^{2}) − R_{d−1}(x^{2}))}{U_{k−d} (\frac{1}{2x})} ∑_{j=1}^{k−d−2} U_{j} (\frac{1}{2x})] .

Proof. By Proposition 4.3, we have three possibilities for the block decomposition of an arbitrary π ∈ ℑ_{n} containing 132 exactly once. Let us use Remark 2.2 to write an equation for 𝔏_{<k,d>}(x). The contribution of the first decomposition above is x𝔏_{<k,d>}(x). The contribution of the second decomposition above is as follows: if π′ contains 12 … (k − d − 1) then π contains < k, d > which is a contradiction, so π′ avoids 12 … (k − d − 1). Therefore the contribution of the second decomposition is x^{3}R_{k−d−1}(x^{2}). Finally, the contribution of the third decomposition above involves two cases: π′′ contains 12 … (k − d) or avoids 12 … (k − d). In the first case we have x^{2}R_{d−1}(x^{2})(𝔏_{<k,d>}(x) − 𝔏_{12...(k−d)}(x)), and in the second case we have x^{2}R_{k−d−1}(x)𝔏_{12...(k−d)}(x). Therefore, if we use Theorem 4.6 to write an equation for 𝔏_{<k,d>}(x) we obtain the desired result. □

5. Containing 132 once and containing another pattern

Let 𝔏_{τ}^{r}(n) denote the number of n-involutions containing 132 exactly once and containing τ exactly r times. Let 𝔏_{τ}^{r}(x) = ∑_{n≥0} 𝔏_{τ}^{r}(n)x^{n} be the corresponding generating function. We begin with the following result.

Theorem 5.1. For all k ≥ 1,

𝔏_{12...k}^{1}(x) = 0.

Proof. By Proposition 4.3 and by Remark 2.2, it is easy to see

𝔏_{12...k}^{1}(x) = x𝔏_{12...(k−1)}^{1}(x) + x^{2}R_{k−1}(x^{2})𝔏_{12...k}^{1}(x).

Moreover, 𝔏_{12}^{1}(x) = 0 by definition, hence the theorem holds by induction on k. □

Next we consider the case τ = 23 … k1.

Theorem 5.2. For all k ≥ 1,

𝔏_{23...k1}^{1}(x) = 0.

Example 5.3. Proposition 4.3 yields that 𝔏_{21}^{1}(n) = 1 for n ≥ 3.

As an extension of Example 5.3, we consider the case τ = 2134 … k.

Theorem 5.4. For all k ≥ 3,

𝔏_{2134...k}^{1}(x) = \frac{x(1 − x^{2})}{U_{k} (\frac{1}{2x})}.

Proof. Using Proposition 4.3 and Remark 2.2, it is easy to see that

𝔏_{2134...k}^{1}(x) = x𝔏_{2134...(k−1)}^{1}(x) + x^{2}R_{k−1}(x^{2})𝔏_{2134...k}(x)

and 𝔏_{21}^{1}(x) = x^{3}/(1 − x). The result follows by induction on k. □

Acknowledgments: The authors are grateful to Eric S. Egge for his careful reading of the manuscript.

References

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

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

[CC] L. Chottin, R. Cori, Une preuve combinatoire de la rationalité d’une série génératrice associée aux arbres, R.A.I.R.O. Informatique théorique 16 n^{o} 2 (1982), 113–128.

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

[CGHK] F.R.K. Chung, R.L. Graham, V.E. Hoggat and M. Kleiman, The number of Baxter permutations, J. Comb. Th. A 24 (1978), 382–394.

[E] A. Errera, Un problème d’énumération, Mémoires publiées par l’Académie royale de Belgique, Bruxelles, 11 (1931).

[Ge] I.M. Gessel, Symmetric functions and P-recursiveness, J. Comb. Th. A 53 (1990), 257–285.

[Gi] S. Gire, Arbres, permutations à motifs exclus et cartes planaires : quelques problèmes algorithmiques et combinatoires, Ph.D.-thesis, Université Bordeaux 1, France (1993).

[G-B] D. Gouyou–Beauchamps, Standard Young tableaux of height 4 and 5, European J. Combin.

10 (1989), 69–82.

[Gu] O. Guibert, Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young, Ph.D.-thesis, Université Bordeaux 1, France (1995).

[GPP] O. Guibert, E. Pergola and R. Pinzani, Vexillary involutions are enumerated by Motzkin numbers, Annals of Comb. 5 (2001), 153–174.

[HM] F. K. Hwang, C. L. Mallows, Enumerating nested and consecutive partitions, J. Combin. Theory Ser. A, 70 (1995), 323–333.

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

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

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

[Kw] G. Kreweras, Sur les éventails de segments, Cahiers du BURO 15 (1970), 3–41.

[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. 126 (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.

[P] E. Pergola, ECO: a Methodology for Enumerating Combinatorial Objects, Ph.D.-thesis, University of Firenze, Italy (1998).

[Re] A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. Math. 41 (1981), 115–136.

[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), Article #R38.

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

[SP] N.J.A. Sloane, S. Plouffe, The encyclopedia of integer sequences, Academic Press (1995).

[S] R. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986, xi + 306 pages; second printing, Cambridge University Press, Cambridge, 1996.

[V] G. X. Viennot, Heaps of pieces 1: basic definitions and combinatorial lemmas, G. Labelle and P. Leroux editors, Combinatoire énumérative, Lecture Notes in Math. 1234 (1986), pp. 321–350.

[W1] J. West, Permutations with forbidden subsequences and stack-sortable permutations, Ph.D.- thesis, Massachusetts Institute of Technology, Cambridge (1990).

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