GENERALIZED PATTERN AVOIDANCE WITH ADDITIONAL RESTRICTIONS

SERGEY KITAEV

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. We consider n-permutations that avoid the generalized pattern 1-32 and whose k rightmost letters form an increasing subword. The number of such permutations is a linear combination of Bell numbers. We find a bijection between these permutations and all partitions of an (n − 1)-element set with one subset marked that satisfy certain additional conditions. Also we find the e.g.f. for the number of permutations that avoid a generalized 3-pattern with no dashes and whose k leftmost or k rightmost letters form either an increasing or decreasing subword. Moreover, we find a bijection between n-permutations that avoid the pattern 132 and begin with the pattern 12 and increasing rooted trimmed trees with n + 1 nodes.

1. Introduction and Background

All permutations in this paper are written as words π = a_{1}a_{2} ⋯ a_{n}, where the a_{i} consist of all the integers 1, 2, …, n.

A pattern is a word on some alphabet of letters, where some of the letters may be separated by dashes. In our notation, the classical permutation patterns, first studied systematically by Simion and Schmidt [SchSim], are of the form p = 1-3-2, the dashes indicating that the letters in a permutation corresponding to an occurrence of p do not have to be adjacent. In the classical case, an occurrence of a pattern p in a permutation π is a subsequence in π (of the same length as the length of p) whose letters are in the same relative order as those in p. For example, the permutation 264153 has only one occurrence of the pattern 1-2-3, namely the subsequence 245. Note that a classical pattern should, in our notation, have dashes at the beginning and end. Since most of the patterns considered in this paper satisfy this, we suppress these dashes from the notation.

In [BabStein] Babson and Steingrímsson introduced generalized permutation patterns (GPs) where two adjacent letters in a pattern may be required to be adjacent in the permutation. Such an adjacency requirement is indicated by the absence of a dash between the corresponding letters in the pattern. Thus, a pattern with no dashes corresponds to a contiguous subword anywhere in a permutation. For example, the permutation π = 516423 has only one occurrence of the pattern 2-31, namely the subword 564, but the pattern 2-3-1 occurs also in the subwords 562 and 563. The motivation for introducing these patterns in [BabStein] was the study of Mahonian statistics.

A number of interesting results on GPs were obtained by Claesson [Claes]. Relations to several well studied combinatorial structures, such as set partitions, Dyck paths, Motzkin paths and involutions, were shown there. In [Kit1] the present author investigated simultaneous avoidance of two or more 3-letter GPs with no dashes. Also there is a number of works concerning GPs by Mansour (see for example [Mans1, Mans2]).

In this paper we consider avoiding some generalized 3-patterns with additional restrictions. The restrictions consist of demanding that a permutation begin or end with the pattern 12 … k or the pattern k(k− 1) … 1.

It turns out that the number of permutations that avoid the pattern 1-32 and end with the pattern 12 … k is a linear combination of the Bell numbers. The n-th Bell number is the number of ways a set of n elements can be partitioned into nonempty subsets. We find a bijection between these permutations and all partitions of an (n − 1)-element set with one subset marked that satisfy certain special conditions. In particular, in Theorem 3, we investigate the case k = 2. We get that the total number of partitions of an (n − 1)-element set with one part marked, is equal to the number of (1-32)-avoiding n-permutations that end with a 12-pattern. Lemma 2 gives us an identity involving the Bell numbers and the Stirling numbers of the second kind, which seems to be new. In Theorem 5 we prove that the number of 132-avoiding npermutations that begin with the pattern 12 is equal to the number of increasing rooted trimmed trees with n + 1 nodes.

In Sections 4 – 7, we give a complete description (in terms of exponential generating functions (e.g.f.)) for the number of permutations that avoid a pattern of the form xyz and begin or end with the pattern 12 … k or the pattern k(k − 1) … 1. We record all the results concerning these e.g.f. in the table in Section 7. The case k = 1 is equivalent to the absence of the additional restriction. This case was considered in [ElizNoy] and [Kit2].

We observe that avoidance of some pattern with the additional restrictions described above, in fact is equivalent to simultaneous avoidance of several patterns. For example, beginning with the pattern 12 is equivalent to the avoidance of the pattern [21) in the Babson-Steingrímsson notation. Thus avoidance of the pattern 132 and beginning with the pattern 12 is equivalent to simultaneous avoidance of the patterns 132 and [21). Also, ending with the pattern 123 is equivalent to simultaneously avoiding the patterns (132], (213], (231], (312] and (321].

2. Set partitions and pattern avoidance

We recall some basic definitions.

A partition of a set S is a family, π = {A_{1}, A_{2}, …, A_{k}}, of pairwise disjoint non-empty subsets of S such that S = ∪_{i}A_{i}. The total number of partitions of an n-element set is called a Bell number and is denoted B_{n}.

The Stirling number of the second kind S(n, k) is the number of ways a set with n elements can be partitioned into k disjoint, non-empty subsets. Proposition 1. Let P (n, k) be the number of n-permutations that avoid the pattern 1-32 and end with the pattern 12 … k. Then

P (n, k) = ∑_{i=0}^{n−k} \binom{n − 1}{i}B_{i}.

Proof. Suppose a permutation π = σ1τ avoids the pattern 1-32 and ends with the pattern 12 … k. The letters of τ must be in increasing order, since otherwise we have an occurrence of the pattern 1-32 involving 1. Also, σ must avoid 1-32. If |σ| = i then obviously 0 ≤ i ≤ n − k and we can choose the letters of σ in \binom{n−1}{i} ways. By [Claes, Proposition 5], the number of i-permutations that avoid the pattern 1-32 is equal to B_{i}, hence there are B_{i} ways to form σ. □

Lemma 2. We have ∑_{i=0}^{n−1} \binom{n}{i}B_{i} = ∑_{i=0}^{n} i · S(n, i).

Proof. The identity can be proved from the recurrences for S(n, k) and B_{n}, but we give a combinatorial proof.

The left-hand side of the identity is the number of ways to choose i elements from an n-element set, and then to make all possible partitions of the chosen elements.

The right-hand side is the number of ways to partition a set with n elements into i disjoint non-empty subsets (i = 1, 2, …, n) and mark one of the subsets. For example if n = 4 then \overline{1} − 24 − 3 and 1 − \overline{24} − 3 are two different partitions, where the marked subset is overlined.

A bijective correspondence between these combinatorial interpretations is given by the following: For the left-hand side, after partitioning the i chosen elements, let the remaining n−i elements form the marked subset in the partition. □

The formula for P (n, k) in Proposition 1, applied to k = 2, and Lemma 2 now give the following theorem: Theorem 3. The total number of partitions of an (n − 1)-element set with one part marked, is equal to the number of (1-32)-avoiding n-permutations that end with the pattern 12.

We give now a direct combinatorial proof of this theorem.

Proof. Suppose P = S_{1} − S_{2} − ⋯ − S_{k} is a partition of an (n − 1)- element set into k subsets with one marked subset and T_{i} is the word that consists of all elements of S_{i} in increasing order. We may, without loss of generality, assume that min(S_{i}) < min(S_{j}) if i > j. In particular, 1 ∈ S_{k}. There are two cases possible:

1) S_{k} = {1} (S_{k} is not marked set);

2) Either S_{k} = \overline{1} or 1 ∈ S_{k} and |S_{k}| ≥ 2. In the first case, to a partition P = S_{1}−S_{2}−⋯−\overline{S_{i}}−⋯−S_{k−1}−1 we

associate the permutation π(P) = nT_{1}T_{2} … T_{i−1}T_{i+1} … T_{k−1}1T_{i}, which is (1-32)-avoiding and ends with the pattern 12 since S_{i} ≠ ∅. For example 4 − \overline{23} − 1 ↦ 54123.

In the second case we adjoin n to a marked subset, and then consider the permutation π(P) = T_{1}T_{2} … T_{k}. This permutation is obviously (1-32)-avoiding since min(S_{i}) < min(S_{j}) if i > j and the letters in T_{i} are in increasing order. Also it ends with the pattern 12. For example 5 − \overline{34} − 12 ↦ 534612, and 5 − 234 − \overline{1} ↦ 523416.

Obviously in both cases we have an injection.

Now it is easy to see that the correspondence above is a surjection as well. Indeed, for any (1-32)-avoiding permutation π that ends with the pattern 12, we can check if π begins with n or not and according to this we have either case 1) or 2). In the first case, we remove n, then read π from left to right and consider all maximal increasing intervals. The elements of each such interval correspond to some subset, and we let all the letters to the right of 1 constitute the marked subset. In the second case, we divide π into maximal increasing intervals, and let the letters of each interval correspond to a subset. Then we let the interval containing n be the marked subset. Thus we have a surjection. So the correspondence is a bijection and the theorem is proved. □

The following theorem generalizes Theorem 3.

Theorem 4. Let P = S_{1}−S_{2}−⋯−S_{ℓ} be a partition of {1, 2, …, n−1} into ℓ subsets with subset S_{i} marked. We assume also that 1 ∈ S_{ℓ}. Then P (n, k) counts all possible marked partitions of {1, 2, …, n − 1} that satisfy the following conditions:

1) if i = ℓ (the last subset is marked) then |S_{ℓ}| ≥ k − 1;

2) if i ≠ ℓ and |S_{ℓ}| ≠ 1 then |S_{ℓ}| ≥ k;

3) if i ≠ ℓ and |S_{ℓ}| = 1 then |S_{i}| ≥ k − 1.

Proof. A proof of this theorem is similar to the proof of Theorem 3. We assume that min(S_{i}) < min(S_{j}) for i > j and consider three cases.

If a partition satisfies 1), that is P = S_{1} − S_{2} − ⋯ − \overline{S_{ℓ}} and |S_{ℓ}| ≥ k − 1, then adjoining n to S_{ℓ} guarantees that the permutation π(P) = T_{1}T_{2} … T_{ℓ}, which is (1-32)-avoiding, ends with k letters in increasing order.

In case 2), we adjoin n to the marked subset and consider π(P) = T_{1}T_{2} … T_{ℓ}. This permutation avoids the pattern 1-32 and ends with the pattern 12 … k since |S_{ℓ}| ≥ k.

In case 3), to a partition P = S_{1} − S_{2} − ⋯ − \overline{S_{i}} − ⋯ − S_{k−1} − 1 we associate the permutation π(P) = nT_{1}T_{2} … T_{i−1}T_{i+1} … T_{k−1}1T_{i}, which is (1-32)-avoiding and ends with at least k letters in increasing order since |S_{i}| ≥ k − 1.

That this correspondence is a bijection can be shown in a way similar to the proof of Theorem 3. □

3. Increasing rooted trimmed trees and pattern avoidance

In an increasing rooted tree, nodes are numbered and the numbers increase as we move away from the root (see [Stan, Chapter 1]). These trees are the foundation for the paper by Elizalde and Noy [ElizNoy], results from which are cited in Sections 4–6.

A trimmed tree is a tree where no node has a single leaf as a child (every leaf has a sibling).

Theorem 5. Let A_{n} denote the set of all n-permutations that avoid the pattern 132 and begin with the pattern 12. The number of permutations in A_{n} is equal to the number of increasing rooted trimmed trees (IRTTs) with n + 1 nodes.

Proof. A right-to-left minimum of a permutation π is an element a_{i} such that a_{i} < a_{j} for every j > i.

We describe a bijective correspondence F between the permutations in A_{n} and IRTTs with n + 1 nodes.

Suppose π ∈ A_{n} and π = P_{0}a_{0}P_{1}a_{1} … P_{k}a_{k}, where a_{i} are the rightto-left minima of π and P_{j} are (possibly empty) subwords of π. We construct a IRTT T = F (π) with n + 1 nodes as follows. The root of T is labelled by 0 and a_{0}, a_{1}, …, a_{k} are the labels of the root’s children if we read them from left to right. Then we let the right-to-left minima of P_{i} be the labels of the children of a_{i} and so on. It is easy to see that, since π avoids 132 and begins with 12, T avoids limbs of length 2. Also, T is an increasing rooted tree and hence T is a IRTT. For instance,

F (2 9 10 5 3 1 11 13 14 8 12 7 4 6) = [figure: 0; 1; 4; 6; 2; 3; 7; 5; 8; 12; 9; 10; 11; 13; 14]

Obviously, the correspondence F is an injection.

To see, that F is a surjection, we show how to construct the permutation π ∈ A_{n} that corresponds to a given IRTT T. The main rule is the following: If a_{i} and a_{j} are siblings, and a_{i} < a_{j}, then the labels of the nodes of the subtree below a_{j}, are all the letters in π between a_{i} and a_{j}, that is, a_{i+1}, a_{i+2}, …, a_{j−1}. If a_{i} is a single child, then the labels of the nodes of the subtree below a_{i} appear immediately left of a_{i} in π. That is, if there are k nodes in the subtree below a_{i} then the k corresponding labels form the subword a_{i−k}a_{i−k+1} … a_{i−1}. We now start from the first level of T, which consists of the root’s children, and apply this rule. After that we consider the second level and so on. The fact that T is a IRTT ensures that π avoids the pattern 132 and begins with the pattern 12. Thus, F is a bijection. □

4. Avoiding 132 and beginning with 12 … k or k(k − 1) … 1

Let E_{q}^{p}(x) denote the e.g.f. for the number of permutations that avoid the pattern q and begin with the pattern p.

If k = 1, then there is no additional restriction, that is, we are dealing with avoidance of the pattern 132 (no dashes) and thus

(1)  E_{132}^{1}(x) = \frac{1}{1 − ∫_{0}^{x} e^{−t^{2}/2} dt},

since this result is a special case of [ElizNoy, Theorem 4.1] and [Kit2, Theorem 12]. Theorem 6. We have

E_{132}^{12}(x) = \frac{e^{−x^{2}/2}}{1 − ∫_{0}^{x} e^{−t^{2}/2} dt} − x − 1,

and for k ≥ 3

E_{132}^{12...k}(x) = E_{132}^{1}(x) ∫_{0}^{x} ∫_{0}^{t_{k−2}} ⋯ ∫_{0}^{t_{2}} (e^{−t_{1}^{2}/2} − \frac{t_{1} + 1}{E_{132}^{1}(t_{1})}) dt_{1}dt_{2} ⋯ dt_{k−2}.

Proof. Let E_{n,k} denote the number of n-permutations that avoid the pattern 132 and begin with an increasing subword of length k > 0. Let π be such a permutation of length n + 1. Also, suppose k ≠ 2. If π = σ1τ then either σ = ϵ or σ ≠ ϵ where ϵ denotes the empty word. If σ = ϵ then τ must avoid 132 and begin with an increasing subword of length k −1. Otherwise σ must avoid 132 and begin with an increasing subword of length k, whereas τ must begin with the pattern 12, or be a single letter (there are n ways to choose this letter), or be ϵ. This leads to the following:

(2)  E_{n+1,k} = E_{n,k−1} + ∑_{i≥0} \binom{n}{i}E_{i,k}E_{n−i,2} + nE_{n−1,k} + E_{n,k}.

Multiplying both sides of the equality with x^{n}/n! and summing over all n we get the following differential equation

(3) \frac{d}{dx}E_{132}^{12...k}(x) = (E_{132}^{12}(x) + x + 1)E_{132}^{12...k}(x) + E_{132}^{12...(k−1)}(x),

with the initial conditions E_{132}^{12...k}(0) = 0 for k ≥ 3.

Observe that equality (3) is not valid for k = 2. Indeed, if k = 2, then it is incorrect to add the term E_{n,k−1} = E_{n,1} in (2), since this term counts the number of permutations π = 1τ with the only restriction for τ that it must avoid 132. The absence of an additional restriction for τ means that the 3 leftmost letters of π could form the pattern 132. However, we can use (3) to find E_{132}^{12}(x) by letting k equal 1. In this case we have

\frac{d}{dx}E_{132}^{1}(x) = (E_{132}^{12}(x) + x + 1)E_{132}^{1}(x),

which gives

(4)  E_{132}^{12}(x) = \frac{e^{−x^{2}/2}}{1 − ∫_{0}^{x} e^{−t^{2}/2} dt} − x − 1.

For the case k ≥ 3, it is convenient to write E_{132}^{12}(x) in the form

E_{132}^{12}(x) = B′(x) − x − 1,

where B(x) = − ln(1 − ∫_{0}^{x} e^{−t^{2}/2} dt) and thus B′(x) = exp(B(x) − \frac{x^{2}}{2} ). We will use the fact that E_{132}^{1}(x) = e^{B(x)}, which follows directly from (1) and the definition of B(x). So (3) is equivalent to the differential equation

\frac{d}{dx}E_{132}^{12...k}(x) = B′(x)E_{132}^{12...k}(x) + E_{132}^{12...(k−1)}(x)

which has the solution

E_{132}^{12...k}(x) = e^{B(x)} ∫_{0}^{x} e^{−B(t)}E_{132}^{12...(k−1)}(t) dt =

E_{132}^{1}(x) ∫_{0}^{x} \frac{E_{132}^{12...(k−1)}(t)}{E_{132}^{1}(t)}dt =

E_{132}^{1}(x) ∫_{0}^{x} ∫_{0}^{t_{2}} \frac{E_{132}^{12...(k−2)}(t_{1})}{E_{132}^{1}(t_{1})}dt_{1}dt_{2} =

E_{132}^{1}(x) ∫_{0}^{x} ∫_{0}^{t_{k−2}} ⋯ ∫_{0}^{t_{2}} \frac{E_{132}^{12}(t_{1})}{E_{132}^{1}(t_{1})}dt_{1}dt_{2} ⋯ dt_{k−2}.

Using (1) and (4) we now get the desired result. □

Using the formula for E_{132}^{12...k}(x) in Theorem 6 one can derive, in particular, that

E_{132}^{123}(x) = −\frac{1}{2} − x − \frac{x^{2}}{2} + \frac{(1 + \frac{x}{2}) e^{−x^{2}/2} − \frac{1}{2}}{1 − ∫_{0}^{x} e^{−t^{2}/2} dt} .

Theorem 7. For k ≥ 2

E_{132}^{k(k−1)...1}(x) = \frac{E_{132}^{1}(x)}{(k − 1)!} ∫_{0}^{x} t^{k−1}e^{−t^{2}/2} dt.

Proof. We proceed as in the proof of Theorem 6.

Let R_{n,k} denote the number of n-permutations that avoid the pattern 132 and begin with a decreasing subword of length k > 1 and let π be such a permutation of length n + 1. Suppose also that π = σ1τ. If τ = ϵ then, obviously, there are R_{n,k} ways to choose σ. If |τ| = 1, that is, 1 is in the second position from the right in π, then there are n ways to choose the rightmost letter in π and we multiply this by R_{k,n−1}, which is the number of ways to choose σ. If |τ| > 1 then τ must begin with the pattern 12, otherwise the letter 1 and the two leftmost letters of τ form the pattern 132, which is forbidden. So, in this case there are ∑_{i≥0} \binom{n}{i}R_{i,k}E_{n−i,2} such permutations with the right properties, where i indicates the length of σ and E_{n−i,2} is defined in the proof of Theorem 6. In the last formula, of course, R_{i,k} = 0 if i < k. Finally we have to consider the situation when 1 is in the k-th position. In this case we can choose the letters of σ in \binom{n}{k−1} ways, write them in decreasing order and then choose τ in E_{n−k+1,2} ways. Thus

(5) R_{n+1,k} = R_{n,k} + nR_{n−1,k} + ∑_{i≥0} \binom{n}{i}R_{i,k}E_{n−i,2} + \binom{n}{k − 1}E_{n−k+1,2}.

We observe that (5) is not valid for n = k − 1 and n = k. Indeed, if 1 is in the k-th position in these cases, the term \binom{n}{k−1}E_{n−k+1,2}, which counts the number of such permutations, is zero, whereas there is one “good” (n+1)-permutation in the case n = k −1 and n “good” (n+1)- permutations in case n = k. Multiplying both sides of the equality with x^{n}/n!, summing over n and using the observation above (which gives the term x^{k−1}/(k −1)!+kx^{k}/k! in the right-hand side of Equation (6)), we get

(6) \frac{d}{dx}E_{132}^{k(k−1)...1}(x) = (E_{132}^{12}(x) + x + 1) (E_{132}^{k(k−1)...1}(x) + \frac{x^{k−1}}{(k − 1)!}) ,

with the initial condition E_{k(k−1)...1}^{132}(0) = 0. We solve the equation in the way proposed in Theorem 6 and get

E_{132}^{k(k−1)...1}(x) = \frac{E_{132}^{1}(x)}{(k − 1)!} ∫_{0}^{x} \frac{(E_{132}^{12}(t) + t + 1)t^{k−1}}{E_{132}^{1}(t)} dt = \frac{E_{132}^{1}(x)}{(k − 1)!} ∫_{0}^{x} t^{k−1}e^{−t^{2}/2} dt.

□

For instance,

E_{132}^{21}(x) = \frac{1 − e^{−x^{2}/2}}{1 − ∫_{0}^{x} e^{−t^{2}/2} dt} and E_{132}^{321}(x) = \frac{1}{2} (−1 + \frac{1 − xe^{−x^{2}/2}}{1 − ∫_{0}^{x} e^{−t^{2}/2} dt}) .

Moreover, the integral ∫_{0}^{x} t^{k−1}e^{−t^{2}/2} dt from the formula for E_{132}^{k(k−1)...1}(x) can be solved to show that E_{132}^{k(k−1)...1}(x) equals

\frac{(k/2 − 1)!2^{k/2−1}}{(k − 1)!(1 − \sqrt{\frac{π}{2}} erf(x))} (1 − e^{−x^{2}/2} ∑_{i=0}^{k/2−1} \frac{x^{2i}}{2^{i}i!}) ,

if k is even, and

\frac{1}{(k − 1)!!} (−1 + \frac{1}{1 − \sqrt{\frac{π}{2}} erf(x)} (1 − e^{−x^{2}/2} ∑_{i=0}^{(k−3)/2} \frac{x^{2i+1}}{(2i + 1)!!}))

if k is odd.

In the formula above, erf(x) is the error function:

erf(x) = \frac{2}{\sqrt{π}} ∫_{0}^{x} e^{−t^{2}} dt.

5. Avoiding 123 and beginning with k(k − 1) … 1 or 12 … k

If k = 1, we have no additional restrictions and, according to [ElizNoy, Theorem 4.1],

E_{123}^{1}(x) = \frac{\sqrt{3}}{2} \frac{e^{x/2}}{cos (\frac{\sqrt{3}}{2}x + \frac{π}{6})}.

Theorem 8. For k ≥ 2

E_{123}^{k(k−1)...1}(x) = \frac{e^{x/2}}{(k − 1)! cos (\frac{\sqrt{3}}{2}x + \frac{π}{6})} ∫_{0}^{x} e^{−t/2}t^{k−1} sin (\frac{\sqrt{3}}{2}t + \frac{π}{3} ) dt.

In particular,

E_{123}^{21}(x) = \frac{\sqrt{3}}{2} tan (\frac{\sqrt{3}}{2}x + \frac{π}{6} ) − x − \frac{1}{2}.

Proof. Let P_{n,k} denote the number of n-permutations that avoid the pattern 123 and begin with a decreasing subword of length k. We observe that we can use arguments similar to the proof of Theorem 7 to get the recurrence formula for P_{n,k}. Indeed, we only need to write the letter P instead of R and E in (5):

(7) P_{n+1,k} = P_{n,k} + nP_{n−1,k} + ∑_{i≥0} \binom{n}{i}P_{i,k}P_{n−i,2} + \binom{n}{k − 1}P_{n−k+1,2}.

This formula is valid for k > 1. Multiplying both sides of the equality with x^{n}/n!, summing over n and reasoning as in the proof of Theorem 7, we get:

(8) \frac{d}{dx}E_{123}^{k(k−1)...1}(x) = (E_{123}^{21}(x) + x + 1) (E_{123}^{k(k−1)...1}(x) + \frac{x^{k−1}}{(k − 1)!}) ,

with the initial condition E_{123}^{k(k−1)...1}(0) = 0. To solve (8), we need to know E_{123}^{21}(x). To find it, we consider the case k = 1. In this case we have almost the same recurrence as we have in (7), but we must remove the last term in the right-hand side:

P_{n+1,1} = P_{n,1} + nP_{n−1,1} + ∑_{i≥0} \binom{n}{i}P_{i,k}P_{n−i,2}.

After multiplying both sides of the last equality with x^{n}/n! and summing over n, we have

\frac{d}{dx}E_{123}^{1}(x) = (E_{123}^{21}(x) + x + 1)E_{123}^{1}(x),

and thus

E_{123}^{21}(x) = \frac{\frac{d}{dx}E_{123}^{1}(x)}{P_{1}(x)} − x − 1 = \frac{\sqrt{3}}{2} tan (\frac{\sqrt{3}}{2}x + \frac{π}{6} ) − x − \frac{1}{2}.

Now we solve (8) in the way we solved Equalion (6) and get

E_{123}^{k(k−1)...1}(x) = \frac{e^{x/2}}{(k − 1)! cos (\frac{\sqrt{3}}{2}x + \frac{π}{6})} ∫_{0}^{x} e^{−t/2}t^{k−1} sin (\frac{\sqrt{3}}{2}t + \frac{π}{3} ) dt.

□

The following theorem is straightforward to prove. Theorem 9. We have E_{123}^{12...k}(x) = 0 for k ≥ 3 and

E_{123}^{12}(x) = E_{123}^{1}(x)−E_{123}^{21}(x) = \frac{\sqrt{3}}{2} \frac{e^{x/2}}{cos (\frac{\sqrt{3}}{2}x + \frac{π}{6})}−\frac{1}{2}−\frac{\sqrt{3}}{2} tan (\frac{\sqrt{3}}{2}x + \frac{π}{6} ) .

6. Avoiding 213 and beginning with k(k − 1) … 1 or 12 … k

If k = 1, then by [ElizNoy, Theorem 4.1] or [Kit2, Theorem 12]

E_{213}^{1}(x) = \frac{1}{1 − ∫_{0}^{x} e^{−t^{2}/2} dt}.

Theorem 10. For k ≥ 2

E_{213}^{12...k}(x) = ∫_{0}^{x} ∫_{0}^{t} \frac{s^{k−2}e^{T (t)−T (s)}}{(k − 2)!(1 − ∫_{0}^{t} e^{−m^{2}/2}dm)} dsdt,

where T (x) = −x^{2}/2 + ∫_{0}^{x} \frac{e^{−t^{2}/2}}{1−∫_{0}^{t} e^{−s^{2}/2}ds} dt.

Proof. Let A_{n} denote the number of n-permutations that avoid the pattern 213 and let K_{n} denote the number of n-permutations that avoid 213 and begin with the pattern 12 … k. Let C_{n} denote the number of n-permutation that avoid 213, begin with the pattern 12 … k and end with the pattern 12 and let D_{n} denote the number of n-permutations that avoid 213 and end with the pattern 12. Also, let A(x), K(x), C(x) and D(x) denote the e.g.f. for the numbers A_{n}, K_{n}, C_{n} and D_{n} respectively.

We observe, that

D(x) = E_{132}^{12}(x) = e^{−x^{2}/2}/(1 − ∫_{0}^{x} e^{−t^{2}/2}dt) − x − 1,

since, by using the reverse and complement discussed in the next section, there are as many permutations that avoid the pattern 213 and end with the pattern 12 as those that avoid the pattern 132 and begin with the pattern 12. Also, A(x) = E_{312}^{1}(x) and K(x) = E_{213}^{12...k}(x).

Suppose now that π = σ(n + 1)τ is an (n + 1)-permutation that avoids the pattern 213 and begins with the pattern 12 … k. So σ must avoid 213, begin with 12 … k, but also end with the pattern 12 since otherwise the two rightmost letters of σ together with the letter (n+1) form the pattern 213, which is forbidden. For τ, there is only one restriction — avoidance of 213. So if |σ| = i then we can choose the letters of σ in \binom{n}{i} ways, which gives ∑_{i≥0} \binom{n}{i}C_{i}A_{i} permutations that avoid the pattern 213 and begin with the pattern 12 … k. Moreover, it is possible for (n + 1) to be in the kth position, in which case we choose the letters of σ in \binom{n}{k−1} ways and arrange them in increasing order. Thus

K_{n+1} = ∑_{i≥0} \binom{n}{i}C_{i}A_{n−i} + \binom{n}{k − 1}A_{n−(k−1)}.

Multiplying both sides of this equality with x^{n}/n! and summing over n, we get

(9)  K′(x) = (C(x) + \frac{x^{k−1}}{(k − 1)!}) A(x),

with the initial condition K(0) = 0.

To solve (9) we need to find C(x). Let π = σ(n + 1)τ be an (n + 1)-permutation that avoids the pattern 213, begins with the pattern 12 … k and ends with the pattern 12. Reasoning as above, σ must avoid the pattern 213, begin with the pattern 12 … k and end with the pattern 12, whereas τ must avoid 213 and end with the pattern 12. This gives ∑_{i≥0} \binom{n}{i}C_{i}D_{n−i} permutations counted by C_{n+1}. Also, the letter (n+1) can be in the kth position, which gives \binom{n}{k−1}D_{n−(k−1)} permutations, and this letter can be in the (n + 1)st position, which gives C_{n} permutations that avoid the pattern 213, begin with the pattern 12 … k and end with the pattern 12. Also, if n + 1 = k and all the letters are arranged in increasing order, then (n + 1) is in the (n + 1)st position, but this permutation is not counted by C_{n} above. So

C_{n+1} = ∑_{i≥0} \binom{n}{i}C_{i}D_{n−i} + \binom{n}{k − 1}D_{n−(k−1)} + C_{n} + δ_{n,k−1},

where δ_{n,k} is the Kronecker delta, that is,

δ_{n,k} = \{ \begin{matrix}1, & if n = k, \\ 0, & else. \end{matrix}

Multiplying both sides of the equality with x^{n}/n! and summing over n, we get

(10)  C′(x) = (D(x) + 1)C(x) + (D(x) + 1)\frac{x^{k−1}}{(k − 1)!}.

To solve (10), it is convenient to introduce the function T (x) such that T′(x) = D(x) + 1. Thus

T (x) = x + ∫_{0}^{x} D(t)dt = −x^{2}/2 + ∫_{0}^{x} \frac{e^{−t^{2}/2}}{1 − ∫_{0}^{t} e^{−s^{2}/2}ds} dt,

and we need to solve the equation

C′(x) = T′(x)C(x) + T′(x)\frac{x^{k−1}}{(k − 1)!},

with C(0) = 0.

The solution to this equation is given by

C(x) = e^{T (x)} ∫_{0}^{x} e^{−T (t)}T′(t)\frac{t^{k−1}}{(k − 1)!}dt = −\frac{x^{k−1}}{(k − 1)!}+e^{T (x)} ∫_{0}^{x} e^{−T (t)} \frac{t^{k−2}}{(k − 2)!}dt.

Now we substitute C(x) into (9) to get the desired result. □

Theorem 11. For k ≥ 2

E_{213}^{k(k−1)...1}(x) = −\frac{x^{k−1}}{(k − 1)!}+∑_{n=0}^{k−2} ∫_{0}^{x} ∫_{0}^{t_{n}} ⋯ ∫_{0}^{t_{1}} \frac{C_{k−n}(t) + δ_{n,k−2}}{1 − ∫_{0}^{t} e^{−m^{2}/2}dm}dtdt_{1} ⋯ dt_{n},

where

C_{k}(x) = e^{T (x)} ∫_{0}^{x} ∫_{0}^{t_{k−2}} ⋯ ∫_{0}^{t_{1}} e^{−T (t)} (\frac{e^{−t^{2}/2}}{1 − ∫_{0}^{t} e^{−m^{2}/2}dm} − t − 1) dtdt_{1} ⋯ dt_{k−2},

with T (x) = −x^{2}/2 + ∫_{0}^{x} \frac{e^{−t^{2}/2}}{1−∫_{0}^{t} e^{−s^{2}/2}ds} dt.

Proof. Let A_{n} denote the number of n-permutations that avoid the pattern 213 and let B_{n,k} denote the number of n-permutations that avoid 213 and begin with the pattern k(k − 1) … 1 for k ≥ 2. Let C_{n,k} denote the number of n-permutation that avoid 213, begin with k(k − 1) … 1 for k ≥ 2 and end with the pattern 12 and let D_{n} denote the number of n-permutations that avoid 213 and end with the pattern

12. Also, let A(x), B_{k}(x), C_{k}(x) and D(x) denote the e.g.f. for the numbers A_{n}, B_{n,k}, C_{n,k} and D_{n} respectively. In the proof of Theorem 10 it was shown that D(x) = e^{−x^{2}/2}/(1 − ∫_{0}^{x} e^{−t^{2}/2}dt) − x − 1 and A(x) = E_{312}^{1}(x). Moreover, B_{k}(x) = E_{213}^{k(k−1)...1}(x).

Suppose now that π = σ(n+1)τ is an (n+1)-permutation that avoids 213 and begins with the pattern k(k − 1) … 1. So σ must avoid 213, begin with k(k − 1) … 1, but also end with the pattern 12 if |σ| ≥ 2, since otherwise the two rightmost letters of σ together with the letter (n + 1) form the pattern 213 which is forbidden. For τ, there is only one restriction - avoidance of 213. So if |σ| = i then we can choose the letters of σ in \binom{n}{i} ways, which gives ∑_{i≥0} \binom{n}{i}C_{i,k}A_{i} permutations counted by B_{n+1,k}. Also, it is possible for (n + 1) to be the leftmost letter, in which case the remaining letters must form a n-permutation that avoids 213 and begins with the pattern (k − 1)(k − 2) … 1. Thus

(11)  B_{n+1,k} = ∑_{i≥0} \binom{n}{i}C_{i,k}A_{n−i} + B_{n,k−1}.

However, this formula is not valid when k = 2 and n = 0. Indeed, since B_{0,1} = A_{0} = 1, it follows from the formula that B_{1,2} = 1, which is not true, since B_{1,2} must be 0. So, in the right-hand side of (11), we need to subtract the term

γ_{n,k} = \{ \begin{matrix}1, & if n = 0 and k = 2, \\ 0, & else. \end{matrix}

Multiplying both sides of the obtained equality by x^{n}/n! and summing over n, we get, that for k ≥ 3

(12)  \frac{d}{dx}B_{k}(x) = C_{k}(x)A(x) + B_{k−1}(x),

with the initial condition B_{k}(0) = 0, and

(13)  \frac{d}{dx}B_{2}(x) = C_{2}(x)A(x) + B_{1}(x) − 1,

with the initial condition B_{2}(0) = 0.

The solution to differential equations (12) and (13) is given by

B_{k}(x) = −\frac{x^{k−1}}{(k − 1)!} + ∑_{n=0}^{k−2} ∫_{0}^{x} ∫_{0}^{t_{n}} ⋯ ∫_{0}^{t_{1}} \frac{C_{k−n}(t) + δ_{n,k−2}}{1 − ∫_{0}^{t} e^{−m^{2}/2}dm}dtdt_{1} ⋯ dt_{n}.

So, to prove the theorem, we only need to find C_{k}(x).

Suppose π = σ(n + 1)τ be an (n + 1)-permutation that avoids the pattern 213, begins with the pattern k(k − 1) … 1 and ends with the pattern 12. It is clear that σ must avoid 213, begin with the pattern k(k − 1) … 1 and end with the pattern 12, whereas τ must avoid 213 and end with the pattern 12. There are ∑_{i≥0} \binom{n}{i}C_{i,k}D_{n−i} permutations with these properties. Also, the letter (n + 1) can be in the leftmost position, which gives C_{n,k−1} permutations, and (n + 1) can be in the rightmost position, which gives C_{n,k} permutations, since in this case, two letters immediately to the left of (n + 1) cannot form a descent. So,

C_{n+1,k} = ∑_{i≥0} \binom{n}{i}C_{i,k}D_{n−i} + C_{n,k−1} + C_{n,k}.

Multiplying both sides of the equality with x^{n}/n! and summing over n, we get the following differential equation

(14)  C′_{k}(x) = (D(x) + 1)C_{k}(x) + C_{k−1}(x).

As when solving Equation (10), it is convenient to introduce the function T (x) such that T′(x) = D(x) + 1. Moreover, Equation (14) is similar to Equation (3) and we can solve it in the same way. Also we observe that from the definitions, C_{1}(t) = D(t), and thus

C_{k}(x) = e^{T (x)} ∫_{0}^{x} ∫_{0}^{t_{k−2}} ⋯ ∫_{0}^{t_{1}} e^{−T (t)}C_{1}(t)dtdt_{1} ⋯ dt_{k−2} =

e^{T (x)} ∫_{0}^{x} ∫_{0}^{t_{k−2}} ⋯ ∫_{0}^{t_{1}} e^{−T (t)} (\frac{e^{−t^{2}/2}}{1 − ∫_{0}^{t} e^{−m^{2}/2}dm} − t − 1) dtdt_{1} ⋯ dt_{k−2}.

□

7. Summarizing the results from sections 4,5 and 6

We recall that the reverse R(π) of a permutation π = a_{1}a_{2} … a_{n} is the permutation a_{n}a_{n−1} … a_{1} and 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. We call these bijections of S_{n} to itself trivial. Let ϕ be an arbitrary trivial bijection. It is easy to see that, for example, there are as many permutations avoiding the pattern 132 as those avoiding the pattern ϕ(132). Moreover if, for instance, a permutation π begins with a decreasing pattern of length k, then depending on ϕ, ϕ(π) either begins with an increasing pattern, or ends with either a decreasing or increasing pattern of length k. This allows us to apply Theorems 6 – 11 to a number of other cases. We summarize all the obtained results concerning avoidance of a generalized 3-pattern with no dashes and beginning or ending with either increasing or decreasing subword, in the table below.

Remark 12. Usually, in the papers on forbidden patterns in permutations one deals with one more trivial bijection, namely the operation of permutation inverse, which is defined in the classical sense. However, this operation is not extended to generalized patterns in the way R and C do. For instance, the permutation π = 25143 avoids the generalized pattern τ = 321, whereas the inverse π^{−1} = 31542 does not avoid τ^{−1} = 321. So, in this paper the possible symmetries have been reduced from 8 to 4.

avoid begin end  e.g.f.
123 12 … k  –
1 123  –  12 … k  \frac{\sqrt{3}}{2} \frac{e^{x/2}}{cos( \frac{\sqrt{3}}{2} x+ \frac{π}{6} )}, if k = 1
321 k … 21  –  \frac{\sqrt{3}}{2} \frac{e^{x/2}}{cos( \frac{\sqrt{3}}{2} x+ \frac{π}{6} )} − \frac{1}{2} − \frac{\sqrt{3}}{2} tan(\frac{\sqrt{3}}{2}x + \frac{π}{6}), if k = 2
321  –  k … 21  0, if k ≥ 3
123 k … 21  –
2 123  –  k … 21  \frac{\sqrt{3}}{2} \frac{e^{x/2}}{cos( \frac{\sqrt{3}}{2} x+ \frac{π}{6} )}, if k = 1
321 12 … k  –
321  –  12 … k  \frac{e^{x/2} ∫_{0}^{x} e^{−t/2}t^{k−1} sin( \frac{\sqrt{3}}{2} t+ \frac{π}{6} )) dt}{(k−1)! cos( \frac{\sqrt{3}}{2} x+ \frac{π}{6} )}, if k ≥ 2
132 12 … k  –
3 213  –  12 … k  (1 − ∫_{0}^{x} e^{−t^{2}/2} dt)^{−1}, if k = 1
312 k … 21  –  e^{−x^{2}/2}(1 − ∫_{0}^{x} e^{−t^{2}/2} dt)^{−1} − x − 1, if k = 2
231  –  k … 21  (1 − ∫_{0}^{x} e^{−t^{2}/2} dt)^{−1} ∫_{0}^{x} ∫_{0}^{t_{k−2}} ⋯ ∫_{0}^{t_{2}}(e^{−t_{1}^{2}/2}−

(t_{1} + 1)(1 − ∫_{0}^{t_{1}} e^{−t^{2}/2} dt))dt_{1}dt_{2} ⋯ dt_{k−2}, if k ≥ 3

132 k … 21  –
4 213  –  k … 21  (1 − ∫_{0}^{x} e^{−t^{2}/2} dt)^{−1}, if k = 1
312 12 … k  –  _{\frac{1}{(k−1)!(1−∫_{0}^{x} e^{−t^{2}/2} dt)}} ∫_{0}^{x} t^{k−1}e^{−t^{2}/2} dt, if k ≥ 2
231  –  12 … k
213 12 … k  –  (1 − ∫_{0}^{x} e^{−t^{2}/2} dt)^{−1}, if k = 1
5 132  –  12 … k
231 k … 21  –  ∫_{0}^{x} ∫_{0}^{t} \frac{s^{k−2}e^{T (t)−T (s)}}{(k−2)!(1−∫_{0}^{t} e^{−m^{2}/2}dm)} dsdt , if k ≥ 2, where
312  –  k … 21  T (x) = −x^{2}/2 + ∫_{0}^{x} \frac{e^{−t^{2}/2}}{1−∫_{0}^{t} e^{−s^{2}/2}ds} dt
213 k … 21  –  (1 − ∫_{0}^{x} e^{−t^{2}/2} dt)^{−1}, if k = 1

6 132  –  k … 21 −\frac{x^{k−1}}{(k−1)!} + ∑_{n=0}^{k−2}∫_{0}^{x} ∫_{0}^{t_{n}} ⋯ ∫_{0}^{t_{1}} \frac{C_{k−n}(t)+δ_{n,k−2}}{1−∫_{0}^{t} e^{−m^{2}/2}dm}dtdt_{1} ⋯ dt_{n},
231 12 … k  –  if k ≥ 2, where C_{k}(x) = e^{T (x)} ∫_{0}^{x} ∫_{0}^{t_{k−2}} ⋯ ∫_{0}^{t_{1}} e^{−T (t)}·
312  –  12 … k (\frac{e^{−t^{2}/2}}{1−∫_{0}^{t} e^{−m^{2}/2}dm} − t − 1) dtdt_{1} ⋯ dt_{k−2} and T (x) as above

References

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

[Bon] 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.

[Claes] A. Claesson: Generalised Pattern Avoidance, European J. Combin. 22 (2001), 961-971.

[ClaesMans] A. Claesson and T. Mansour: Permutations avoiding a pair of gener-

alized patterns of length three with exactly one dash, preprint CO/0107044.

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

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

[Kit2] S. Kitaev: Partially ordered generalized patterns, to appear in Discrete Mathematics.

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

[Loth] M. Lothaire: Combinatorics on Words, Encyclopedia of Mathematics and its Applications, 17, Addison-Wesley Publishing Co., Reading, Mass. (1983).

[Mans1] T. Mansour: Continued fractions and generalized patterns, European J. Combin., to appear (2002), math.CO/0110037.

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

[SloPlo] N. J. A. Sloane and S. Plouffe: The Encyclopedia of Integer Sequences,

Academic Press, (1995). http://www.research.att.com/~njas/sequences/

[Stan] R. Stanley: Enumerative Combinatorics, Volume 1, Cambridge University Press, (1997).

[SchSim] R. Simion, F. Schmidt: Restricted permutations, European J. Combin. 6

(1985), no. 4, 383–406.

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

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