ENUMERATING PERMUTATIONS AVOIDING A PAIR OF BABSON-STEINGRÍMSSON PATTERNS

ANDERS CLAESSON AND TOUFIK MANSOUR

Abstract. Babson and Steingrímsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. Subsequently, Claesson presented a complete solution for the number of permutations avoiding any single pattern of type (1, 2) or (2, 1). For eight of these twelve patterns the answer is given by the Bell numbers. For the remaining four the answer is given by the Catalan numbers.

In the present paper we give a complete solution for the number of permutations avoiding a pair of patterns of type (1, 2) or (2, 1). We also conjecture the number of permutations avoiding the patterns in any set of three or more such patterns.

1. Introduction

Classically, a pattern is a permutation σ ∈ S_{k}, and a permutation π ∈ S_{n} avoids σ if there is no subword of π that is order equivalent to σ. For example, π ∈ S_{n} avoids 132 if there is no 1 ≤ i < j < k ≤ n such that π(i) < π(k) < π(j). We denote by S_{n}(σ) the set permutations in S_{n} that avoids σ.

The first case to be examined was the case of permutations avoiding one pattern of length 3. Knuth [6] found that, for any τ ∈ S_{3}, |S_{n}(τ)| = C_{n}, where C_{n} = \frac{1}{n+1} \binom{2n}{n} is the nth Catalan number. Later Simion and Schmidt [7] found the cardinality of S_{n}(P) for all P ⊆ S_{3}.

In [1] Babson and Steingrímsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. The motivation for Babson and Steingrímsson in introducing these patterns was the study of Mahonian statistics. Two examples of such patterns are 1 32 and 13 2 (1 32 and 13 2 are of type (1, 2) and (2, 1) respectively). A permutation π = a_{1}a_{2} ⋯ a_{n} avoids 1 32 if there are no subwords a_{i}a_{j}a_{j+1} of π such that a_{i} < a_{j+1} < a_{j}. Similarly π avoids 13 2 if there are no subwords a_{i}a_{i+1}a_{j} of π such that a_{i} < a_{j} < a_{i+1}.

Claesson [2] presented a complete solution for the number of permutations avoiding any single pattern of type (1, 2) or (2, 1) as follows. Proposition 1 (Claesson [2]). Let n ∈ ℕ. We have

|S_{n}(p)| = \begin{cases}B_{n} & if p ∈ \{1 23, 3 21, 12 3, 32 1, 1 32, 3 12, 21 3, 23 1\}, \\ C_{n} & if p ∈ \{2 13, 2 31, 13 2, 31 2\}, \end{cases}

where B_{n} and C_{n} are the nth Bell and Catalan numbers, respectively.

In addition, Claesson gave some results for the number of permutations avoiding a pair of patterns. Proposition 2 (Claesson [2]). Let n ∈ ℕ. We have

S_{n}(1 23, 12 3) = B_{n}^{∗}, S_{n}(1 23, 1 32) = I_{n}, and S_{n}(1 23, 13 2) = M_{n}, where B_{n}^{∗} is the nth Bessel number (# non-overlapping partitions of [n] (see [4])), I_{n} is the number of involutions in S_{n}, and M_{n} is the nth Motzkin number.

Date: July 23, 2002.

Key words and phrases. permutation, pattern avoidance.

This paper is organized as follows. In Section 2 we define the notion of a pattern and some other useful concepts. For a proof of Proposition 1 we could refer the reader to [2]. We will however prove Proposition 1 in Section 3 in the context of binary trees. The idea being that this will be a useful aid to understanding of the proofs of Section 4. In Section 4 we give a solution for the number of permutations avoiding any given pair of patterns of type (1, 2) or (2, 1). These results are summarized in the following table.

\begin{matrix}# pairs & |S_{n}(p, q)| \\ 2 & 0, n > 5 \\ 2 & 2(n − 1) \\ 4 & \binom{n}{2} + 1 \\ 34 & 2^{n−1} \\ 8 & M_{n} \\ 2 & a_{n} \\ 4 & b_{n} \\ 4 & I_{n} \\ 4 & C_{n} \\ 2 & B_{n}^{∗} \end{matrix}  \begin{aligned}Here \\ & ∑_{n≥0} a_{n}x^{n} & = \frac{1}{1 − x − x^{2} ∑_{n≥0} B_{n}^{∗}x^{n}} \\ and \\ & b_{n+2} & = b_{n+1} + ∑_{k=0}^{n} \binom{n}{k}b_{k}. \end{aligned}

Finally, in Section 5 we conjecture the sequences |S_{n}(P)| for sets P of three or more patterns of type (1, 2) or (2, 1).

2. Preliminaries

By an alphabet X we mean a non-empty set. An element of X is called a letter. A word over X is a finite sequence of letters from X. We consider also the empty word, that is, the word with no letters; it is denoted by ϵ. Let w = x_{1}x_{2} ⋯ x_{n} be a word over X. We call |w| := n the length of w. A subword of w is a word v = x_{i_{1}}x_{i_{2}} ⋯ x_{i_{k}}, where 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n.

Let [n] := {1, 2, …, n} (so [0] = ∅). A permutation of [n] is bijection from [n] to [n]. Let S_{n} be the set of permutations of [n], and S = ∪_{n≥0}S_{n}. We shall usually think of a permutation π as the word π(1)π(2) ⋯ π(n) over the alphabet [n].

Define the reverse of π by π^{r}(i) = π(n + 1 − i), and define the complement of π by π^{c}(i) = n + 1 − π(i), where i ∈ [n].

For each word w = x_{1}x_{2} ⋯ x_{n} over the alphabet {1, 2, 3, 4, …} without repeated letters, we define the projection of w onto S_{n}, which we denote proj(w), by

proj(w) = a_{1}a_{2} ⋯ a_{n} , where a_{i} = |{j ∈ [n] : x_{j} ≤ x_{i}}|.

Equivalently, proj(w) is the permutation in S_{n} which is order equivalent to w. For example, proj(2659) = 1324.

We may regard a pattern as a function from S_{n} to the set ℕ of natural numbers. The patterns of main interest to us are defined as follows. Let xyz ∈ S_{3} and π = a_{1}a_{2} ⋯ a_{n} ∈ S_{n}, then

(x yz) π = |{a_{i}a_{j}a_{j+1} : proj(a_{i}a_{j}a_{j+1}) = xyz, 1 ≤ i < j < n}|

and similarly (xy z) π = (z yx) π^{r}. For instance

(1 23) 491273865 = |{127, 138, 238}| = 3.

A pattern p = p_{1} p_{2} ⋯ p_{k} containing exactly k − 1 dashes is said to be of type (|p_{1}|, |p_{2}|, …, |p_{k}|). For example, the pattern 142 5 367 is of type (3, 1, 3), and any classical pattern of length k is of type (\underbrace{1, 1, …, 1}_{k}).

We say that a permutation π avoids a pattern p if p π = 0. The set of all permutations in S_{n} that avoids p is denoted S_{n}(p) and, more generally, S_{n}(P) = ⋂_{p∈P} S_{n}(p) and S(P) = ⋃_{n≥0} S_{n}(P).

We extend the definition of reverse and complement to patterns the following way. Let us call π the underlying permutation of the pattern p if π is obtained from p by deleting all the dashes in p. If p is a pattern with underlying permutation π, then p^{c} is the pattern with underlying permutation π^{c} and with dashes at precisely the same positions as there are dashes in p. We define p^{r} as the pattern we get from regarding p as a word and reading it backwards. For example, (1 23)^{c} = 3 21 and (1 23)^{r} = 32 1. Observe that

σ ∈ S_{n}(p) ⟺ σ^{r} ∈ S_{n}(p^{r})
σ ∈ S_{n}(p) ⟺ σ^{c} ∈ S_{n}(p^{c}).

These observations of course generalize to S_{n}(P) for any set of patterns P.

The operations reverse and complement generates the dihedral group D_{2} (the symmetry group of a rectangle). The orbits of D_{2} in the set of patterns of type (1, 2) or (2, 1) will be called symmetry classes. For instance, the symmetry class of 1 23 is

{1 23, 3 21, 12 3, 32 1}.

We also talk about symmetry classes of sets of patterns (defined in the obvious way). For example, the symmetry class of {1 23, 3 21} is {{1 23, 3 21}, {32 1, 12 3}}.

A set of patterns P such that if p, p′ ∈ P then, for each n, |S_{n}(p)| = |S_{n}(p′)| is called a Wilf-class. For instance, by Proposition 1, the Wilf-class of 1 23 is

{1 23, 3 21, 12 3, 32 1, 1 32, 3 12, 21 3, 23 1}.

We also talk about Wilf-classes of sets of patterns (defined in the obvious way). It is clear that symmetry classes are Wilf-classes, but as we have seen the converse does not hold in general.

In what follows we will frequently use the following well known bijection between increasing binary trees and permutations (e.g. see [8, p. 24]). Let π be any word on the alphabet {1, 2, 3, 4, …} with no repeated letters. If π ≠ ϵ then we can factor π as π = σ ˆ0 τ, where ˆ0 is the minimal element of π. Define T (ϵ) = • (a leaf) and

T (π) = [figure: ˆ0; T (σ); T (τ)]

In addition, we define U(t) as the unlabelled counterpart of the labelled tree t. For instance

T (316452) = [figure: 1; 3; 2; 4; 6; 5] U ∘ T (316452) = [figure: ◯; ◯; ◯; ◯; ◯; ◯]

Note that we, for ease of presentation, do not display the leafs (•).

3. Single patterns

There are 3 symmetry classes and 2 Wilf-classes of single patterns. The details are as follows.

Proposition 3 (Claesson [2]). Let n ∈ ℕ. We have

|S(p)| = \begin{cases}B_{n} & if p ∈ \{1 23, 3 21, 12 3, 32 1\}, \\ B_{n} & if p ∈ \{1 32, 3 12, 21 3, 23 1\}, \\ C_{n} & if p ∈ \{2 13, 2 31, 13 2, 31 2\}, \end{cases}

where B_{n} and C_{n} are the nth Bell and Catalan numbers, respectively.

Proof of the first case. Note that

σ1τ ∈ S(1 23) ⟺ \begin{cases}proj(σ) ∈ S(1 23) \\ proj(τ) ∈ S(12) \\ σ1τ ∈ S \end{cases}

where of course S(12) = {ϵ, 1, 21, 321, 4321, …}. This enable us to give a bijection Φ between S_{n}(1 23) and the set of partitions of [n], by induction. Let the elements of 1τ form the first block of Φ(σ1τ) and let the rest of the blocks be as in Φ(σ). □

The most transparent way to see the above correspondence is perhaps to view the permutation as an increasing binary tree. Example 4. The tree

T (649752183) = [figure: 1; 2; 3; 4; 8; 6; 5; 7; 9]

corresponds to the partition {{1, 3, 8}, {2}, {4, 5, 7, 9}, {6}}.

Proof of the second case. This case is analogous to the previous one. We have

σ1τ ∈ S(1 32) ⟺ \begin{cases}proj(σ) ∈ S(1 32) \\ proj(τ) ∈ S(21) \\ σ1τ ∈ S \end{cases}

We give a bijection Φ between S_{n}(1 23) and the set of partitions of [n], by induction. Let the elements of 1τ form the first block of Φ(σ1τ) and let the rest of the blocks be as in Φ(σ). □

Example 5. The tree

T (645792138) = [figure: 1; 2; 3; 4; 8; 6; 5; 7; 9]

corresponds to the partition {{1, 3, 8}, {2}, {4, 5, 7, 9}, {6}}.

Now that we have seen the structure of S(1 23) and S(1 32), it is trivial to give a bijection between the two sets. Indeed, if Θ : S(1 23) → S(1 32) is given by Θ(ϵ) = ϵ and Θ(σ1τ) = Θ(σ) 1 τ^{r} then Θ is such a bijection. Actually Θ is its own inverse.

Proof of the third case. It is plain that a permutation avoids 2 13 if and only if it avoids 2 1 3 (see [2]). Note that

σ1τ ∈ S(2 1 3) ⟺ \begin{cases}proj(σ), proj(τ) ∈ S(2 1 3) \\ τ > σ \\ σ1τ ∈ S \end{cases}

where τ > σ means that any letter of τ is greater than any letter of σ. Hence we get a unique labelling of the binary tree corresponding to σ1τ, that is, if π_{1}, π_{2} ∈ S(2 1 3) and U ∘ T (π_{1}) = U ∘ T (π_{2}) then π_{1} = π_{2}. It is well known that there are exactly C_{n} (unlabelled) binary trees with n (internal) nodes. The validity of the last statement is for example seen from the following simple bijection between Dyck words and binary trees. Fixing notation, we let the set of Dyck words be the smallest set of words over {u, d} that contains the empty word and is closed under (α, β) ↦ uαdβ. Now the promised bijection is given by Ψ(•) = ϵ and

Ψ([figure: ◯; L; R] ) = uΨ(L)dΨ(R).
□

4. Pairs of patterns

There are \binom{12}{2} = 66 pairs of patterns altogether. It turns out that there are 21 symmetry classes and 10 Wilf-classes. The details are as follows.

4.1. The Wilf-class corresponding to {0}_{n}. Proposition 6. Let n ∈ ℕ with n > 5. For any pair {p, q} in the set

{ {1 23, 32 1}, {3 21, 12 3} }

we have |S_{n}(p, q)| = 0.

Proof. We have

σ1τ ∈ S(1 23, 32 1) ⟺ \begin{cases}proj(σ) ∈ S(21, 1 23) \\ proj(τ) ∈ S(12, 32 1) \\ σ1τ ∈ S \end{cases}

The result now follows from S(21, 1 23) = {ϵ, 1, 12} and S(12, 32 1) = {ϵ, 1, 21}.

□

4.2. The Wilf-class corresponding to {2(n − 1)}_{n}. Proposition 7. Let n ∈ ℕ with n > 1. For any pair {p, q} in the set

{ {1 23, 3 21}, {32 1, 12 3} }

we have |S_{n}(p, q)| = 2(n − 1).

Proof. Since 3 21 is the complement of 1 23, the cardinality of S_{n}(1 23, 3 21) is twice the number of permutations in S_{n}(1 23, 3 21) in which 1 precedes n. In addition, 1 and n must be adjacent letters in a permutation avoiding 1 23 and 3 21. Let σ1nτ be such a permutation. Note that τ must be both increasing and decreasing, that is, τ ∈ {ϵ, 2, 3, 4, …, n − 1}, so there are n − 1 choices for τ. Furthermore, there is exactly one permutation in S_{n}(1 23, 3 21) of the form σ1n, namely (⌈\frac{n+1}{2}⌉, …, n − 2, 3, n − 1, 2, n, 1), and similarly there is exactly one of the form σ1nk for each k ∈ {2, 3, …, n − 1}. This completes our argument. □

4.3. The Wilf-class corresponding to \{\binom{n}{2} + 1\}_{n}. Proposition 8. Let n ∈ ℕ. For any pair {p, q} in the set

{ {1 23, 2 31}, {3 21, 2 13}, {12 3, 31 2}, {32 1, 13 2} }

we have |S_{n}(p, q)| = \binom{n}{2} + 1.

Proof. Note that

σ1τ ∈ S(1 23, 2 31) ⟺ \begin{cases}proj(σ), proj(τ) ∈ S(12) \\ σ1τ ∈ S(2 31) \end{cases}

It is now rather easy to see that π ∈ S_{n}(1 23, 2 31) if and only if π = n ⋯ 21 or π is constructed the following way. Choose i and j such that 1 ≤ j < i ≤ n. Let π(i − 1) = 1, π(i) = n + 1 − j and arrange the rest of the elements so that π(1) > π(2) > ⋯ > π(i − 1) and π(i) > π(i + 1) > ⋯ > π(n) (this arrangement is unique). Since there are \binom{n}{2} ways of choosing i and j we get the desired result. □

4.4. The Wilf-class corresponding to {2^{n−1}}_{n}. Proposition 9. Let n ∈ ℕ with n > 0. For any pair {p, q} in the set

{ {1 23, 2 13}, {3 21, 2 31}, {12 3, 13 2}, {32 1, 31 2} }

we have |S_{n}(p, q)| = 2^{n−1}.

Proof. We have

σ1τ ∈ S(1 23, 2 13) ⟺ \begin{cases}proj(σ) ∈ S(1 23, 2 13) \\ proj(τ) ∈ S(12) \\ σ > τ \\ σ1τ ∈ S, \end{cases}

where σ > τ means that any letter of τ is greater than any letter of σ. This enable us to give a bijection between S_{n}(1 23, 2 13) and the set of compositions (ordered formal sums) of n. Indeed, such a bijection Ψ is given by Ψ(ϵ) = ϵ and Ψ(σ1τ) = Ψ(σ) + |1τ|. □

Example 10. The tree

U ∘ T (958764132) = [figure: ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘]

corresponds to the composition 1 + 3 + 1 + 4 of 9. Proposition 11. Let n ∈ ℕ with n > 0. For any pair {p, q} in the set

{ {1 23, 23 1}, {3 21, 21 3}, {12 3, 3 12}, {32 1, 1 32} }

we have |S_{n}(p, q)| = 2^{n−1}.

Proof. We have

σ1τ ∈ S(1 23, 23 1) ⟺ \begin{cases}proj(σ), proj(τ) ∈ S(12) \\ σ1τ ∈ S \end{cases}

Hence a permutation in S(1 23, 23 1) is given by the following procedure. Choose a subset S ⊆ {2, 3, 4, …, n}, let σ be the word obtained by writing the elements of S in decreasing order, and let τ be the word obtained by writing the elements of {2, 3, 4, …, n} \ S in decreasing order. □

ENUMERATING PERMUTATIONS AVOIDING A PAIR OF BABSON-STEINGRÍMSSON PATTERNS 7

Example 12. The tree

T (421653) = [figure: 1; 2; 3; 4; 5; 6]

corresponds to the subset {2, 4} of {2, 3, 4, 5, 6}. Proposition 13. Let n ∈ ℕ with n > 0. For any pair {p, q} in the set

{ {1 23, 31 2}, {3 21, 13 2}, {12 3, 2 31}, {32 1, 2 13} }

we have |S_{n}(p, q)| = 2^{n−1}. Proof. This case is essentially identical to the case dealt with in Proposition 9. □ Proposition 14. Let n ∈ ℕ with n > 0. For any pair {p, q} in the set

{ {1 32, 2 13}, {3 12, 2 31}, {13 2, 21 3}, {23 1, 31 2} }

we have |S_{n}(p, q)| = 2^{n−1}. Proof. The bijection Θ between S(1 23) and S(1 32) (see page 3) provides a oneto-one correspondence between S_{n}(1 32, 2 13) and S_{n}(1 23, 2 13). Consequently the result follows from Proposition 9. □ Proposition 15. Let n ∈ ℕ with n > 0. For any pair {p, q} in the set

{ {1 32, 2 31}, {3 12, 2 13}, {31 2, 21 3}, {23 1, 13 2} }

we have |S_{n}(p, q)| = 2^{n−1}. Proof. We have

σ1τ ∈ S(3 12, 2 13) ⟺ \begin{cases}proj(σ), proj(τ) ∈ S(3 12, 2 13) \\ σ = ϵ or τ = ϵ \\ σ1τ ∈ S \end{cases}

Thus a bijection between S_{n}(3 12, 2 13) and {0, 1}^{n−1} is given by Ψ(ϵ) = ϵ and

Ψ(σ1τ) = xΨ(στ) where x = \begin{cases}1 & if σ ≠ ϵ, \\ 0 & if τ ≠ ϵ, \\ ϵ & otherwise. \end{cases}
□

Example 16. The tree

U ∘ T (136542) = [figure: ∘; ∘; ∘; ∘; ∘; ∘]

corresponds to 01011 ∈ {0, 1}^{5}. Proposition 17. Let n ∈ ℕ with n > 0. For any pair {p, q} in the set

{ {1 32, 3 12}, {23 1, 21 3} }

we have |S_{n}(p, q)| = 2^{n−1}.

8 ANDERS CLAESSON AND TOUFIK MANSOUR

Proof. Since 3 12 is the complement of 1 32, the cardinality of S_{n}(1 32, 3 12) is twice the number of permutations in S_{n}(1 32, 3 12) in which 1 precedes n. In addition, n must be the last letter in such a permutation or else a hit of 1 32 would be formed. We have

σ1τn ∈ S(1 32, 3 12) ⟺ \begin{cases}proj(σ1τ) ∈ S(1 32, 3 12) \\ proj(τ) ∈ S(21) \\ σ1τ ∈ S \end{cases}
⟺ \begin{cases}proj(σ) ∈ S(1 32, 3 12) \\ proj(τ) ∈ S(21) \\ σ < τ \\ σ1τ ∈ S \end{cases}

The rest of the proof follows the same lines as the proof of Proposition 9. □ Proposition 18. Let n ∈ ℕ with n > 0. For any pair {p, q} in the set

{ {1 32, 23 1}, {3 12, 21 3} }

we have |S_{n}(p, q)| = 2^{n−1}. Proof. We can copy almost verbatim the proof of Proposition 15, indeed, it is easy to see that S_{n}(1 32, 23 1) = S_{n}(1 32, 2 31). □ Proposition 19. Let n ∈ ℕ with n > 0. For any pair {p, q} in the set

{ {1 32, 31 2}, {3 12, 13 2}, {21 3, 2 31}, {23 1, 2 13} }

we have |S_{n}(p, q)| = 2^{n−1}. Proof. We can copy almost verbatim the proof of Proposition 17, indeed, it is easy to see that S_{n}(1 32, 31 2) = S_{n}(1 32, 3 12). □ Proposition 20. Let n ∈ ℕ with n > 0. For any pair {p, q} in the set

{ {2 13, 2 31}, {31 2, 13 2} }

we have |S_{n}(p, q)| = 2^{n−1}. Proof. |S_{n}(2 13, 2 31)| = |S_{n}(2 1 3, 2 3 1)| = 2^{n−1} by [7, Lemma 5(d)]. □ Proposition 21. Let n ∈ ℕ with n > 0. For any pair {p, q} in the set

{ {2 13, 13 2}, {2 31, 31 2} }

we have |S_{n}(p, q)| = 2^{n−1}. Proof. |S_{n}(2 13, 13 2)| = |S_{n}(1 3 2, 2 1 3)| = 2^{n−1} by [7, Lemma 5(b)]. □ Proposition 22. Let n ∈ ℕ with n > 0. For any pair {p, q} in the set

{ {2 13, 31 2}, {2 31, 13 2} }

we have |S_{n}(p, q)| = 2^{n−1}. Proof. |S_{n}(2 13, 31 2)| = |S_{n}(2 1 3, 3 1 2)| = 2^{n−1} by [7, Lemma 5(c)]. □

4.5. The Wilf-class corresponding to {M_{n}}_{n}.

Proposition 23. Let n ∈ ℕ. For any pair {p, q} in the set

{ {1 23, 13 2}, {3 21, 31 2}, {12 3, 2 13}, {32 1, 2 31} }

we have |S_{n}(p, q)| = M_{n}, where M_{n} is the nth Motzkin number.

Proof. See Proposition 2. □

Proposition 24. Let n ∈ ℕ. For any pair {p, q} in the set

{ {1 23, 21 3}, {3 21, 23 1}, {12 3, 1 32}, {32 1, 3 12} }

we have |S_{n}(p, q)| = M_{n}, where M_{n} is the nth Motzkin number.

Proof. We give a bijection Λ : S_{n}(1 23, 21 3) → S_{n}(1 23, 13 2) by means of induction. Let π ∈ S_{n}(1 23, 21 3). Define Λ(π) = π for n ≤ 1. Assume n ≥ 2 and π = a_{1}a_{2} ⋯ a_{n}. It is plain that either a_{1} = n or a_{2} = n, so we can define

Λ(π) = \begin{cases}(a′_{1} + 1, …, a′_{n−1} + 1, a′_{n−2} + 1, 1) & if \begin{cases}a_{1} = n and \\ a′_{1} ⋯ a′_{n−1} = Λ(a_{2}a_{3}a_{4} ⋯ a_{n}), \end{cases} \\ (a′_{1} + 1, …, a′_{n−1} + 1, 1, a′_{n−2} + 1) & if \begin{cases}a_{2} = n and \\ a′_{1} ⋯ a′_{n−1} = Λ(a_{1}a_{3}a_{4} ⋯ a_{n}). \end{cases} \end{cases}

Observing that if σ ∈ S_{n}(1 23, 13 2) then σ(n − 1) = 1 or σ(n) = 1, it easy to find the inverse of Λ. □

4.6. The Wilf-class corresponding to {1, 1, 2, 4, 9, 22, 58, 164, 496, 1601, …}. In [2] Claesson introduced the notion of a monotone partition. A partition is monotone if its non-singleton blocks can be written in increasing order of their least element and increasing order of their greatest element, simultaneously. He then proved that monotone partitions and non-overlapping partitions are in ono-to-one correspondence. Non-overlapping partitions where first studied by Flajolet and Schot in [4]. A partition π is non-overlapping if for no two blocks A and B of π we have min A < min B < max A < max B. Let B_{n}^{∗} be the number of non-overlapping partitions of [n]; this number is called the nth Bessel number. Proposition 2 tells us that there is a bijection between non-overlapping partitions and permutations avoiding 1 23 and 12 3. Below we define a new class of partitions called strongly monotone partitions and then show that there is a bijection between strongly monotone partitions and permutations avoiding 1 32 and 21 3.

Definition 25. Let π be an arbitrary partition whose blocks {A_{1}, …, A_{k}} are ordered so that for all i ∈ [k − 1], min A_{i} > min A_{i+1}. If max A_{i} > max A_{i+1} for all i ∈ [k − 1], then we call π a strongly monotone partition.

In other words a partition is strongly monotone if its blocks can be written in increasing order of their least element and increasing order of their greatest element, simultaneously. Let us denote by a_{n} the number of strongly monotone partitions of [n]. The sequence {a_{n}}_{0}^{∞} starts with

1, 1, 2, 4, 9, 22, 58, 164, 496, 1601, 5502, 20075, 77531, 315947, 1354279.

It is routine to derive the continued fraction expansion

∑_{n≥0} a_{n}x^{n} = \frac{1}{1 − 1 · x − \frac{x^{2}}{1 − 1 · x − \frac{x^{2}}{1 − 2 · x − \frac{x^{2}}{1 − 3 · x − \frac{x^{2}}{1 − 4 · x − \frac{x^{2}}{...}}}}}}

using the standard machinery of Flajolet [3] and Françon and Viennot [5]. One can also note that there is a one-to-one correspondence between strongly monotone partitions and non-overlapping partition, π, such that if {x} and B are blocks of π then either x < min B or max B < x. In addition, we observe that

∑_{n≥0} a_{n}x^{n} = \frac{1}{1 − x − x^{2}B^{∗}(x)},

where B^{∗}(x) = ∑_{n≥0} B_{n}^{∗}x^{n} is the ordinary generating function for the Bessel numbers. Proposition 26. Let n ∈ ℕ. For any pair {p, q} in the set

{ {1 32, 21 3}, {3 12, 23 1} }

we have |S_{n}(p, q)| = a_{n}, where a_{n} is the number of strongly monotone partitions of [n] (see Definition 25).

Proof. Suppose π ∈ S_{n} has k + 1 left-to-right minima 1, 1′, 1′′, …, 1^{(k)} such that

1 < 1′ < 1′′ < ⋯ < 1^{(k)}, and π = 1^{(k)}τ^{(k)} ⋯ 1′τ′1τ.

Then π avoids 1 32 if and only if, for each i, τ^{(i)} ∈ S(21). If π avoids 1 32 and x_{i} = max 1^{(i)}τ^{(i)} then π avoids 21 3 precisely when x_{0} < x_{1} < ⋯ < x_{k}. This follows from observing that the only potential (21 3)-subwords of π are x_{i+1}1^{(k)}x_{j} with j ≤ i.

Mapping π to the partition {1σ, 1′σ′, …, 1^{(k)}τ^{(k)}} we thus get a one-to-one correspondence between permutations in S_{n}(1 32, 21 3) and strongly monotone partitions of [n]. □

4.7. The Wilf-class corresponding to {1, 1, 2, 4, 9, 23, 65, 199, 654, 2296, …}. Proposition 27. Let n ∈ ℕ. For any pair {p, q} in the set

{ {1 23, 3 12}, {3 21, 1 32}, {23 1, 12 3}, {32 1, 21 3} }

we have |S_{n}(p, q)| = b_{n}, where the sequence {b_{n}} satisfies b_{0} = 1 and, for n ≥ −2,

b_{n+2} = b_{n+1} + ∑_{k=0}^{n} \binom{n}{k}b_{k}.

Proof. Suppose π ∈ S_{n} has k + 1 left-to-right minima 1, 1′, 1′′, …, 1^{(k)} such that

1 < 1′ < 1′′ < ⋯ < 1^{(k)}, and π = 1^{(k)}τ^{(k)} ⋯ 1′τ′1τ.

Then π avoids 1 23 if and only if, for each i, τ^{(i)} ∈ S(12). If π avoids 1 23 and x_{i} = max 1^{(i)}τ^{(i)} then π avoids 3 12 precisely when

j > i and x_{i} ≠ 1^{(i)} ⟹ x_{j} < x_{i}.

This follows from observing that the only potential (3 12)-subwords of π are x_{j}1^{(k)}x_{i} with j ≤ i. Thus we have established

σ1τ ∈ S_{n}(1 23, 3 12) ⟺ \begin{cases}proj(σ) ∈ S(1 23, 3 12) \\ τ ≠ ϵ ⇒ τ = τ′n and proj(τ′) ∈ S(12) \\ σ1τ ∈ S_{n} \end{cases}

If we know that σ1τ′n ∈ S_{n}(1 23, 3 12) and proj(τ′) ∈ S_{k}(12) then there are \binom{n−2}{k} candidates for τ′. In this way the recursion follows. □

4.8. The Wilf-class corresponding to I_{n}. Proposition 28. Let n ∈ ℕ. For any pair {p, q} in the set

{ {1 23, 1 32}, {3 21, 3 12}, {21 3, 12 3}, {32 1, 23 1} }

we have |S_{n}(p, q)| = I_{n}, where I_{n} is the number of involutions in S_{n}.

Proof. See Proposition 2. □

4.9. The Wilf-class corresponding to C_{n}. Proposition 29. Let n ∈ ℕ. For any pair {p, q} in the set

{ {1 32, 13 2}, {3 12, 31 2}, {21 3, 2 13}, {23 1, 2 31} }

we have |S_{n}(p, q)| = C_{n}, where C_{n} is the nth Catalan number.

Proof. S_{n}(1 32, 13 2) = S_{n}(1 3 2). □

4.10. The Wilf-class corresponding to B_{n}^{∗}. Proposition 30. Let n ∈ ℕ. For any pair {p, q} in the set

{ {1 23, 12 3}, {3 21, 32 1} }

we have |S_{n}(p, q)| = B_{n}^{∗}, where B_{n}^{∗} is the nth Bessel number.

Proof. See Proposition 2. □

5. More than two patterns

Let P be a set of patterns of type (1, 2) or (2, 1). With the aid of a computer we have calculated the cardinality of S_{n}(P) for sets P of three ore more patterns. From these results we arrived at the plausible conjectures of table 1 (some of which are trivially true). We use the notation m × n to express that there are m symmetric classes each of which contains n sets. Moreover, we denote by F_{n} the nth Fibonacci number (F_{0} = F_{1} = 1, F_{n+1} = F_{n} + F_{n−1}).

Acknowledgements

The first author wishes to express his gratitude towards Einar Steingrímsson, Kimmo Eriksson, and Mireille Bousquet-Mélou; Einar for his guidance and infectious enthusiasm; Kimmo for useful suggestions and a very constructive discussion on the results of this paper; Mireille for her great hospitality during a stay at LaBRI, where some of the work on this paper was done.

We would like to thank N. J. A. Sloane for his excellent web site “The On-Line Encyclopedia of Integer Sequences”

            http://www.research.att.com/~njas/sequences/.

It is simply an indispensable tool for all studies concerned with integer sequences.

For |P | = 3 there are 220 sets, 55 symmetry classes and 9 Wilf-classes.

cardinality # sets
0 7 × 4
3 1 × 4
n 24 × 4
1 + \binom{n}{2} 2 × 4
F_{n} 7 × 4
\binom{n}{[n/2]} 1 × 4
2^{n−2} + 1 1 × 4
2^{n−1} 10 × 4
M_{n} 2 × 4

For |P | = 4 there are 495 sets, 135 symmetry classes, and 9 Wilf-classes.

cardinality  # sets
0 1 × 1 + 6 × 2 + 30 × 4
2 2 × 1 + 5 × 2 + 35 × 4
3  1 × 4
n  37 × 4 + 1 × 2
1 + \binom{n}{2}  1 × 4
F_{n}  9 × 4 + 1 × 2
\binom{n}{[n/2]}  1 × 2
2^{n−2} + 1  1 × 2
2^{n−1}  1 × 4 + 3 × 2

For |P | = 5 there are 792 sets, 198 symmetry classes, and 5 Wilf-classes.

cardinality # sets
0 84 × 4
1 16 × 4
2 74 × 4
n 20 × 4
F_{n} 4 × 4

For |P | = 6 there are 924 sets, 246 symmetry classes, and 4 Wilf-classes.

cardinality  # sets
0 17 × 2 + 124 × 4
1  4 × 2 + 38 × 4
2  7 × 2 + 51 × 4
n  1 × 2 + 3 × 4
F_{n}  1 × 2

For |P | = 7 there are 792 sets, 198 symmetry classes, and 3 Wilf-classes.

cardinality # sets
0 140 × 4
1 40 × 4
2 18 × 4

For |P | = 8 there are 495 sets, 135 symmetry classes, and 3 Wilf-classes.

cardinality  # sets
0 2 × 1 + 14 × 2 + 94 × 4
1  4 × 2 + 18 × 4
2  1 × 1 + 2 × 4

For |P | = 9 there are 220 sets, 55 symmetry classes, and 2 Wilf-classes.

cardinality # sets
0 50 × 4
1 5 × 4

For |P | = 10 there are 66 sets, 21 symmetry classes, and 2 Wilf-classes.

cardinality  # sets
0 8 × 2 + 12 × 4
1  1 × 2

For |P | = 11 there are 12 sets, 3 symmetry classes, and 1 Wilf-class.

cardinality # sets ; 0 3 × 4

For |P | = 12 there is 1 set, 1 symmetry class, and 1 Wilf-class.

cardinality # sets ; 0 1 × 1

Table 1. The cardinality of S_{n}(P) for |P | > 2.

References

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

[2] A. Claesson. Generalized pattern avoidance. To appear in: European Journal of Combinatorics, 2001.

[3] P. Flajolet. Combinatorial aspects of continued fractions. Annals of Discrete Mathematics, 8:217–222, 1980.

[4] P. Flajolet and R. Schott. Non–overlapping partitions, continued fractions, Bessel functions and a divergent series. European Journal of Combinatorics, 11:421–432, 1990.

[5] J. Françon and G. Viennot. Permutations selon leurs pics, creux, doubles montées et double descentes, nombres d’Euler et nombres de Genocchi. Discrete Math., 28(1):21–35, 1979.

[6] D. E. Knuth. The art of computer programming, volume 3. Addison-Wesley, 1973.

[7] R. Simion and F. W. Schmidt. Restricted permutations. European Journal of Combinatorics, 6:383–406, 1985.

[8] R. P. Stanley. Enumerative Combinatorics, volume 1. Cambridge University Press, 1997.

Matematik, Chalmers tekniska högskola och Göteborgs universitet, S-412 96 Göteborg, Sweden

   E-mail address: claesson@math.chalmers.se

LaBRI, Univerité Bordeaux I, 351 cours de la Libération, 33405 Talence Cedex, France

   E-mail address: toufik@labri.fr