RESTRICTED 132-DUMONT PERMUTATIONS

Toufik Mansour ^{1}

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

                              toufik@math.chalmers.se

Abstract

In [D] Dumont showed that certain classes of permutations on n letters are counted by the Genocchi numbers. In particular, Dumont showed that the (n + 1)st Genocchi number is the number of permutations on 2n letters with the following properties: (1) each even integer must be followed by a smaller integer (this rule disallows the sequence from ending with an even integer), (2) each odd integer is either followed by a larger integer or is final in the sequence. We call such permutations by Dumont permutations of the first kind. In this paper we study the number of Dumont permutations of the first kind on n letters avoiding the pattern 132 and avoiding (or containing exactly once) an arbitrary pattern on k letters. In several interesting cases the generating function depends only on k.

Keywords: Dumont permutations, restricted permutations, generating functions.

1. Introduction

Classical patterns. Let α ∈ 𝔖_{n} and τ ∈ 𝔖_{k} be two permutations. We say that α contains τ if there exists a subsequence 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n such that (α_{i_{1}}, …, α_{i_{k}}) is order-isomorphic to τ; in such a context τ is usually called a pattern. We say that α avoids τ, or is τ-avoiding, if such a subsequence does not exist. The set of all τ-avoiding permutations in 𝔖_{n} is denoted 𝔖_{n}(τ). For an arbitrary finite collection of patterns T, we say that α avoids T if α avoids any τ ∈ T; the corresponding subset of 𝔖_{n} is denoted 𝔖_{n}(T).

While the case of permutations avoiding a single pattern has attracted much attention, the case of multiple pattern avoidance remains less investigated. In particular, it is natural, as the next step, to consider permutations avoiding pairs of patterns τ_{1}, τ_{2}. This problem was solved completely for τ_{1}, τ_{2} ∈ 𝔖_{3} (see [SS]), for τ_{1} ∈ 𝔖_{3} and τ_{2} ∈ 𝔖_{4} (see [W]), and for τ_{1}, τ_{2} ∈ 𝔖_{4} (see [Bo1, Km] and references therein). Several recent papers [CW, MV1, Kr, 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 t times. Such a problem for certain τ_{1}, τ_{2} ∈ 𝔖_{3} and t = 1 was investigated in [R], and for certain τ_{1} ∈ 𝔖_{3}, τ_{2} ∈ 𝔖_{k} in [RWZ, MV1, Kr]. The tools involved in these papers include generating trees, continued fractions, Chebyshev polynomials, and Dyck words. Also, the tools involved in these papers include many sequences, for example sequence of Catalan numbers, Fibonacci numbers, and Pell numbers.

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

We denote the nth Catalan number by C_{n} = \frac{1}{n+1} \binom{2n}{n}. The generating function for the Catalan

numbers is denoted by C(x), that is, C(x) = ∑_{n≥0} C_{n}x^{n} = \frac{1−\sqrt{1−4x}}{2x}.

Generalized patterns. In [BS] introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. We write a classical pattern with dashes between any two adjacent letters of the pattern, say 1342, as 1-3-4-2, and if we write, say 24-3-1, then we mean that if this pattern occurs in permutation π ∈ 𝔖_{n}, then the letters in the permutation π that correspond to 2 and 4 are adjacent (see [C]). For example, the permutation π = 35421 has only two occurrences of the pattern 23-1, namely the subsequences 352 and 351, whereas π has four occurrences of the pattern 2-3-1, namely the subsequences 352, 351, 342, and 341.

Claesson [C] presented a complete solution for the number of permutations avoiding any single generalized pattern of length three with exactly one adjacent pair of letters. Claesson and Mansour [CM] presented a complete solution for the number of permutations avoiding any double generalized patterns of length three with exactly one adjacent pair of letters. Kitaev [Ki] investigate simultaneous avoidance of two or more 3-letters generalized patterns without internal dashes. Later, Mansour [M1, M2] (for more details see [M3]) presented a general approach to study the number of permutations avoiding 1-3-2 and avoiding (or containing exactly once) an arbitrary generalized pattern.

Dumont permutations. Dumont [D] showed that certain classes of permutations in 𝔖_{n} are counted by the Genocchi numbers (see [SP, Sequence A001469(M3041)]). Dumont showed that the (n + 1)st Genocchi number is the number of permutations in 𝔖_{2n} with the following properties: (1) each even integer must be followed by a smaller integer (this rule disallows the sequence from ending with an even integer), (2) each odd integer is either followed by a larger integer or is final in the sequence. We call such permutations by Dumont permutations of the first kind. For example, 2143, 3421, and 4213 are the all Dumont permutations of the first kind of length 4.

Dumont [D] defined another type of permutations in 𝔖_{n} and showed that the (n + 1)st Genocchi number is the number of permutations in 𝔖_{2n} with the following properties: (1) π_{i} < i for any even position i, (2) π_{i} ≥ i for any odd position i. We call such permutations by Dumont permutations of the second kind. For example, 2143, 3142, 4132 are the all Dumont permutations of the second kind of length 4.

Remark 1.1. Let π ∈ 𝔖_{n} be any Dumont permutation of the second kind; since π_{2} < 2 we get π_{2} = 1. Hence, it is easy to see that there are no Dumont permutations of the second kind in 𝔖_{n}(132) for all n ≥ 4. So, in this paper we discus only the case of Dumont permutations of the first kind.

We define for all r ≥ 2,

Q_{r}(x) = 1 + \frac{x^{2}Q_{r−1}(x)}{1 − x^{2}Q_{r−2}(x)}. (1.1)

We denote the solution of Recurrence 1.1 with Q_{0}(x) = 0 and Q_{1}(x) = 1 by F_{r}(x), and we denote the solution of Recurrence 1.1 with Q_{0}(x) = Q_{1}(x) = 1 by G_{r}(x). For example, F_{2}(x) = 1 + x^{2}, F_{3}(x) = \frac{1+x^{4}}{1−x^{2}} , G_{2}(x) = \frac{1}{1−x^{2}} , and G_{3}(x) = \frac{1−x^{2}+x^{4}}{(1−x^{2})^{2}} . Evidently, F_{r}(x) and G_{r}(x) are a rational functions in x^{2}, and for all r ≥ 1,

F_{r}(x) = 1 + ∑_{j=1}^{r−1} \frac{x^{2j}}{∏_{m=r−1−j}^{r−2}(1 − x^{2}F_{m}(x))} and G_{r}(x) = 1 + ∑_{j=1}^{r−1} \frac{x^{2j}}{∏_{m=r−1−j}^{r−2}(1 − x^{2}G_{m}(x))}. (1.2)

Example 1.2. Using Recurrence 1.1 it is easy to see that

F_{4}(\sqrt{x}) = ∑_{n≥0}(f_{n+2} + f_{n} − 2)x^{n} and G_{4}(\sqrt{x}) = 1 + x + ∑_{n≥2}(3 · 2^{n−2} − 1)x^{n},

where f_{n} is the nth Fibonacci number.

Organization of the paper. In this paper we use generating function techniques to study those Dumont permutations of the first kind which avoid 132 and avoid (or contain exactly once) an arbitrary pattern on k letters. In several interesting cases the generating function depends only on k.

The paper is organized as follows. The case of Dumont permutations of the first kind avoiding both 132 and τ is treated in Section 2. We present a simple structure for any Dumont permutation of the first kind avoiding 132. This structure can be obtained explicitly for several interesting cases, including classical patterns and generalized patterns. This allows us to find explicitly some statistics on Dumont permutations of the first kind which avoid 132. The case of avoiding 132 and containing another pattern τ exactly once is treated in Section 3. Again, we find explicitly the generating function for several interesting cases of τ, including classical patterns and generalized patterns.

Most of the explicit solutions obtained in Sections 2-4 involve the generating functions F_{k}(x) and G_{k}(x).

2. Dumont permutations of the first kind which avoid 132 and another pattern

Let 𝔇_{τ}^{(1)}(n) denote the number of Dumont permutations of the first kind in 𝔖_{n}(132, τ), and let 𝔇_{τ}^{(1)}(x) = ∑_{n≥0} 𝔇_{τ}^{(1)}(n)x^{n} be the corresponding generating function. In this section we describe a method for enumerating Dumont permutations of the first kind which avoid 132 and another pattern and we use our method to enumerate 𝔇_{τ}^{(1)}(n) for various τ. We begin with an observation concerning the structure of the Dumnot permutations of the first kind avoiding 132 which holds immediately from definitions.

Proposition 2.1. For any π ∈ 𝔇_{n}^{(1)}(132) such that π_{j} = n, there holds one of the following assertions:

1. if n is odd number then π = (π′, n), where π′ ∈ 𝔇_{n−1}^{(1)}(132);

2. if n is even number then π = (π′, n, π′′) such that π′ is a Dumont permutation of the first kind on the numbers n − j + 1, n − j + 2, …, n − 1, π′′ is nonempty Dumont permutation of the first kind on the numbers 1, 2, ⋯, n − j, and j = 1, 2, 4, …, n − 2.

2.1. τ = ∅. As a corollary of Proposition 2.1 we find an explicit formula for the number of 132avoiding Dumont permutations of the first kind in 𝔖_{n}.

Theorem 2.2. The generating function for the number of 132-avoiding Dumont permutations of the first kind in 𝔖_{n} is given by (1 + x)C(x^{2}). In other words, the number of 132-avoiding Dumont permutations of the first kind in 𝔖_{n} is given by C_{[n/2]}, which is the [n/2]th Catalan number.

Proof. By Proposition 2.1, we have two possibilities for block decomposition of an arbitrary π ∈ 𝔇_{n}^{(1)}(132). Let us write an equation for 𝔇_{∅}^{(1)}(x). The contribution of the first decomposition above equals

∑_{n≥0} 𝔇_{∅}^{(1)}(2n + 1)x^{2n+1} = x ∑_{n≥0} 𝔇_{∅}^{(1)}(2n)x^{2n},

equivalently,

𝔇_{∅}^{(1)}(x) − 𝔇_{∅}^{(1)}(−x) = x(𝔇_{∅}^{(1)}(x) + 𝔇_{∅}^{(1)}(−x)). (2.1)

The contribution of the second decomposition above equals

∑_{n≥1} 𝔇_{∅}^{(1)}(2n)x^{2n} = ∑_{n≥1} 𝔇_{∅}^{(1)}(2n − 1)x^{2n} + ∑_{n≥1} ∑_{j=0}^{n} 𝔇_{∅}^{(1)}(2j + 1)𝔇_{∅}^{(1)}(2n + 2 − 2j)x^{2n},

equivalently,

\begin{matrix}𝔇_{∅}^{(1)}(x) + 𝔇_{∅}^{(1)}(−x) − 2 = \\ = x(𝔇_{∅}^{(1)}(x) − 𝔇_{∅}^{(1)}(−x)) + \frac{x}{2}(𝔇_{∅}^{(1)}(x) − 𝔇_{∅}^{(1)}(−x))(𝔇_{∅}^{(1)}(x) + 𝔇_{∅}^{(1)}(−x) − 2). \end{matrix} (2.2)

By putting 𝔇_{∅}^{(1)}(x) = (1 + x)A(x) in Equations 2.1 and 2.2 it is easy to see that A(x) = C(x^{2}).

2.2. A classical pattern τ = 12 … k. Let us start by the following example.

Example 2.3. By definitions we have 𝔇_{1}^{(1)}(x) = 1 and 𝔇_{12}^{(1)}(x) = 1 + x + x^{2}.

The case of varying k is more interesting. As an extension of Example 2.3, let us consider the case τ = 12 … k.

Theorem 2.4. Let A_{k}(x) = \frac{1}{2}(𝔇_{12...k}^{(1)}(x) + 𝔇_{12...k}^{(1)}(−x)) and B_{k}(x) = \frac{1}{2}(𝔇_{12...k}^{(1)}(x) − 𝔇_{12...k}^{(1)}(−x)) for all k ≥ 0. Then

A_{k}(x) = F_{k}(x), B_{k}(x) = xF_{k−1}(x), and 𝔇_{12...k}^{(1)}(x) = F_{k}(x) + xF_{k−1}(x).

Proof. Using the same arguments as in the proof of Theorem 2.2 we get

𝔇_{12...k}^{(1)}(x) − 𝔇_{12...k}^{(1)}(−x) = x(𝔇_{12...(k−1)}^{(1)}(x) + 𝔇_{12...(k−1)}^{(1)}(−x)),

and

\begin{matrix}𝔇_{12...k}^{(1)}(x) + 𝔇_{12...k}^{(1)}(−x) − 2 = x(𝔇_{12...k}^{(1)}(x) − 𝔇_{12...k}^{(1)}(−x))+ \\ +\frac{x}{2}(𝔇_{12...(k−1)}^{(1)}(x) − 𝔇_{12...(k−1)}^{(1)}(−x))(𝔇_{12...k}^{(1)}(x) + 𝔇_{12...k}^{(1)}(−x) − 2). \end{matrix}

The rest is easy to check by the definitions of A_{k} and B_{k}.

Example 2.5. Theorem 2.4, for k = 3, yields 𝔇_{123}^{(1)}(x) = \frac{1+x+x^{4}−x^{5}}{1−x^{2}} . In other words, the number of 132-avoiding Dumont permutation of the first kind in 𝔖_{n}(123) is given by 1+(−1)^{n} for all n ≥ 4, and 1 for n = 0, 1, 2, 3. An another example, Theorem 2.4, for k = 4, yields 𝔇_{1234}^{(1)}(x) = \frac{1+2x+x^{2}+2x^{6}+x^{7}+x^{8}}{(1+x)(1−x^{2}−x^{4})} . In other words, the number of 132-avoiding Dumont permutation of the first kind in 𝔖_{n}(1234) is f_{n/2+2} +f_{n/2} −2 if n is even number, otherwise 2 for all n ≥ 2, where f_{n} is the nth Fibonacci number.

As an extension of Theorem 2.4, let us define

𝔄(x_{1}, x_{2}, x_{3}, …) = ∑_{π∈𝔇^{(1)}} ∏_{j≥1} x_{1}^{12...j(π)},

where 𝔇^{(1)} is the set of all Dumont permutations of the first kind of all sizes including the empty permutation, and τ(π) is the number of occurrences of τ in π. Let

\begin{matrix}A^{(1)}(x_{1}, x_{2}, x_{3}, …) = \frac{1}{2}(𝔄(x_{1}, x_{2}, x_{3}, …) + 𝔄(−x_{1}, x_{2}, x_{3}, …)), \\ B^{(1)}(x_{1}, x_{2}, x_{3}, …) = \frac{1}{2}(𝔄(x_{1}, x_{2}, x_{3}, …) − 𝔄(−x_{1}, x_{2}, x_{3}, …)). \end{matrix}

Using the same arguments as in the proof of Theorem 2.4, we obtain the following.

Theorem 2.6. We have

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

and

B^{(1)}(x_{1}, x_{2}, x_{3}, …) = x_{1}A^{(1)}(x_{1}x_{2}, x_{2}x_{3}, x_{3}x_{4}, …).

Aa an application to Theorem 2.6, for x_{1} = x and x_{j} = 1, j ≥ 2, we get that

B^{(1)}(x, 1, 1, …) = xA^{(1)}(x, 1, 1, …),

and

A^{(1)}(x, 1, 1, …) = \frac{1}{1 − \frac{x^{2}}{1 − \frac{x^{2}}{...}}} = C(x^{2}).

Hence, we have 𝔇_{∅}^{(1)}(x) = (1 + x)C(x^{2}) (see Theorem 2.2).

An another application for Theorem 2.6 is the number of right to left maxima. Let π ∈ 𝔖_{n}, π_{i} is a right to left maxima if π_{i} > π_{j} for all i < j. We denote the number of right to left maxima of π by rlm(π). In [BCS, Proposition 5] proved

lrm(π) = ∑_{j≥1} 12 … j(π)(−1)^{j−1}.

Therefore,

∑_{π∈𝔇^{(1)}} x^{|π|}y^{rlm(π)} = 𝔄(xy, y^{−1}, y, y^{−1}, …)

together with Theorem 2.6 and A^{(1)}(x, 1, 1, …) = C(x^{2}) we get

∑_{π∈𝔇^{(1)}} x^{|π|}y^{rlm(π)} = 1 + xC(x^{2})y + ∑_{n≥2} x^{2n−2}C^{n−1}(x^{2})y^{n}.

Corollary 2.7. The generating function for the number of Dumont permutations of the first kind avoiding 132 and having exactly k right to left maxima is given by x^{2k−2}C^{k−1}(x^{2}) for all k ≥ 2, and x^{k}C^{k}(x^{2}) for k = 0, 1.

2.3. A classical pattern τ = 2134 … k. Similarly as in Theorem 2.4, we obtain the case τ = 2134 … k.

Theorem 2.8. For all k ≥ 2,

𝔇_{213...k}^{(1)}(x) = G_{k−1}(x) + xG_{k−2}.

Example 2.9. Theorem 2.8 for k = 3, 4 yields 𝔇_{213}^{(1)}(x) = \frac{1+x−x^{3}}{1−x} and 𝔇_{2134}^{(1)}(x) = \frac{1+x−x^{2}−x^{3}+x^{4}}{(1−x^{2})^{2}} .

2.4. A generalized pattern 12-3- ⋯ -k. In this subsection we use the notation of generalized patterns (see Section 1). For example, we write the classical pattern 132 as 1-3-2.

By definitions, we get 𝔇_{12}^{(1)}(x) = 1+x+x^{2}. So, by the same arguments as in the proof of Theorem 2.4, together with

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

we obtain the following.

Theorem 2.10. For all k ≥ 1,

𝔇_{12-3-...-k}^{(1)}(x) = 𝔇_{1-2-3-...-k}^{(1)}(x) = F_{k}(x) + xF_{k−1}(x).

A comparison of Theorem 2.4 with Theorem 2.10 suggests that there should exist a bijection between the sets 𝔖_{n}(1-3-2, 12-3- ⋯ -k) and 𝔖_{n}(1-3-2, 1-2-3- ⋯ -k). However, we failed to produce such a bijection, and finding it remains a challenging open question.

Now, let us define

𝔅(x_{1}, x_{2}, x_{3}, …) = ∑_{π∈𝔇^{(1)}} x_{1}^{1(π)} ∏_{j≥2} x_{1}^{12-3-...-j(π)},

where 𝔇^{(1)} is the set of all Dumont permutations of the first kind of all sizes including the empty permutation, and τ(π) is the number of occurrences of τ in π. Let

\begin{matrix}A^{(2)}(x_{1}, x_{2}, x_{3}, …) = \frac{1}{2}(𝔅(x_{1}, x_{2}, x_{3}, …) + 𝔅(−x_{1}, x_{2}, x_{3}, …)), \\ B^{(2)}(x_{1}, x_{2}, x_{3}, …) = \frac{1}{2}(𝔅(x_{1}, x_{2}, x_{3}, …) − 𝔅(−x_{1}, x_{2}, x_{3}, …)). \end{matrix}

Using the same arguments as those in the proof of Theorem 2.4, we get

Theorem 2.11.

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

and

B^{(2)}(x_{1}, x_{2}, x_{3}, …) = x_{1} − x_{1}x_{2} + x_{1}x_{2}A^{(2)}(x_{1}, x_{2}x_{3}, x_{3}x_{4} …).

Let π ∈ 𝔖_{n}; we say π_{j} is a rise for π if π_{j} < π_{j+1} for all j = 1, 2, …, n − 1. We denote the number of rises of π by rises(π). By definitions, we have

∑_{π∈𝔇^{(1)}} x^{|π|}y^{rises(π)} = x − xy + (1 + xy)A^{(2)}(x, y, 1, 1, …),

so an application for Theorem 2.11 we get

Corollary 2.12. The generating function ∑_{π∈𝔇^{(1)}} x^{|π|}y^{rises(π)} is given by

\frac{1 + xy − 2x^{2}y + 2x^{2}y^{2} − (1 + xy)\sqrt{1 − 4x^{2}y}}{2x^{2}y^{2}} .

In other words, the generating function for Dumont permutations of the first kind avoiding 1-3-2 with exactly k rises is given by C_{k}x^{2k+1} + C_{k+1}x^{2k+2} for all k ≥ 1, and 1 + x + x^{2} for k = 0, where C_{m} is the mth Catalan number.

2.5. A generalized pattern τ = 21-3- ⋯ -k. In this subsection, we use the notation of generalized patterns (see Section 1). For example, we write the classical pattern 132 as 1-3-2.

By definitions, we get 𝔇_{21}^{(1)}(x) = 1 + x. So, by the same arguments as in the proof of Theorem 2.4 together with

𝔇_{21}^{(1)}(x) = 𝔇_{2-1}^{(1)}(x) = 1 + x,

we obtain the following.

Theorem 2.13. For all k ≥ 2,

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

A comparison of Theorem 2.8 with Theorem 2.13 suggests that there should exist a bijection between the sets 𝔖_{n}(1-3-2, 21-3- ⋯ -k) and 𝔖_{n}(1-3-2, 2-1-3- ⋯ -k). However, we failed to produce such a bijection, and finding it remains a challenging open question.

Now, let us define

ℭ(x_{1}, x_{2}, x_{3}, …) = ∑_{π∈𝔇^{(1)}} x_{1}^{1(π)} ∏_{j≥2} x_{1}^{21-3-...-j(π)},

where 𝔇^{(1)} is the set of all Dumont permutations of the first kind of all sizes including the empty permutation, and τ(π) is the number of occurrences of τ in π. Let

\begin{matrix}A^{(3)}(x_{1}, x_{2}, x_{3}, …) = \frac{1}{2}(ℭ(x_{1}, x_{2}, x_{3}, …) + ℭ(−x_{1}, x_{2}, x_{3}, …)), \\ B^{(3)}(x_{1}, x_{2}, x_{3}, …) = \frac{1}{2}(ℭ(x_{1}, x_{2}, x_{3}, …) − ℭ(−x_{1}, x_{2}, x_{3}, …)). \end{matrix}

Using the same arguments as in the proof of Theorem 2.4, we get the following.

Theorem 2.14. We have

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

and

B^{(3)}(x_{1}, x_{2}, x_{3}, …) = x_{1}A^{(3)}(x_{1}, x_{2}x_{3}, x_{3}x_{4} …).

Let π ∈ 𝔖_{n}; we say that π_{j} is a descent for π if π_{j} > π_{j+1} for all j = 1, 2, …, n − 1. We denote the number of descents of π by descents(π). By definitions, we have

∑_{π∈𝔇^{(1)}} x^{|π|}y^{decents(π)} = (1 + x)A^{(3)}(x, y, 1, 1, …),

therefore an application for Theorem 2.14 we get

Corollary 2.15. The generating function ∑_{π∈𝔇^{(1)}} x^{|π|}y^{descents(π)} is given by (1+x)C(x^{2}y). In other words, the generating function for Dumont permutations of the first kind avoiding 1-3-2 with exactly k descents is given by C_{k}x^{2k+1} + C_{k}x^{2k+2} for all k ≥ 0, where C_{m} is the mth Catalan number.

2.6. A classical pattern τ = 23 … k1. Again, Proposition 2.1 gives a complete answer for τ = 23 … k1.

Theorem 2.16. For all k ≥ 3,

𝔇_{23...k1}^{(1)}(x) = 1 + x + \frac{x^{2}(1 + x)}{1 − x^{2} − x^{2}F_{k−3}(x)}.

Proof. Using the same arguments as in the proof of Theorem 2.2 we get

𝔇_{23...k1}^{(1)}(x) − 𝔇_{23...k1}^{(1)}(−x) = x(𝔇_{23...k1}^{(1)}(x) + 𝔇_{23...k1}^{(1)}(−x)),

and

\begin{matrix}𝔇_{23...k1}^{(1)}(x) + 𝔇_{23...k1}^{(1)}(−x) − 2 = x(𝔇_{23...k1}^{(1)}(x) − 𝔇_{23...k1}^{(1)}(−x))+ \\ +\frac{x}{2}(𝔇_{12···(k−2)}^{(1)}(x) − 𝔇_{12...(k−2)}^{(1)}(−x))(𝔇_{23...k1}^{(1)}(x) + 𝔇_{23...k1}^{(1)}(−x) − 2). \end{matrix}

The rest is easy to check by the definitions of F_{k}(x) together with Theorem 2.4.

Example 2.17. Theorem 2.16, for k = 5, yields 𝔇_{23451}^{(1)}(x) = \frac{(1+x)(1−x^{2}−x^{4})}{1−2x^{2}−x^{4}}. In other words, the number of Dumont permutation of the first kind in 𝔖_{n}(132, 23451) is given by P_{[n/2]}, which is the [n/2]th Pell number for all n ≥ 2.

3. Dumont permutations of the first kind which avoid 132 and contain another pattern exactly once

Let 𝔇_{τ;r}^{(1)}(n) denote the number of Dumont permutations of the first kind in 𝔖_{n}(132) containing τ exactly r times, and let 𝔇_{τ;r}^{(1)}(x) = ∑_{n≥0} 𝔇_{τ;r}^{(1)}(n)x^{n} be the corresponding generating function.

3.1. A classical pattern τ = 12 … k.

Theorem 3.1. Let

A_{k}(x) = \frac{x^{2}}{1 − x^{2}F_{k−2}(x)}A_{k−1}(x) + \frac{x^{4}F_{k−1}(x)}{(1 − x^{2}F_{k−2}(x))^{2}} A_{k−2}(x)

for all k ≥ 2, where A_{1}(x) = 0 and A_{2}(x) = x^{4}. Then for all k ≥ 2

𝔇_{12...k;1}^{(1)}(x) = A_{k}(x) + xA_{k−1}(x).

Proof. By Proposition 2.1, we have two possibilities for block decomposition of an arbitrary π in 𝔇_{n}^{(1)}(132). Let us write an equation for 𝔇_{12...k;1}^{(1)}(x). The contribution of the first decomposition above is

∑_{n≥0} 𝔇_{12...k;1}^{(1)}(2n + 1)x^{2n+1} = x ∑_{n≥0} 𝔇_{12...(k−1);1}^{(1)}(2n)x^{2n},

equivalently

𝔇_{12...k;1}^{(1)}(x) − 𝔇_{12...k;1}^{(1)}(−x) = x(𝔇_{12...(k−1);1}^{(1)}(x) + 𝔇_{12...(k−1);1}^{(1)}(−x)). (3.1)

RESTRICTED 132-DUMONT PERMUTATIONS 9

The contribution of the second decomposition above is

∑_{n≥1} 𝔇_{12...k;1}^{(1)}(2n)x^{2n} = ∑_{n≥1} 𝔇_{12...k;1}^{(1)}(2n − 1)x^{2n}+

+ ∑_{n≥1} ∑_{j=0}^{n} 𝔇_{12...(k−1);1}^{(1)}(2j + 1)𝔇_{12...k;0}^{(1)}(2n + 2 − 2j)x^{2n}+

+ ∑_{n≥1} ∑_{j=0}^{n} 𝔇_{12...(k−1);0}^{(1)}(2j + 1)𝔇_{12...k;1}^{(1)}(2n + 2 − 2j)x^{2n},

equivalently

\begin{matrix}𝔇_{12...k;1}^{(1)}(x) + 𝔇_{12...k;1}^{(1)}(−x) = x(𝔇_{12...k;1}^{(1)}(x) − 𝔇_{12...k;1}^{(1)}(−x))+ \\ +\frac{x}{2}(𝔇_{12...(k−1);1}^{(1)}(x) − 𝔇_{12...(k−1);1}^{(1)}(−x))(𝔇_{12...k;0}^{(1)}(x) + 𝔇_{12...k;0}^{(1)}(−x) − 2)+ \\ +\frac{x}{2}(𝔇_{12...(k−1);0}^{(1)}(x) − 𝔇_{12...(k−1);0}^{(1)}(−x))(𝔇_{12...k;1}^{(1)}(x) + 𝔇_{12...k;1}^{(1)}(−x)). \end{matrix} (3.2)

Using Theorem 2.4, Equation 3.1, Equation 3.2, and Definition 1.1, we get the desired result. Example 3.2. Theorem 3.1 for k = 3 we get

𝔇_{123;1}^{(1)}(x) = \frac{x^{5}(1 + x − x^{2})}{1 − x^{2}},

and for k = 4 we get

𝔇_{1234;1}^{(1)}(x) = \frac{x^{7}(1 + x − 3x^{2} + 2x^{3} + 3x^{4} + 3x^{5} − x^{6} + x^{7})}{(1 − x^{2})(1 − x^{2} − x^{4})^{2}}.

As an extension of Theorem 3.1, let us consider the case r ≥ 1. Theorem 2.6, for given k and r, yields an explicit formula for 𝔇_{12...k;r}^{(1)}(x). For example, for k = 3 and r = 0, 1, 2, 3, 4, we have the following. Theorem 3.3. We have

(i) 𝔇_{123;0}^{(1)}(x) = \frac{1 + x + x^{4} − x^{5}}{1 − x^{2}} ;

(ii) 𝔇_{123;1}^{(1)}(x) = \frac{x^{5}(1 + x − x^{2})}{1 − x^{2}};

(iii) 𝔇_{123;2}^{(1)}(x) = \frac{x^{5}(1 + x^{2})(1 + 2x − 2x^{2} − x^{3} + x^{4})}{(1 − x^{2})^{2}};

(iv) 𝔇_{123;3}^{(1)}(x) = \frac{x^{7}(1 + x − x^{2} + x^{3} − x^{4} − x^{5} + x^{6})}{(1 − x^{2})^{2}};

(v) 𝔇_{123;4}^{(1)}(x) = \frac{x^{9}(1 + x^{2})(−1 − 3x + 3x^{2} + 3x^{3} − 3x^{4} − x^{5} + x^{6})}{(1 − x^{2})^{2}}.

3.2. A classical pattern τ = 2134 … k. Similarly to Theorem 3.1, we have Theorem 3.4. Let

A_{k}(x) = \frac{x^{2}}{1 − x^{2}G_{k−2}(x)}A_{k−1}(x) + \frac{x^{4}G_{k−1}(x)}{(1 − x^{2}G_{k−2}(x))^{2}} A_{k−2}(x)

for all k ≥ 4, where A_{1}(x) = A_{2}(x) = x^{2} and A_{3}(x) = \frac{x^{4}}{1−x^{2}} . Then, for all k ≥ 2, 𝔇_{213...k;1}^{(1)}(x) = A_{k}(x) + xA_{k−1}(x).

10 RESTRICTED 132-DUMONT PERMUTATIONS

3.3. A generalized patterns τ = 12-3- ⋯ -k and τ = 21-3- ⋯ -k. Similarly to Theorem 3.1, we get Theorem 3.5. Let

A_{k}(x) = \frac{x^{2}}{1 − x^{2}F_{k−2}(x)}A_{k−1}(x) + \frac{x^{4}F_{k−1}(x)}{(1 − x^{2}F_{k−2}(x))^{2}} A_{k−2}(x)

for all k ≥ 4, where A_{1}(x) = x^{2} and A_{2}(x) = 2x^{4}. Then, for all k ≥ 2,

𝔇_{12-3-···-k;1}^{(1)}(x) = A_{k}(x) + xA_{k−1}(x).

As an extension of Theorem 3.5, let us consider the case r ≥ 1. Theorem 2.11, for given k and r, yields an explicit formula for 𝔇_{12-3-···-k;r}^{(1)}(x). For example, for k = 3 and r = 0, 1, 2, 3, 4, we have the following. Theorem 3.6. We have

(i) 𝔇_{12-3;0}^{(1)}(x) = \frac{1 + x + x^{4} − x^{5}}{1 − x^{2}} ;

(ii) 𝔇_{12-3;1}^{(1)}(x) = \frac{x^{5}(2 + 3x − 4x^{2} − x^{3} + 2x^{4})}{(1 − x^{2})^{2}};

(iii)𝔇_{12-3;2}^{(1)}(x) = \frac{x^{7}(2 + 2x − 6x^{2} − x^{3} + 6x^{4} + x^{5} − 2x^{6})}{(1 − x^{2})^{3}};

(iv) 𝔇_{12-3;3}^{(1)}(x) = \frac{x^{7}(3 + 5x − 10x^{2} − 9x^{3} + 10x^{4} + 3x^{5} + 4x^{7} − 5x^{8} − x^{9} + 2x^{1}0)}{(1 − x^{2})^{4}};

(v) 𝔇_{12-3;4}^{(1)}(x) = \frac{x^{9}(5 + 5x − 23x^{2} − 7x^{3} + 40x^{4} − x^{5} − 30x^{6} + 5x^{7} + 5x^{8} − x^{9} + 5x^{10} + x^{11} − 2x^{12})}{(1 − x^{2})^{5}}.

Similarly to Theorem 3.1, we have Theorem 3.7. Let

A_{k}(x) = \frac{x^{2}}{1 − x^{2}G_{k−2}(x)}A_{k−1}(x) + \frac{x^{4}G_{k−1}(x)}{(1 − x^{2}G_{k−2}(x))^{2}} A_{k−2}(x)

for all k ≥ 4, where A_{1}(x) = A_{2}(x) = x^{2}, A_{3}(x) = \frac{x^{4}}{1−x^{2}} , and A_{4}(x) = \frac{x^{6}(2−x^{2})}{(1−x^{2})^{3}}. Then, for all k ≥ 2,

𝔇_{21-3-···-k;1}^{(1)}(x) = A_{k}(x) + xA_{k−1}(x).

As an extension of Theorem 3.7, let us consider the case r ≥ 1. Theorem 2.14, for given k and r, yields an explicit formula for 𝔇_{21-3-···-k;r}^{(1)}(x). For example, for k = 3 and r = 0, 1, 2, 3, 4, we have the following. Theorem 3.8. We have

(i) 𝔇_{21-3;0}^{(1)}(x) = \frac{1 + x + x^{4} − x^{5}}{1 − x^{2}} ;

(ii) 𝔇_{21-3;1}^{(1)}(x) = \frac{x^{3}(1 + x − x^{2})}{1 − x^{2}};

(iii) 𝔇_{21-3;2}^{(1)}(x) = \frac{x^{5}(1 + 2x − 2x^{2} − x^{3} + x^{4})}{(1 − x^{2})^{2}};

(iv) 𝔇_{21-3;3}^{(1)}(x) = \frac{x^{5}(1 + x − x^{2} + x^{3} − x^{4} − x^{5} + x^{6})}{(1 − x^{2})^{2}};

(v) 𝔇_{21-3;4}^{(1)}(x) = \frac{x^{7}(1 + 2x − 2x^{2} − 2x^{5} + 2x^{6} + x^{7} − x^{8})}{(1 − x^{2})^{3}}.

4. Further results

Here we present three different directions to generalize the results of the previous sections. The first of these directions is to consider one occurrence of the classical pattern 132. For example, the following result is true.

Theorem 4.1. There does not exist a Dumont permutation of the first kind containing 132 (classical pattern) exactly once.

Proof. Let π = (π′, n, π′′) be a Dumont permutation of the first kind of length n, which contain the pattern 132 exactly once. It is easy to see that there does not exist a Dumont permutation of the first kind where n = 0, 1, 2, 3. Suppose n ≥ 4, and let us assume by induction on n that there does not exist a Dumont permutation of the first kind of length m ≤ n − 1 containing 132 exactly once. To prove this property for n, let us consider the following two cases together with using Proposition 2.1: n is either an even number, or n is an odd number.

1. Let n be an odd number. Since π is a Dumont permutation of the first kind, we get π′′ = ∅, so π contains 132 exactly once if and only if π′ contains 132 exactly once.

2. Let n be an even number. Since π is a Dumont permutation of the first kind we have π′′ ≠ ∅. Now, let us consider two cases: either n does not appear in the occurrence of 132, or n does it.

(a) Let the occurrence of 132 does not contain the element n. So, every element of π′ greater than every element of π′′. Therefore, either π′ is a Dumont permutation of the first kind of length m ≤ n − 2 contains 132 exactly once, or π′′ is a Dumont permutation of the first kind of length m ≤ n − 1 contains 132 exactly once.

(b) Let the occurrence of 132 contains the element n. So, π = (π′, a, n, π′′, a+1, π′′′) (see [MV4]) such that π_{p} = n and π_{q} = a + 1, where every element of π′ is greater than every element of π′′ and every element of π′′ is greater than every element of π′′′. Since n is even number and maximal in π we have that a is an odd number, so a + 1 is an even number. Therefore, by using Proposition 2.1 we get that p, q are even numbers, (π′, a) is of odd length, and π′′ is of even length. On the other hand, q = p + 1 + |π′′|, so q is an odd number, a contradiction.

Hence, by induction on n we get the desired result.

The second direction is to consider more than one additional restriction. For example, the following result is true.

Theorem 4.2. Let k ≥ 2. The generating function for the number of Dumont permutations of the first kind in 𝔖_{n}(1-3-2, 1-2-3 ⋯ -k, 2-1-3 ⋯ -k) is given by

G_{k−1}(x) + xG_{k−2}(x).

A comparison of Theorem 4.2 with Theorem 2.8 suggests that there should exist a bijection between the sets 𝔖_{n}(1-3-2, 2-1-3- ⋯ -k) and 𝔖_{n}(1-3-2, 1-2-3 ⋯ -k, 2-1-3- ⋯ -k). However, we failed to produce such a bijection, and finding it remains an open question.

The third direction is to consider another 3-letter pattern instead of 1-3-2.

Theorem 4.3. The number of Dumont permutation of the second kind in 𝔖_{n}(3-2-1) is the same as the number of Dumont permutation of the first kind in 𝔖_{n}(2-3-1) (or in 𝔖_{n}(3-1-2)) which is equal to C_{[n/2]}.

Acknowledgments: The author are grateful to S. Kitaev for his careful reading of the manuscript.

References

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

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

[BCS] P. Brändén, A. Claesson, and E. Steingrímsson, Continued fractions and increasing subsequences in permutations, Discr. Math., to appear.

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

[CM] A. Claesson and T. Mansour, Permutations avoiding a pair of generalized patterns of length three with exactly one dash, preprint CO/0107044.

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

[D] D. Dumont, Interpretations combinatoires des nombres de Genocchi, Duke Math. J. 41 (1974), 305–318.

[Ki] S. Kitaev, Multi-avoidance of generalised patterns, to appear in Discrete Mathematics.

[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. in Applied Math. 27 (2001), 510–530.

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

[M2] T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combinatorics 6 (2002), 1–12.

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

[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 Chebychev polynomials (2000), Annals of Combinatorics, 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.

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

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

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

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

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