COUNTING OCCURRENCES OF A PATTERN OF TYPE (1, 2) OR (2, 1) IN PERMUTATIONS

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. 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.

With respect to being equidistributed there are three different classes of patterns of type (1, 2) or (2, 1). We present a recursion for the number of permutations containing exactly one occurrence of a pattern of the first or the second of the aforementioned classes, and we also find an ordinary generating function for these numbers. We prove these results both combinatorially and analytically. Finally, we give the distribution of any pattern of the third class in the form of a continued fraction, and we also give explicit formulas for the number of permutations containing exactly r occurrences of a pattern of the third class when r ∈ {1, 2, 3}.

1. Introduction and preliminaries

Let [n] = {1, 2, …, n} and denote by S_{n} the set of permutations of [n]. We shall view permutations in S_{n} as words with n distinct letters in [n].

Classically, a pattern is a permutation σ ∈ S_{k}, and an occurrence of σ in a permutation π = a_{1}a_{2} ⋯ a_{n} ∈ S_{n} is a subword of π that is order equivalent to σ. For example, an occurrence of 132 is a subword a_{i}a_{j}a_{k} (1 ≤ i < j < k ≤ n) of π such that a_{i} < a_{k} < a_{j}. We denote by s_{σ}^{r}(n) the number of permutations in S_{n} that contain exactly r occurrences of the pattern σ.

In the last decade much attention has been paid to the problem of finding the numbers s_{σ}^{r}(n) for a fixed r ≥ 0 and a given pattern σ (see [1, 2, 4, 6, 7, 8, 11, 13, 14, 16, 17, 18, 19, 20, 21] ). Most of the authors consider only the case r = 0, thus studying permutations avoiding a given pattern. Only a few papers consider the case r > 0, usually restricting themselves to patterns of length 3. Using two simple involutions (reverse and complement) on S_{n} it is immediate that with respect to being equidistributed, the six patterns of length three fall into the two classes {123, 321} and \{132, 213, 231, 312\}. Noonan [15] proved that s_{123}^{1}(n) = \frac{3}{n} \binom{2n}{n−3}. A general approach to the problem was suggested by Noonan and Zeilberger [16]; they gave another proof of Noonan’s result, and conjectured that

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

and s_{132}^{1}(n) = \binom{2n−3}{n−3}. The latter conjecture was proved by Bóna in [7]. A conjecture of Noonan and Zeilberger states that s_{σ}^{r}(n) is P -recursive in n for any r and σ. It was proved by Bóna [5] for σ = 132.

Mansour and Vainshtein [14] suggested a new approach to this problem in the case σ = 132, which allows one to get an explicit expression for s_{132}^{r}(n) for any given r.

Date: October 8, 2002.

More precisely, they presented an algorithm that computes the generating function ∑_{n≥0} s_{132}^{r}(n)x^{n} for any r ≥ 0. To get the result for a given r, the algorithm performs certain routine checks for each element of the symmetric group S_{2r}. The algorithm has been implemented in C, and yields explicit results for 1 ≤ r ≤ 6.

In [3] 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 permutation statistics. Two examples of (generalized) patterns are 1 32 and 13 2. An occurrence of 1 32 in a permutation π = a_{1}a_{2} ⋯ a_{n} is a subword a_{i}a_{j}a_{j+1} of π such that a_{i} < a_{j+1} < a_{j}. Similarly, an occurrence of 13 2 is a subword a_{i}a_{i+1}a_{j} of π such that a_{i} < a_{j} < a_{i+1}. More generally, if xyz ∈ S_{3} and π = a_{1}a_{2} ⋯ a_{n} ∈ S_{n}, then we define

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

where proj(x_{1}x_{2}x_{3})(i) = |{j ∈ {1, 2, 3} : x_{j} ≤ x_{i}}| for i ∈ {1, 2, 3} and x_{1}, x_{2}, x_{3} ∈ [n]. For instance, proj(127) = proj(138) = proj(238) = 123, and

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

Similarly, we also define (xy z) π = (z yx) π^{r}, where π^{r} denotes the reverse of π, that is, π read backwards.

For any word (finite sequence of letters), w, we denote by |w| the length of w, that is, the number of letters in w. A pattern σ = σ_{1} σ_{2} ⋯ σ_{k} containing exactly k − 1 dashes is said to be of type (|σ_{1}|, |σ_{2}|, …, |σ_{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}).

In [11] Elizalde and Noy presented the following theorem regarding the distribution of the number of occurrences of any pattern of type (3).

Theorem 1 (Elizalde and Noy [11]). Let h(x) = \sqrt{(x − 1)(x + 3)}. Then

∑_{π∈S} x^{(123)π} \frac{t^{|π|}}{|π|!} = \frac{2h(x)e^{\frac{1}{2} (h(x)−x+1)t}}{h(x) + x + 1 + (h(x) − x − 1)e^{h(x)t}} ,

∑_{π∈S} x^{(213)π} \frac{t^{|π|}}{|π|!} = \frac{1}{1 − ∫_{0}^{t} e^{(x−1)z^{2}/2}dz} .

The easy proof of the following proposition can be found in [9]. Proposition 2 (Claesson [9]). With respect to being equidistributed, the twelve patterns of type (1, 2) or (2, 1) fall into the three classes

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

In the subsequent discussion we refer to the classes of the proposition above (in the order that they appear) as Class 1, 2 and 3 respectively.

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

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

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

COUNTING PATTERNS OF TYPE (1, 2) OR (2, 1) 3

In particular, since B_{n} is not P -recursive in n, this result implies that for generalized patterns the conjecture that s_{σ}^{r}(n) is P -recursive in n is false for r = 0 and, for example, σ = 1 23.

This paper is organized as follows. In Section 2 we find a recursion for the number of permutations containing exactly one occurrence of a pattern of Class 1, and we also find an ordinary generating function for these numbers. We prove these results both combinatorially and analytically. Similar results are also obtained for patterns of Class 2. In Section 3 we give the distribution of any pattern of Class 3 in the form of a continued fraction, and we also give explicit formulas for the number of permutations containing exactly r occurrences of a pattern of Class 3 when r ∈ {1, 2, 3}.

2. Counting occurrences of a pattern of Class 1 or 2

Theorem 4. Let u_{1}(n) be the number of permutations of length n containing exactly one occurrence of the pattern 1 23 and let B_{n} be the nth Bell number. The numbers u_{1}(n) satisfy the recurrence

u_{1}(n + 2) = 2u_{1}(n + 1) + ∑_{k=0}^{n−1} \binom{n}{k}[u_{1}(k + 1) + B_{k+1}],

whenever n ≥ −1, with the initial condition u_{1}(0) = 0.

Proof. Each permutation π ∈ S_{n+2}^{1}(1 23) contains a unique subword abc such that a < b < c and bc is a segment of π. Let x be the last letter of π and define the sets T , T′, and T′′ by

π ∈ \begin{cases}T & if x = 2, \\ T′ & if x ≠ 2 and a = 1, \\ T′′ & if x ≠ 2 and a ≠ 1. \end{cases}

Then S_{n+2}^{1}(1 23) is the disjoint union of T , T′, and T′′, so

u_{1}(n + 2) = |T | + |T′| + |T′′|.

Since removing/adding a trailing 2 from/to a permutation does not affect the number of hits of 1 23, we immediately get

|T | = u_{1}(n + 1).

For the cardinality of T′ we observe that if x ≠ 2 and a = 1 then b = 2: If the letter 2 precedes the letter 1 then every hit of 1 23 with a = 1 would cause an additional hit of 1 23 with a = 2 contradicting the uniqueness of the hit of 1 23; if 1 precedes 2 then a = 1 and b = 2. Thus we can factor any permutation π ∈ T′ uniquely in the form π = σ2τ, where σ is (1 23)-avoiding, the letter 1 is included in σ, and τ is nonempty and (12)-avoiding. Owing to Proposition 3 we have showed

|T′| = ∑_{k=0}^{n−1} \binom{n}{k}B_{k+1}.

Suppose π ∈ T′′. Since x ≠ 2 and a ≠ 1 we can factor π uniquely in the form π = σ1τ, where σ contains exactly one occurrence of 1 23, the letter 2 is included in σ, and τ is nonempty and (12)-avoiding. Consequently,

|T′′| = ∑_{k=0}^{n} \binom{n}{k}u_{1}(k + 1),

which completes the proof. □

Example 5. Let us consider all permutations of length 5 that contain exactly one occurrence of 1 23, and give a small illustration of the proof of Theorem 12. If T , T′ and T′′ are defined as above then

T = \underline{1}\underline{3}\underline{5}4|2 \underline{1}4\underline{3}\underline{5}|2 \underline{1}\underline{4}\underline{5}3|2 \underline{1}5\underline{3}\underline{4}|2 4\underline{1}\underline{3}\underline{5}|2 5\underline{1}\underline{3}\underline{4}|2 \underline{3}\underline{4}\underline{5}1|2

T′ = \begin{matrix}\underline{1}|\underline{2}\underline{5}43 \underline{1}3|\underline{2}\underline{5}4 \underline{1}4|\underline{2}\underline{5}3 \underline{1}43|\underline{2}\underline{5} \underline{1}5|\underline{2}\underline{4}3 \underline{1}53|\underline{2}\underline{4} \\ \underline{1}54|\underline{2}\underline{3} 3\underline{1}|\underline{2}\underline{5}4 3\underline{1}4|\underline{2}\underline{5} 3\underline{1}5|\underline{2}\underline{4} 34\underline{1}|\underline{2}\underline{5} 35\underline{1}|\underline{2}\underline{4} \\ 4\underline{1}|\underline{2}\underline{5}3 4\underline{1}3|\underline{2}\underline{5} 4\underline{1}5|\underline{2}\underline{3} 43\underline{1}|\underline{2}\underline{5} 45\underline{1}|\underline{2}\underline{3} 5\underline{1}|\underline{2}\underline{4}3 \\ 5\underline{1}3|\underline{2}\underline{4} 5\underline{1}4|\underline{2}\underline{3} 53\underline{1}|\underline{2}\underline{4} 54\underline{1}|\underline{2}\underline{3} \end{matrix}

T′′ = \begin{matrix}\underline{2}\underline{3}\underline{4}|15 \underline{2}\underline{3}\underline{5}|14 \underline{2}\underline{3}\underline{5}4|1 \underline{2}4\underline{3}\underline{5}|1 \underline{2}\underline{4}\underline{5}|13 \\ \underline{2}\underline{4}\underline{5}3|1 \underline{2}5\underline{3}\underline{4}|1 \underline{3}\underline{4}\underline{5}2|1 4\underline{2}\underline{3}\underline{5}|1 5\underline{2}\underline{3}\underline{4}|1 \end{matrix}

where the underlined subword is the unique hit of 1 23, and the bar indicates how the permutation is factored in the proof of Theorem 12. Theorem 6. Let v_{1}(n) be the number of permutations of length n containing exactly one occurrence of the pattern 1 32 and let B_{n} be the nth Bell number. The numbers v_{1}(n) satisfy the recurrence

v_{1}(n + 1) = v_{1}(n) + ∑_{k=1}^{n−1} [\binom{n}{k}v_{1}(k) + \binom{n − 1}{k − 1}B_{k}] ,

whenever n ≥ 0, with the initial condition v_{1}(0) = 0.

Proof. Each permutation π ∈ S_{n+2}^{1}(1 32) contains a unique subword acb such that a < b < c and cb is a segment of π. Define the sets T and T′ by

π ∈ \begin{cases}T & if a = 1, \\ T′ & if a ≠ 1. \end{cases}

Then S_{n+2}^{1}(1 32) is the disjoint union of T and T′, so

v_{1}(n + 2) = |T | + |T′|.

For the cardinality of T we observe that if a = 1 then b = 2: If the letter 2 precedes the letter 1 or 12 is a segment of π then every hit of 1 23 with a = 1 would cause an additional hit of 1 32 with a = 2 contradicting the uniqueness of the hit of 1 23; if 1 precedes 2 then a = 1 and b = 2. Thus we can factor π uniquely in the form π = σx2τ, where σx is (1 32)-avoiding, the letter 1 is included in σ, and τ is nonempty and (12)- avoiding. Let R_{n} be the set of (1 32)-avoiding permutations of [n] that do not end with the letter 1. Since the letter 1 cannot be the last letter of a hit of 1 32, we have, by Proposition 3, that |S_{n}^{0}(1 32) \ R_{n}| = B_{n−1}. Consequently, |R_{n}| = B_{n} − B_{n−1} and

|T | = ∑_{k=1}^{n} \binom{n − 1}{k − 1}|R_{k}|

= ∑_{k=1}^{n} \binom{n − 1}{k − 1}(B_{k} − B_{k−1})

= ∑_{k=1}^{n−1} \binom{n − 1}{k − 1}B_{k}.

For the last identity we have used the familiar recurrence relation B_{n+1} = ∑_{k=0}^{n} \binom{n}{k}B_{k}.

Suppose π ∈ T′. Since a ≠ 1 we can factor π uniquely in the form π = σ1τ, where σ contains exactly one occurrence of 1 32, and τ is nonempty and (12)-avoiding. Accordingly,

|T′′| = ∑_{k=0}^{n} \binom{n}{k}v_{1}(k),

which completes the proof. □

Let σ be a pattern of Class 1 or 2. Using combinatorial reasoning we have found a recursion for the number of permutations containing exactly one occurrence of the pattern σ (Theorem 4 and 6). More generally, given r ≥ 0, we would like to find a recursion for the number of permutations containing exactly r occurrence of the pattern σ. Using a more general and analytic approach we will now demonstrate how this (at least in principle) can be achieved.

Let S_{σ}^{r}(x) be the generating function S_{σ}^{r}(x) = ∑_{n} s_{σ}^{r}(n)x^{n}. To find functional relations for S_{σ}^{r}(x) the following lemma will turn out to be useful. Lemma 7. If {a_{n}} is a sequence of numbers and A(x) = ∑_{n≥0} a_{n}x^{n} is its ordinary generating function, then, for any d ≥ 0,

∑_{n≥0} [∑_{j=0}^{n} \binom{n}{j}a_{j+d}] x^{n} = \frac{(1 − x)^{d−1}}{x^{d}} [A(\frac{x}{1 − x}) − ∑_{j=0}^{d−1} a_{j}(\frac{x}{1 − x})^{j}] .

Proof. It is plain that

∑_{n≥0}[∑_{j=0}^{n} \binom{n}{j}a_{j}]x^{n} = \frac{1}{1 − x}A(\frac{x}{1 − x}).

See for example [12, p 192]. On the other hand,

∑_{n≥0} a_{n+d}x^{n} = \frac{1}{x^{d}} [A(x) − ∑_{j=0}^{d−1} a_{j}x^{j}].

Combining these two identities we get the desired result. □

Define S_{n}^{r}(σ) to be the set of permutations π ∈ S_{n} such that (σ)π = r. Let s_{σ}^{r}(n) = |S_{n}^{r}(σ)| for r ≥ 0 and s_{σ}^{r}(n) = 0 for r < 0. Given b_{1}, b_{2}, …, b_{k} ∈ ℕ, we also define

s_{σ}^{r}(n; b_{1}, b_{2}, …, b_{k}) = #{a_{1}a_{2} ⋯ a_{n} ∈ S_{n}^{r}(σ) | a_{1}a_{2} ⋯ a_{k} = b_{1}b_{2} ⋯ b_{k}}.

As a direct consequence of the above definitions, we have

s_{σ}^{r}(n) = ∑_{j=1}^{n} s_{σ}^{r}(n; j).  (1)

We start by considering patterns that belong to Class 1 and we use 12 3 as a representative of this class. Let us define

u_{r}(n; b_{1}, …, b_{k}) = s_{12 3}^{r}(n; b_{1}, …, b_{k}),
u_{r}(n) = s_{12 3}^{r}(n),
U_{r}(x) = S_{12 3}^{r}(x).

Lemma 8. Let n ≥ 1. We have u_{r}(n; n − 1) = u_{r}(n; n) = u_{r}(n − 1) and

u_{r}(n; i) = ∑_{j=1}^{i−1} u_{r}(n − 1; j) + ∑_{j=0}^{n−i−1} u_{r−j}(n − 1; n − 1 − j),

whenever 1 ≤ i ≤ n − 2.

Proof. If a_{1}a_{2} ⋯ a_{n} is any permutation of [n] then

(12 3)a_{1}a_{2} ⋯ a_{n} = (12 3)a_{2}a_{3} ⋯ a_{n} + \begin{cases}n − a_{2} & if a_{1} < a_{2}, \\ 0 & if a_{1} > a_{2}. \end{cases}

Hence,

u_{r}(n; i) = ∑_{j=1}^{i−1} u_{r}(n; i, j) + ∑_{j=i+1}^{n} u_{r}(n; i, j)

= ∑_{j=1}^{i−1} u_{r}(n − 1; j) + ∑_{j=i+1}^{n} u_{r−n+j}(n − 1; j − 1)

= ∑_{j=1}^{i−1} u_{r}(n − 1; j) + ∑_{j=0}^{n−i−1} u_{r−j}(n − 1; n − 1 − j).

For i = n − 1 or i = n it is easy to see that u_{r}(n; i) = u_{r}(n − 1). □

Using Lemma 8 we quickly generate the numbers u_{r}(n); the first few of these numbers are given in Table 1. Given r ∈ ℕ we can also use Lemma 8 to find a

n\r  0  1  2  3  4  5  6
0  1
1  1
2  2
3  5  1
4  15  7  1  1
5  52  39  13  12  2  1  1
6  203  211  112  103  41  24  17
7  877  1168  843  811  492  337  238
8  4140  6728  6089  6273  4851  3798  2956
9  21147 40561 43887 48806 44291 38795 33343
10 115975 256297 321357 386041 394154 379611 355182

Table 1. The number of permutations of length n containing exactly r occurrences of the pattern 12-3.

functional relation determining U_{r}(x). Here we present such functional relations for r = 0, 1, 2 and also explicit formulas for r = 0, 1.

Equation 1 tells us how to compute u_{r}(n) if we are given the numbers u_{r}(n; i). For the case r = 0 Lemma 9, below, tells us how to do the converse.

Lemma 9. If 1 ≤ i ≤ n − 2 then

u_{0}(n; i) = ∑_{j=0}^{i−1} \binom{i − 1}{j}u_{0}(n − 2 − j).

Proof. For n = 1 the identity is trivially true. Assume the identity is true for n = m. We have

u_{0}(m + 1; i) = ∑_{j=1}^{i−1} u_{0}(m; j) + u_{0}(m − 1)  by Lemma 8

= ∑_{j=1}^{i−1} ∑_{k=0}^{j−1} \binom{j − 1}{k}u_{0}(m − 2 − k) + u_{0}(m − 1)

by the induction hypothesis

= ∑_{j=1}^{i−1} ∑_{k=j−1}^{i−2} \binom{k}{j − 1}u_{0}(m − 1 − j).

Using the familiar equality \binom{1}{k} + \binom{2}{k} + ⋯ + \binom{n}{k} = \binom{n+1}{k+1} we then get

u_{0}(m + 1; i) = ∑_{j=1}^{i−1} \binom{i − 1}{j}u_{0}(m − 1 − j).

Thus the identity is true for n = m + 1 and by the principle of induction the desired identity is true for all n ≥ 1. □

The following proposition is a direct consequence of Proposition 3. However, we give a different proof. The proof is intended to illustrate the general approach. It is advisable to read this proof before reading the proof of Theorem 4′ below. Proposition 10. The ordinary generating function for the number of (12 3)-avoiding permutations of length n is

U_{0}(x) = ∑_{k≥0} \frac{x^{k}}{(1 − x)(1 − 2x) ⋯ (1 − kx)}.

Proof. We have

u_{0}(n) = ∑_{k=1}^{n} u_{0}(n; k)  by Equation 1

= 2u_{0}(n − 1) + ∑_{i=1}^{n−2} ∑_{j=0}^{i−1} \binom{i − 1}{j}u_{0}(n − 2 − j)  by Lemma 8 and 9

= u_{0}(n − 1) + ∑_{i=0}^{n−2} \binom{n − 2}{i}u_{0}(n − 1 − i)  by ∑_{i=k}^{n} \binom{i}{k} = \binom{n + 1}{k + 1}

= u_{0}(n − 1) + ∑_{i=0}^{n−2} \binom{n − 2}{i}u_{0}(i + 1).

Therefore, by Lemma 7, we have

U_{0}(x) = xU_{0}(x) + 1 − x + xU_{0} (\frac{x}{1 − x}),

which is equivalent to

U_{0}(x) = 1 + \frac{x}{1 − x}U_{0} (\frac{x}{1 − x}).

An infinite number of applications of this identity concludes the proof. □

We now derive a formula for U_{1}(x) that is somewhat similar to the one for U_{0}(x). The following lemma is a first step in this direction.

Lemma 11. If 1 ≤ i ≤ n − 2 then

u_{1}(n; i) = ∑_{j=0}^{i−1} \binom{i − 1}{j}u_{1}(n − 2 − j) + u_{0}(n; i).

Proof. For n = 1 the identity is trivially true. Assume the identity is true for n = m. Lemma 8 and the induction hypothesis imply

u_{1}(m + 1; i) = ∑_{j=1}^{i−1} u_{1}(m; j) + u_{1}(m − 1) + u_{0}(m − 1)

= ∑_{j=0}^{i−1} \binom{j − 1}{k}u_{1}(m − 1 − j) + ∑_{j=1}^{i−1} u_{0}(m; j) + u_{0}(m − 1).

In addition, Lemma 9 implies

u_{0}(m + 1; i) = ∑_{j=1}^{i−1} ∑_{k=0}^{j−1} \binom{j − 1}{k}u_{0}(n − 2 − k) + u_{0}(n − 1)

= ∑_{j=0}^{i−1} \binom{i − 1}{j}u_{0}(n − 1 − j)

= ∑_{j=1}^{i−1} u_{0}(m; j) + u_{0}(m − 1).

Thus the identity is true for n = m + 1 and by the principle of induction the desired identity is true for all n ≥ 1. □

Next, we rediscover Theorem 4. Theorem 4′. Let u_{1}(n) be the number of permutations of length n containing exactly one occurrence of the pattern 12 3 and let B_{n} be the nth Bell number. The numbers u_{1}(n) satisfy the recurrence

u_{1}(n + 2) = 2u_{1}(n + 1) + ∑_{k=0}^{n−1} \binom{n}{k}[u_{1}(k + 1) + B_{k+1}],

whenever n ≥ −1, with the initial condition u_{1}(0) = 0.

Proof. Similarly to the proof of Proposition 10, we use Equation 1, Lemma 8, 9, and 11 to get

u_{1}(n) = 2u_{1}(n − 1) + ∑_{i=1}^{n−2} [∑_{j=0}^{i−1} \binom{i − 1}{j}u_{1}(n − 2 − j) + u_{0}(n; i)]

= 2u_{1}(n − 1) + ∑_{i=1}^{n−2} ∑_{j=0}^{i−1} \binom{i − 1}{j}(u_{1}(n − 2 − j) + u_{0}(n − 2 − j))

= u_{1}(n − 1) − u_{0}(n − 1) + ∑_{i=0}^{n−2} \binom{n − 2}{i}(u_{1}(i + 1) + u_{0}(i + 1))

= 2u_{1}(n − 1) + ∑_{i=0}^{n−3} \binom{n − 2}{i}(u_{1}(i + 1) + u_{0}(i + 1)).
□

Corollary 12. The ordinary generating function, U_{1}(x), for the number of permutations of length n containing exactly one occurrence of the pattern 12 3 satisfies the functional equation

U_{1}(x) = \frac{x}{1 − x}(U_{1}(\frac{x}{1 − x}) + U_{0}(\frac{x}{1 − x}) − U_{0}(x)).

Proof. The result follows from Theorem 4 together with Lemma 7. □

Corollary 13. The ordinary generating function for the number of permutations of length n containing exactly one occurrence of the pattern 12 3 is

U_{1}(x) = ∑_{n≥1} \frac{x}{1 − nx} ∑_{k≥0} \frac{kx^{k+n}}{(1 − x)(1 − 2x) ⋯ (1 − (k + n)x)}.

Proof. We simply apply Corollary 12 an infinite number of times and in each step we perform some rather tedious algebraic manipulations. □

Theorem 14. The ordinary generating function, U_{2}(x), for the number of permutations of length n containing exactly two occurrences of the pattern 12 3 satisfies the functional equation

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

Proof. The proof is similar to the proofs of Lemma 11, Theorem 4’ and Corollary 12, and we only sketch it here.

Lemma 8 yields

u_{2}(n; n) = u_{2}(n − 1)
u_{2}(n; n − 1) = u_{2}(n − 1)
u_{2}(n; n − 2) = u_{2}(n − 1) − u_{2}(n − 2) + u_{1}(n − 2)

and, by means of induction,

u_{2}(n; i) = u_{1}(n; i) + u_{0}(n; i) − u_{0}(n − 1; i) + ∑_{j=0}^{i−1} \binom{i − 1}{j}u_{2}(n − 2 − j),

whenever 1 ≤ i ≤ n − 3. Therefore, u_{2}(0) = u_{2}(1) = u_{2}(2) = 0 and

u_{2}(n) = 3u_{2}(n − 1) − u_{2}(n − 2) + u_{1}(n − 2)+

∑_{i=1}^{n−3} \binom{n − 3}{i}(u_{2}(n − 1 − i) + u_{1}(n − 1 − i) + u_{0}(n − 1 − i) − u_{0}(n − 2 − i)).

whenever n ≥ 3. Thus, the result follows from Lemma 7. □

We now turn our attention to patterns that belong to Class 2 and we use 23 1 as a representative of this class. The results found below regarding the 23 1 pattern are very similar to the ones previously found for the 12 3 pattern, and so are the proofs; therefore we choose to omit most of the proofs. However, we give the necessary lemmas from which the reader may construct her/his own proofs.

Define

v_{r}(n; b_{1}, …, b_{k}) = s_{23 1}^{r}(n; b_{1}, …, b_{k}),
v_{r}(n) = s_{23 1}^{r}(n),
V_{r}(x) = S_{23 1}^{r}(x).

If a_{1}a_{2} ⋯ a_{n} is any permutation of [n] then

(23 1)a_{1}a_{2} ⋯ a_{n} = (23 1)a_{2}a_{3} ⋯ a_{n} + \begin{cases}a_{1} − 1 & if a_{1} < a_{2}, \\ 0 & if a_{1} > a_{2}. \end{cases}

Lemma 15. Let n ≥ 1. We have v_{r}(n; 1) = v_{r}(n; n) = v_{r}(n − 1) and

v_{r}(n; i) = ∑_{j=1}^{i−1} v_{r}(n − 1; j) + ∑_{j=i}^{n−1} v_{r−i+1}(n − 1; j),

whenever 2 ≤ i ≤ n − 1.

Using Lemma 15 we quickly generate the numbers v_{r}(n); the first few of these numbers are given in Table 2.

n\r  0  1  2  3  4  5  6
0  1
1  1
2  2
3  5  1
4  15  6  3
5  52  32  23  10  3
6  203  171  152  98  62  22  11
7  877  944  984  791  624  392  240
8  4140  5444  6460  6082  5513  4302  3328
9  21147 32919 43626 46508 46880 41979 36774
10 115975 208816 304939 360376 396545 393476 377610

Table 2. The number of permutations of length n containing exactly r occurrences of the pattern 23-1.

Lemma 16. If 2 ≤ i ≤ n − 1 then

v_{0}(n; i) = ∑_{j=0}^{i−2} \binom{i − 2}{j}v_{0}(n − 2 − j).

Proposition 17. The ordinary generating function for the number of (23 1)-avoiding permutations of length n is

V_{0}(x) = ∑_{k≥0} \frac{x^{k}}{(1 − x)(1 − 2x) ⋯ (1 − kx)}.

Lemma 18. If 2 ≤ i ≤ n − 1 then

v_{1}(n; i) = ∑_{j=0}^{i−2} \binom{i − 2}{j}v_{1}(n − 2 − j) + v_{0}(n; i − 1) − v_{0}(n − 1, i − 1).

Theorem 6′. Let v_{1}(n) be the number of permutations of length n containing exactly one occurrence of the pattern 23 1 and let B_{n} be the nth Bell number. The numbers v_{1}(n) satisfy the recurrence

v_{1}(n + 1) = v_{1}(n) + ∑_{k=1}^{n−1} [\binom{n}{k}v_{1}(k) + \binom{n − 1}{k − 1}B_{k}] ,

whenever n ≥ 0, with the initial condition v_{1}(0) = 0.

Corollary 19. The ordinary generating function for the number of permutations of length n containing exactly one occurrence of the pattern 23 1 satisfies the functional equation

V_{1}(x) = \frac{x}{1 − x}V_{1}(\frac{x}{1 − x}) + x(V_{0}(\frac{x}{1 − x}) − V_{0}(x)).

Corollary 20. The ordinary generating function for the number of permutations of length n containing exactly one occurrence of the pattern 23 1 is

V_{1}(x) = ∑_{n≥1} \frac{x}{1 − (n − 1)x} ∑_{k≥0} \frac{kx^{k+n}}{(1 − x)(1 − 2x) ⋯ (1 − (k + n)x)}.

Theorem 21. The ordinary generating function, V_{2}(x), for the number of permutations of length n containing exactly two occurrences of the pattern 23 1 satisfies the functional equation

V_{2}(x) = \frac{x}{1 − x}(V_{2}(\frac{x}{1 − x}) + (1 − 2x)V_{1}(\frac{x}{1 − x}) + (1 − 3x + x^{2})V_{0}(\frac{x}{1 − x})) − x + x^{2}

Proof. By Lemma 5

v_{2}(n; n) = v_{2}(n − 1)
v_{2}(n; 1) = v_{2}(n − 1)
v_{2}(n; 2) = v_{2}(n − 2) + v_{1}(n − 1) − v_{1}(n − 2)
v_{2}(n; 3) = v_{2}(n − 2) + v_{2}(n − 3) + v_{1}(n − 2) − v_{1}(n − 3)+
+ v_{0}(n − 1) − v_{0}(n − 2) − v_{0}(n − 3)

and, by means of induction,

v_{2}(n; i) = ∑_{j=0}^{i−2} \binom{i − 2}{j}v_{2}(n − 2 − j) + v_{1}(n; i − 1) + v_{1}(n − 1; i − 1) − v_{0}(n − 1; i − 2)

for n − 1 ≥ i ≥ 4. Thus v_{2}(0) = v_{2}(1) = v_{2}(2) = 0 and for all n ≥ 3

v_{2}(n) = v_{2}(n − 1)+ ∑_{j=0}^{n−2} \binom{n − 2}{j}v_{2}(n − 1 − j)+

+ ∑_{j=0}^{n−3} \binom{n − 3}{j}(v_{1}(n − 1 − j) − v_{1}(n − 2 − j))+

+ ∑_{j=0}^{n−4} \binom{n − 4}{j}(v_{0}(n − 1 − j) − v_{0}(n − 2 − j) − v_{0}(n − 3 − j)).

The result now follows from Lemma 7. □

3. Counting occurrences of a pattern of Class 3

We choose 2 13 as our representative for Class 3 and we define w_{r}(n) as the number of permutations of length n containing exactly r occurrences of the pattern 2 13. We could apply the analytic approach from the previous section to the problem of determining w_{r}(n). However, a result by Clarke, Steingrímsson and Zeng [10, Corollary 11] provides us with a better option. Theorem 22. The following Stieltjes continued fraction expansion holds

∑_{π∈S} x^{1+(12)π}y^{(21)π}p^{(2 31)π}q^{(31 2)π}t^{|π|} = \frac{1}{1 − \frac{x[ 1 ]_{p,q}t}{1 − \frac{y[ 1 ]_{p,q}t}{1 − \frac{x[ 2 ]_{p,q}t}{1 − \frac{y[ 2 ]_{p,q}t}{...}}}}}

where [ n]_{p,q} = q^{n−1} + pq^{n−2} + ⋯ + p^{n−2}q + p^{n−1}.

Proof. In [10, Corollary 11] Clarke, Steingrímsson and Zeng derived the following continued fraction expansion

∑_{π∈S} y^{des π}p^{Res π}q^{Ddif π}t^{|π|} = \frac{1}{1 − \frac{[ 1 ]_{p}t}{1 − \frac{yq[ 1 ]_{p}t}{1 − \frac{q[ 2 ]_{p}t}{1 − \frac{yq^{2}[ 2 ]_{p}t}{...}}}}}

where [ n]_{p} = 1 + p + ⋯ + p^{n−1}. We refer the reader to [10] for the definitions of Ddif and Res. However, given these definitions, it is easy to see that Res = (2 31) and Ddif = (21) + (2 31) + (31 2). Moreover, des = (21) and |π| = 1 + (12)π + (21)π. Thus, substituting y(xq)^{−1} for y, pq^{−1} for p, and xt for t, we get the desired result. □

The following corollary is an immediate consequence of Theorem 22. Corollary 23. The bivariate ordinary generating function for the distribution of occurrences of the pattern 2 13 admits the Stieltjes continued fraction expansion

∑_{π∈S} p^{(2 13)π}t^{|π|} = \frac{1}{1 − \frac{[ 1 ]_{p}t}{1 − \frac{[ 1 ]_{p}t}{1 − \frac{[ 2 ]_{p}t}{1 − \frac{[ 2 ]_{p}t}{...}}}}}

where [ n]_{p} = 1 + p + ⋯ + p^{n−1}

Using Corollary 23 we quickly generate the numbers w_{r}(n); the first few of these numbers are given in Table 3. Corollary 24. The number of (2 13)-avoiding permutations of length n is

w_{0}(n) = \frac{1}{n + 1}\binom{2n}{n}.

n\r  0  1  2  3  4  5  6
0  1
1  1
2  2
3  5  1
4  14  8  2
5  42  45  25  7  1
6  132  220  198  112  44  12  2
7  429 1001  1274  1092  700  352  140
8  1430 4368  7280  8400  7460  5392  3262
9  4862 18564 38556 56100 63648 59670 47802
10 16796 77520 193800 341088 470934 541044 535990

Table 3. The number of permutations of length n containing exactly r occurrences of the pattern 2-13.

Proof. This result is explicitly stated in Proposition 3, but it also follows from Corollary 23 by putting p = 0. □

Corollary 25. The number of permutations of length n containing exactly one occurrence of the pattern 2 13 is

w_{1}(n) = \binom{2n}{n − 3}.

Proof. For m > 0 let

W (p, t; m) = \frac{1}{1 − \frac{[ m]_{p}t}{1 − \frac{[ m]_{p}t}{1 − \frac{[ m + 1 ]_{p}t}{1 − \frac{[ m + 1 ]_{p}t}{...}}}}}

Note that

W (p, t; m) = \frac{1}{1 − \frac{[ m]_{p}t}{1 − [ m]_{p}tW (p, t; m + 1).}}

Assume m > 1. Differentiating W (p, t; m) with respect to p and evaluating the result at p = 0 we get

D_{p}W (p, t; m)|_{p=0} = tC(t)^{3} + t^{2}C(t)^{5} + t^{2}C(t)^{4}D_{p}W (p, t; m + 1)|_{p=0}

where C(t) = W (0, t, 1) is the generating function for the Catalan numbers. Applying this identity an infinite number of times we get

D_{p}W (p, t, m)|_{p=0} = tC(t)^{3} + t^{2}C(t)^{5} + t^{3}C(t)^{7} + ⋯ = \frac{tC(t)^{3}}{1 − tC(t)^{2}} .

On the other hand, D_{p}W (p, t; 1)|_{p=0} = t^{2}C(t)^{4}D_{p}W (p, t; 2)|_{p=0}. Combining these two identities we get

D_{p}W (p, t; 1)|_{p=0} = \frac{t^{3}C(t)^{7}}{1 − tC(t)^{2}} .

Since ∑_{n≥0} w_{1}(n)t^{n} = D_{p}W (p, t; 1)|_{p=0} the proof is completed on extracting coefficients in the last identity. □

The proofs of the following two corollaries are similar to the proof of Corollary 25 and are omitted. Corollary 26. The number of permutations of length n containing exactly two occurrences of the pattern 2 13 is

w_{2}(n) = \frac{n(n − 3)}{2(n + 4)}\binom{2n}{n − 3}.

Corollary 27. The number of permutations of length n containing exactly three occurrences of the pattern 2 13 is

w_{3}(n) = \frac{1}{3}\binom{n + 2}{2}\binom{2n}{n − 5}.

As a concluding remark we note that there are many questions left to answer. What is, for example, the formula for w_{k}(n) in general? What are the combinatorial explanations of ns_{1 2 3}^{1}(n) = 3s_{2 13}^{1}(n) and

(n + 3)(n + 2)(n + 1)s_{2 13}^{1}(n) = 2n(2n − 1)(2n − 2)s_{2 1 3}^{1}(n)?

In addition, Corollary 25 obviously is in need of a combinatorial proof.

References

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

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

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

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

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

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

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

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

[9] A. Claesson. Generalized pattern avoidance. European J. Combin., 22(7):961–971, 2001.

[10] R.J. Clarke, E. Steingrímsson, and J. Zeng. New Euler-Mahonian statistics on permutations and words. Adv. in Appl. Math., 18(3):237–270, 1997.

[11] S. Elizalde and M. Noy. Enumeration of subwords in permutations. In Formal power series and algebraic combinatorics (Tempe, 2001), pages 179–189. Arizona State University, 2001.

[12] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete mathematics. Addison-Wesley Publishing Company, Reading, MA, second edition, 1994.

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

[14] T. Mansour and A. Vainshtein. Counting occurrences of 132 in a permutation. To appear in: Adv. Appl. Math., 2001.

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

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

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

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

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

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

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

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