Multi-Avoidance of Generalised Patterns

Sergey Kitaev ^{∗}

Abstract Recently, Babson and Steingrímsson introduced generalised permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. We investigate simultaneous avoidance of two or more 3-patterns without internal dashes, that is, where the pattern corresponds to a contiguous subword in a permutation.

1 Introduction and Background

We write permutations as words π = a_{1}a_{2} ⋯ a_{n}, whose letters are distinct and usually consist of the integers 1, 2, …, n.

An occurrence of a pattern p in a permutation π is “classically” defined as a subsequence in π (of the same length as the length of p) whose letters are in the same relative order as those in p. Formally speaking, for r ≤ n, we say that a permutation σ in the symmetric group S_{n} has an occurrence of the pattern p ∈ S_{r} if there exist 1 ≤ i_{1} < i_{2} < ⋯ < i_{r} ≤ n such that p = σ(i_{1})σ(i_{2}) … σ(i_{r}) in reduced form. The reduced form of a permutation σ on a set {j_{1}, j_{2}, …, j_{r}}, where j_{1} < j_{2} < ⋯ < j_{r}, is a permutation σ_{1} obtained by renaming the letters of the permutation σ so that j_{i} is renamed i for all i ∈ {1, …, r}. For example, the reduced form of the permutation 3651 is 2431.

In [1] Babson and Steingrímsson introduced generalised permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. In order to avoid confusion we write a ”classical” pattern, say 231, as 2-3-1, and if we write, say 2-31, then we mean that if this pattern occurs in the permutation, then the letters in the permutation that correspond to 3 and 1 are adjacent. For example, the permutation π = 516423 has only one occurrence of the pattern 2-31, namely the subword 564, whereas the pattern 2-3-1 occurs, in addition, in the subwords 562 and 563.

∗Matematiska Institutionen, Chalmers tekniska högskola and Göteborgs universitet, S-412 96 Göteborg, Sweden; E-mail: kitaev@math.chalmers.se

The motivation for introducing these patterns in [1] was the study of Mahonian statistics. A number of interesting results on generalised patterns were obtained in [5]. Relations to several well studied combinatorial structures, such as set partitions, Dyck paths, Motzkin paths and involutions, were shown there.

In this paper we consider 3-patterns without internal dashes, that is, generalised patterns of the form xyz. Thus, such patterns correspond to contiguous subwords anywhere in a permutation. For example the permutation π = 12345 has 3 occurrences of the pattern 123 but 10 occurrences of the classical pattern 1-2-3. Patterns without internal dashes were considered by Elizalde and Noy in [6]. In that paper, there is a number of results on the distribution of several classes of patterns without internal dashes. In particular, formulas are given for the bivariate exponential generating functions that count permutations by the number of occurrences of any given 3-pattern. Those formulas give rise to the exponential generating functions for the number of permutations that avoid any 3-pattern.

As in the paper by Simion and Schmidt [11], dealing with the classical patterns, one can consider the case when permutations have to avoid two or more generalised patterns simultaneously. A number of such cases were considered in [5]. However, except for the simultaneous avoidance of the patterns 123 and 132, and three more pairs that are essentially equivalent to this, there are no other results for multi-avoidance of the patterns without internal dashes. In this paper we give either an explicit formula or a recursive formula for almost all cases of simultaneous avoidance of more than two patterns. We also mention what is known about double restrictions.

2 Preliminaries

Since we only treat patterns of length 3, and permutations of length 1 or 2 avoid all such patterns, we always assume that our permutations have length n ≥ 3.

Obviously, no permutation avoids all six patterns of length three. Only the increasing permutation 12 … n avoids all 3-patterns but 123, and only the decreasing permutation avoids all but 321.

Consider now permutations that avoid all but one 3-pattern, different from 123 and 321, Obviously, there is exactly one such 3-permutation. However, for n ≥ 4 there is no such permutation. Indeed, if the permutation π = a_{1}a_{2} … a_{n} avoids the patterns 123 and 321, then the letters of π alternate in size. That means that a_{1}a_{2}a_{3} and a_{2}a_{3}a_{4} form different patterns and thus π has an occurrence of a forbidden pattern.

There are, of course, \binom{6}{k} sets consisting of k different 3-patterns, so we have 15 sets of two 3-patterns, 20 with three 3-patterns and 15 with four. So we have 50 different sets having more than one restriction. But we can simplify our work by partitioning the sets into equivalence classes in the way shown below and it will be enough to consider only 18 sets of restrictions.

The reverse R(π) of a permutation π = a_{1}a_{2} … a_{n} is the permutation a_{n}a_{n−1} … a_{1}. The complement C(π) is the permutation b_{1}b_{2} … b_{n} where b_{i} = n + 1 − a_{i}. Also, R ∘ C is the composition of R and C. For example, R(13254) = 45231, C(13254) = 53412 and R ∘ C(13254) = 21435. We call these bijections of S_{n} to itself trivial, and it is easy to see that for any pattern p the number A_{p}(n) of permutations avoiding the pattern p is the same as for the patterns R(p), C(p) and R ∘ C(p). For example, the number of permutations that avoid the pattern 132 is the same as the number of permutations that avoid the pattern 231. This property holds for sets of patterns as well. If we apply one of the trivial bijections to all patterns of a set G, then we get a set G′ for which A_{G′}(n) is equal to A_{G}(n). For example, the number of permutations avoiding {123, 132} equals the number of those avoiding {321, 312} because the second set is obtained from the first one by complementing each pattern.

So up to equivalence modulo the trivial bijections we need to investigate 18 sets of restrictions that are represented in the table below.

We define the double factorial n!! by 0!! = 1, and, for n > 0,

n!! = \{ \begin{matrix}n · (n − 2) ⋯ 3 · 1, & if n is odd, \\ n · (n − 2) ⋯ 4 · 2, & if n is even. \end{matrix}

Recall that the n-th Catalan number is defined by

C_{n} = \frac{1}{n + 1}\binom{2n}{n}.

Instead of writing A_{G}(n) for a set G of patterns, we will write A(n) since it will be unambiguous what set of patterns is under consideration.

Class Restrictions  Formula
1  123, 321, 132, 312
123, 321, 231, 213  2

123, 312, 132, 213

2 321, 213, 231, 312 2

123, 231, 231, 132 321, 132, 312, 231

3  132, 231, 213, 312  2
4  123, 321, 132, 231  2, if n = 3
123, 321, 312, 213  0, if n > 3

132, 213, 312, 321

5 231, 312, 213, 123 n − 1

213, 132, 231, 321 312, 231, 132, 123

6 123, 321, 132, 213 2C_{k}, if n = 2k + 1
123, 321, 231, 312  C_{k} + C_{k−1}, if n = 2k
7  123, 132, 213
231, 312, 321  \binom{n}{⌊n/2⌋}

123, 132, 231

8 123, 213, 312 n

132, 231, 321 213, 312, 321 132, 213, 231

9 132, 213, 312 1 + 2^{n−2}

132, 231, 312 213, 231, 312

123, 132, 312  Recursive Formula:
10  123, 213, 231  A(0) = 1; A(1) = 1;
132, 312, 321  A(n) = ∑_{i} \binom{n − i − 1}{i}A(n − 2i − 1) + ((n + 1) mod 2)
213, 231, 321  The first few numbers: 1, 1, 2, 3, 6, 13, 29, 72, 185 …

Class Restrictions  Formula

123, 321, 132

11 123, 321, 231 (n − 1)!! + (n − 2)!!

123, 321, 312 123, 321, 213

12 123, 231, 312 ?

132, 213, 321 123, 231

13 321, 132 ?

321, 213 123, 312

14 213, 231 ?

312, 132

15 132, 213 ?

231, 312

16 123, 321 2E_{n}, where E_{n} is the n-th Euler number

123, 132

17 321, 231 the number of involutions in S_{n}
321, 312  (Claesson, [5])

123, 213

18 132, 231 2^{n−1}

312, 213

We now give proofs and comments for the results represented in the table.

3 Proofs, remarks, comments

From now on, when talking about class i, we mean the first set of patterns in the equivalence class i according to the table above. Thus, for instance, 8 will be taken to refer to the set of patterns {123, 132, 231}.

Let us consider class 1. There are only two patterns, namely 231 and 213, that are allowed to occur. Suppose a permutation π = a_{1}a_{2} … a_{n} avoids the patterns from 1. If a_{1}a_{2}a_{3} forms a 231-pattern then a_{2}a_{3}a_{4} has to form a 213-pattern since a_{2} > a_{3}. It is easy to see that a_{3}a_{4}a_{5} has to form the pattern 231 and so on. Moreover, if we consider the letters in even positions from left to right then we get an increasing sequence any element of which is greater then any element in an odd position; letters in odd positions form a decreasing sequence when read from left to right. From this we see that there is a unique such permutation in which the letters {1, 2, …, ⌊(n + 1)/2⌋} are in the odd positions in decreasing order, and all other letters are in the even positions in increasing order.

By the same argument there is only one permutation that avoids 1 and begins with a 213-pattern. Thus, in this case A(n) = 2.

For class 2 there are only two permutations that avoid it, namely π_{1} = n(n − 1)(n − 2) … 1 and π_{2} = (n − 1)n(n − 2)(n − 3) … 1. This is because n has to be either in the leftmost position or in the second position from the left, for otherwise we have either an occurrence of the pattern 123 or of the pattern 213 that involves n. To the right of n we have to have decreasing order because otherwise we have an occurrence of a 312- or a 213-pattern. Moreover, if n is in the second position from the left then in the leftmost position we must have the letter (n − 1) because otherwise (n − 1) must be in the third place and the first three letters form a 132-pattern.

There are obviously only two permutations that avoid class 3. They are π_{1} = 12 … n and π_{2} = n(n − 1) … 1.

For class 4, only the patterns 213 and 312 are allowed. Obviously, for n = 3 we have A(n) = 2. Suppose n > 3. If a permutation π = a_{1}a_{2} … a_{n} avoids 4, then it has to be that a_{2} < a_{3}, because a_{1}a_{2}a_{3} forms either a 213or a 312-pattern. But this means that a_{2}a_{3}a_{4} cannot form a 213- or a 312pattern, whence A(n) = 0.

For class 5, n has to be either in the rightmost position or in the second position from the right, for otherwise we have an occurrence of a 312- or a 321-pattern. Moreover we must have increasing order to the left of n because otherwise we have an occurrence of a 213- or a 312-pattern. Thus there is only one permutation with n in the rightmost position. If n is in the second position from the right then (n−1) cannot be in the rightmost position, because in this case we have an occurrence of a 132-pattern that involves n and (n − 1). So in this case (n − 1) has to be in the third position from the right, and we can put any letter i other than n − 1 and n in the rightmost position. This means that A(n) = 1 + (n − 2) = n − 1.

Class 6 will be considered in Theorem 2 below.

Theorem 1. For class 7 we have A(n) = \binom{n}{⌊n/2⌋}.

Proof. Let us construct a permutation that avoids class 7 by inserting the numbers 1, 2, …, n into n slots and observing the following: The number 1 can be placed either in the rightmost slot or in the second slot from the right, since otherwise, independently of what we have to the right of 1 in the permutation, we get either a 123- or a 132-pattern, which is prohibited. If 1 has already been placed then 2 must be placed in such way that:

1. The two slots immediately to the right of 2 are not both empty, for otherwise we will get an occurrence of either a 123- or a 132-pattern involving 2;

2. If 1 is not in the rightmost slot then 2 cannot be immediately to the left of 1, because in this case we will get an occurrence of a 213-pattern involving the letters 1 and 2.

In general it is easy to see that if i letters have been placed then for some j such that 0 ≤ j ≤ i the rightmost j slots are non-empty and the 2 · (i − j) slots immediately to the left of these j slots are alternatingly empty and non-empty. By an argument analogous to the above we can only place the letter (i + 1) into either

0) the rightmost empty slot or

1) the second empty slot to the left of the leftmost non-empty slot.

If we place 1 next to the rightmost slot we assume that we use option 1).

Let us call the leftmost two slots critical slots. When we fill one of the critical slots, there is only one way to place the remaining letters, using option 0), since in this case, option 1) can not be applied any more.

So any permutation with the right properties can be written as a sequence of 0s and 1s according to which option we use in placing the ith letter (i = 1, 2, …) and we stop writing a (0,1)-sequence whenever we reach one of the critical slots.

Let us call the (0,1)-sequences thus constructed legal sequences.

Example 1. Let n = 6. The (0,1)-sequence 01101 is a legal sequence that corresponds to the permutation 5736241. But 1111 is not a legal sequence, because after 3 steps, namely 111, we are already in a critical slot and must stop writing the (0,1)-sequence.

Since obviously there is a bijection between legal sequences and permutations in class 7, our problem is to count all possible legal sequences. We prove by induction on n that the number of such sequences is equal to \binom{n}{⌊n/2⌋}.

It is easy to check this for n = 3.

Assuming that for all i < n we have A(i) = \binom{i}{⌊i/2⌋}, we prove the statement for A(n). We consider separately the cases when n is even and odd.

Suppose n is even. The number of legal sequences that begin with 0 is obviously equal to

A(n − 1) = \binom{n − 1}{⌊(n − 1)/2⌋} = \binom{n − 1}{(n − 2)/2}.

Now we prove that the number of legal sequences beginning with 1 is equal to the number of legal sequences beginning with 0. We shall show that a bijection between these legal sequences is given by the correspondence 0X ↔ 1X, where 0X is any legal (0,1)-sequence of length ℓ, \frac{n}{2} ≤ ℓ ≤ n − 1, that starts with 0. From this it follows that

A(n) = 2A(n − 1) = \binom{n−1}{(n−2)/2} + \binom{n−1}{(n−2)/2} =

= \binom{n−1}{(n−2)/2} + \binom{n−1}{n/2} = \binom{n}{n/2} = \binom{n}{⌊n/2⌋}.

So the problem is to prove that 0X ↔ 1X is a bijection.

We use induction on even n. If n = 2 then we only have the critical slots and thus there are only two legal sequences possible, namely 0 and 1. In this case X = ∅ and we have that 0X ↔ 1X is a bijection.

Suppose for all even m less than n the correspondence 0X ↔ 1X is a bijection. We consider the case m = n. Recall that n is even.

By n-permutation we mean a permutation of elements 1, 2, …, n.

A (0,1)-sequence p_{0} = 00X′ is a legal sequence that corresponds to some n-permutation avoiding 7 if and only if p′_{0} = X′ is a legal sequence that corresponds to some (n − 2)-permutation. To see this we observe that after the first two steps, p_{0} fills in the two rightmost slots. We can strike them and forget about the first two steps of p_{0}; by this, we are left with the (0,1)- sequence X′ that can be investigated (if it is a legal sequence) with respect to (n − 2)-permutations.

By the same reasoning, a (0,1)-sequence p_{1} = 10X′ is a legal sequence that corresponds to some n-permutation avoiding 7 if and only if p′_{1} = X′ is a legal sequence that corresponds to some (n − 2)-permutation.

From these arguments we conclude, that if X = 0X′ then the correspondence 0X ↔ 1X is a bijection.

For any natural number k, we write (k) instead of writing k consecutive letters 1. In particular (0) = ∅.

Suppose X = (k)0X′ and k ≥ 1. Reasoning as before, p_{0} = 0(k)0X′ is a legal sequence with respect to n-permutations if and only if p′_{0} = 0(k−1)X′ is a legal sequence with respect to (n−2)-permutations. Also, p_{1} = 1(k)0X′ is a legal sequence with respect to n-permutations if and only if p′_{1} = 1(k − 1)X′ is a legal sequence with respect to (n − 2)-permutations. By induction, for (n − 2)-permutations, the correspondence 0Y ↔ 1Y between legal sequences 0Y and 1Y is a bijection, thus the correspondence 0X ↔ 1X, when X = (k)0X′, is a bijection for n-permutations as well.

The last thing we need to observe is that since n is even, p_{0} = 0(k) is a legal sequence if and only if p_{1} = 1(k) is a legal sequence.

This proves that the correspondence 0X ↔ 1X is a bijection.

Suppose n is odd. If a legal sequence begins with 0, then we obviously have that there are A(n−1) = \binom{n−1}{(n−1)/2} such legal sequences. So to prove the statement we need to prove that the number of legal sequences that begin with 1 is equal to \binom{n−1}{(n+1)/2} because if it is so then we have

A(n) = \binom{n − 1}{(n − 1)/2} + \binom{n − 1}{(n + 1)/2} = \binom{n}{(n − 1)/2} = \binom{n}{⌊n/2⌋}.

If a legal sequence begins with 1 then either i) the number of 1s always exceeds the number of 0s, or

ii) at some point the number of 1s is equal to the number of 0s.

Let us consider case i). Here we deal with Catalan numbers, which, among many other things, count the Dyck paths. A Dyck path of length 2n is a lattice path from (0, 0) to (2n, 0) with steps (1, 1) and (1, −1) that never goes below the x-axis. Let us explain why in case i) we have \frac{1}{(n−1)/2} \binom{n−3}{(n−3)/2} legal sequences with the right properties.

We can see that the number of ones is fixed in this case and equal to (n − 1)/2. We can complete our (0,1)-sequence with 0s if necessary (in order to complete a Dyck path that corresponds to the (0,1)-sequence under consideration). Moreover, we can forget about the leftmost letter 1 because we know that it is followed by another letter 1, so we have (n − 3)/2 ones. We thus substitute k = (n − 3)/2 in the formula for the Catalan numbers, C_{k} = \frac{1}{k+1} \binom{2k}{k}, which completes the consideration of i).

In case ii) we apply induction. Let us consider the first time, say step i, when the number of 0s is equal to the number of 1s. Obviously it can occur at any even step (and not at any odd one). Moreover, because it is the first such time, if we consider initial subsequences of length less then i, we always have that in such subsequences the number of 1s exceeds the number of 0s. So in case ii), if we apply the induction hypothesis to the A(n − i), the number of legal sequences is equal to

∑_{i is even^{i=2}}^{n−3} \frac{1}{i/2}\binom{i − 2}{(i − 2)/2}A(n − i) = ∑_{i is even^{i=2}}^{n−3} \frac{1}{i/2}\binom{i − 2}{(i − 2)/2}\binom{n − i}{(n − i − 1)/2}.

So to complete the case when n is odd we need only check the following equality:

\binom{n − 1}{(n + 1)/2} =

∑_{i is even^{i=2}}^{n−3} \frac{1}{i/2}\binom{i − 2}{(i − 2)/2}\binom{n − i}{(n − i − 1)/2} + \frac{1}{(n − 1)/2}\binom{n − 3}{(n − 3)/2}.

The last term can be moved inside the sum. Since n is odd, we have n = 2m + 1 and the equation above can be rewritten as

\binom{2m}{m + 1} = ∑_{i=1}^{m} \frac{1}{i}\binom{2(i − 1)}{i − 1}\binom{2(m − i) + 1}{m − i}.

We give a combinatorial proof of this identity. We observe that the left hand side of it counts the number of all lattice paths from (0, 0) to (2m, −2) with steps (1, 1) and (1, −1).

The i-th term in the right hand side counts the number of such paths whose first step below the x-axis is just after step 2(i − 1). Now the first 2(i − 1) steps of any such path determine a Dyck path of length 2(i − 1). So there are \binom{2(i−1)}{i−1}/i possibilities for a such path to pass the point (2(i − 1), 0) and come to the point (2i − 1, −1) with the (1, −1) step. We multiply this number with \binom{2(m−i)+1}{m−i} which counts the number of all lattice paths from (2i − 1, −1) to (2m, −2) with steps (1, 1) and (1, −1). Thus, the right hand side counts the same paths as the left hand side.

This completes the case when n is odd and thereby the proof.

Example 2. For n = 4 there are indeed \binom{4}{2} = 6 permutations avoiding class 7. In the table below we show these permutations and legal sequences that correspond to them.

Permutation Corresponding legal sequence
4321  0000
3421  001
4231  01
4312  100
3412  101
2413  11

Theorem 2. For class 6 we have

A(n) = \{ \begin{matrix}2C_{k}, & if n = 2k + 1, \\ C_{k} + C_{k−1}, & if n = 2k, \end{matrix}

where C_{k} is the k-th Catalan number.

Proof. We consider n empty slots. If we fill the slots successively with the letters 1, 2, …, n then we always have one or two possibilities, namely, either

0) we place the current number in the rightmost empty slot, or

1) we place it in the second empty slot left of the leftmost non-empty slot.

Observe that we can use option 0), except in the first step, only if there is a non-empty slot to the left of the rightmost empty slot. This is a crucial difference between classes 6 and 7.

As in the proof of Theorem 1 we can consider the critical slots as well as (0,1)-sequences that appear in the obvious way (we have always one or two possibilities until we reach a critical slot and uniquely place all remaining numbers). After that we can associate the (0,1)-sequences with Dyck paths and apply the formula for the number of Dyck paths.

The number of legal sequences that correspond to the permutations avoiding class 6, whose rightmost letter is 1, is equal to

\frac{1}{⌊(n − 1)/2⌋ + 1}\binom{2 · ⌊(n − 1)/2⌋}{⌊(n − 1)/2⌋}.

The number of legal sequences that correspond to the permutations avoiding class 6, with the second letter from the right equals 1, is equal to

\frac{1}{⌊n/2⌋ + 1}\binom{2 · ⌊n/2⌋}{⌊n/2⌋}.

From these facts we have that

A(n) = \frac{1}{⌊n/2⌋ + 1}\binom{2 · ⌊n/2⌋}{⌊n/2⌋} + \frac{1}{⌊(n − 1)/2⌋ + 1}\binom{2 · ⌊(n − 1)/2⌋}{⌊(n − 1)/2⌋}.

Substituting n by 2k + 1 and 2k, respectively, completes the proof.

For class 8, 1 must be either in the rightmost position or in the second position from the right. It is easy to see that the letters to the left of 1 must be in decreasing order. So there are n ways to choose the rightmost element of a permutation and all other elements can be placed uniquely, so there are n permutations avoiding 8.

For class 9, if 1 is in the rightmost position then we must place all other letters in decreasing order, so in this case we have the permutation π = n(n − 1) … 21 that avoids class 9.

Assume that 1 is not in the rightmost position. The letters to the left of 1 must be in decreasing order. On the other hand it is easy to see that the letters to the right of 1 must be in increasing order (the set of such elements is non-empty). But 2 can not be to the left of 1 since in this case we obviously have an occurrence of a 213-pattern in the permutation that involves the letters 1 and 2. So 2 is immediately right of 1. Thus, to determine a permutation in class 9 is equivalent to partitioning the letters {3, 4, …, n} into two blocks. There are 2^{n−2} ways of doing it. One of the blocks is all elements of a permutation to the right of 12, and the other one is all elements to the left of 12. So there are 1 + 2^{n−2} permutations avoiding class 9.

Let us consider class 10. We explain how to get a recurrence relation for A(n) in this case.

It is easy to see that 1 is either in the rightmost position or in the second position from the right. In the first case there are A(n−1) permutations that avoid 10. In the second case we can place the letter 2 either in the position immediately left of 1 or in the second position left of 1.

In the first of these cases we choose from the remaining (n − 2) letters a candidate for the rightmost position. One can do this in (n − 2) ways. Then we multiply this by A(n − 3) since three of rightmost positions do not affect to placement of all other letters in a permutation.

So we need to consider the case when 2 is in the second position left of 1. In general, we need to consider the case when the letters 1, 2, …, i have been already placed in such way that 2i rightmost positions are alternatingly empty and non-empty, the rightmost position is empty, and these i letters are in decreasing order from the left to the right. If we place (i + 1) immediately left of the leftmost non-empty position then we choose i elements from the remaining (n−i−1) elements in order to fill in i of rightmost empty positions. We observe that we must fill in the chosen elements in increasing order from the left to the right, otherwise we get an occurrence of a 312-pattern that is prohibited. Then we multiply this by A(n − 2i − 1) because in this case the (2i + 1) rightmost letters do not affect the placement of the other letters in the permutation. So we need to consider the case when (i + 1) is in the second position left of i and so on.

So we have

A(n) = ∑_{i} \binom{n − i − 1}{i}A(n − 2i − 1) + ((n + 1) mod 2).

The last term appears because if n is odd we have to consider the permutation

π = \frac{n + 1}{2} \frac{n − 1}{2} \frac{n + 3}{2} \frac{n − 3}{2} … 2(n − 1)1n,

which avoids 10 and which is not counted in the sum.

As initial conditions one can take A(0) = 1, A(1) = 1.

Theorem 3. For class 11 we have A(n) = (n − 1)!! + (n − 2)!!.

Proof. Since the patterns 123 and 321 can not occur in the permutations avoiding class 11, such permutations are alternating or reverse alternating, that is, of the form a_{1} > a_{2} < a_{3} > ⋯ or a_{1} < a_{2} > a_{3} < ⋯, with one more restriction. One can easily see that 1 is either in the rightmost position or next to this position, for otherwise we have an occurrence of a 123- or 132pattern. If we go from the right to the left starting from 1 and jumping over one element then we get an increasing sequence of letters because otherwise we have an occurrence of the pattern 132.

Let P_{1}(n) be the number of permutations having 1 in the rightmost position and let P_{2}(n) be the number of permutations having 1 in the next to the rightmost position. Then obviously

A(n) = P_{1}(n) + P_{2}(n).

It is easy to see that

\begin{matrix}P_{1}(n) = P_{2}(n − 1), \\ P_{2}(n) = (n − 1)P_{2}(n − 2) \end{matrix}

whence P_{1}(n) = (n − 2)!! and P_{2}(n) = (n − 1)!!.

Class 16 is a classically studied object. Permutations that avoid 16 are the alternating and the reverse alternating permutations. It is well known that the exponential generating function for the number of such permutations is 2(tan x+sec x)^{2}. The initial values for A(n) are 1, 2, 4, 10, 32, 122, 544, 2770, … For the result on class 17 we refer the reader to Porism 10 in [5].

Finally, for class 18 we can observe that to the left of 1 in such a permutation we must have a decreasing subword and to the right of 1 we must have an increasing subword, since otherwise we have either a 132- or a 231pattern. Thus we can choose the elements to the right of 1 from the set {2, 3, …, n} in 2^{n−1} ways and then arrange uniquely the right hand side and the left hand side (elements of a permutation to the left of 1). So there are 2^{n−1} permutations that avoid class 18.

References

[1] E. Babson, E. Steingrímsson: Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. 44 (2000), Art. B44b, 18 pp.

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

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

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

[5] A. Claesson: Generalised Pattern Avoidance, European J. Combin. 22 (2001), no. 7, 961–971.

[6] S. Elizalde and M. Noy: Enumeration of Subwords in Permutations, Proceedings of FPSAC 2001.

[7] M. Klazar: Counting pattern-free set partitions. I. A generalisation of Stirling numbers of the second kind, European J. Combinatorics 21 (2000), no. 3, 367–378.

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

[9] N. J. A. Sloane and S. Plouffe. The Encyclopedia of Integer Sequences, Academic Press, (1995) http://www.research.att.com/∼njas/sequences/.

[10] R. P. Stanley: Enumerative Combinatorics, Vol. 1, Cambridge University Press, (1997).

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

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