PARTIALLY ORDERED GENERALIZED PATTERNS

SERGEY KITAEV

Abstract. We introduce partially ordered generalized patterns (POGPs), which further generalize the generalized permutation patterns (GPs) introduced by Babson and Steingrímsson [BabStein]. A POGP p is a GP some of whose letters are incomparable. Thus, in an occurrence of p in a permutation π, two letters that are incomparable in p pose no restrictions on the corresponding letters in π. We describe many relations between POGPs and GPs and give general theorems about the number of permutations avoiding certain classes of POGPs. These theorems have several known results as corollaries but also give many new results. We also give the generating function for the entire distribution of the maximum number of non-overlapping occurrences of a pattern p with no dashes, provided we know the e.g.f. for the number of permutations that avoid p.

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.

We will be concerned with patterns in permutations. 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 don’t 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 41352 has only one occurrence of the pattern 1 − 2 − 3, namely the subword 135.

Note that a classical pattern should, in our notation, have dashes at the beginning and end. Since all patterns considered in this paper satisfy this, we suppress these dashes from the notation. Thus, a pattern with no dashes corresponds to a contiguous subword anywhere in a permutation.

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. 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 in [Claes]. Relations to several well studied combinatorial structures, such as set partitions, Dyck paths, Motzkin paths and involutions, were shown there. In [Kit] the present author investigated simultaneous avoidance of two or more 3-letter GPs with no dashes. This work is of particular interest here since avoidance of the patterns considered in this paper has a close connection to simultaneous avoidance of two or more GPs with no dashes. Also important here is the work of Elizalde and Noy [ElizNoy] where they find the distribution of several patterns with no dashes.

In this paper we introduce a further generalization of GPs — namely partially ordered generalized patterns (POGP). A POGP is a GP some of whose letters are incomparable. For instance, if we write p = 1 − 1′2′ then we mean that in an occurrence of p in a permutation π the letter corresponding to the 1 in p can be either larger or smaller than the letters corresponding to 1′2′. Thus, the permutation 13425 has four occurrences of p, namely 134, 125, 325 and 425.

We consider two particular classes of POGPs — shuffle patterns and multi-patterns. A multipattern is of the form p = σ_{1} − σ_{2} − ⋯ − σ_{k} and a shuffle pattern is of the form p = σ_{0} − a_{1} − σ_{1} − a_{2} − ⋯ − a_{k} − σ_{k}, where for any i and j, the letter a_{i} is greater than any letter of σ_{j} and for any i ≠ j each letter of σ_{i} is incomparable with any letter of σ_{j} These patterns are investigated in Sections 4 and 5. A corollary to one of our theorems (Theorem 13) about the shuffle patterns is the result of Claesson [Claes, Proposition 2] that the number of n-permutations that avoid the pattern 12 − 3 is the n-th Bell number.

Let p = σ_{1}−σ_{2}−⋯−σ_{k} be an arbitrary multi-pattern and let A_{i}(x) be the exponential generating function (e.g.f.) for the number of permutations that avoid σ_{i} for each i. In Theorem 28 we find the e.g.f., in terms of the A_{i}(x), for the number of permutations that avoid p. In particular, this allows us to find the e.g.f. for the entire distribution of the maximum number of non-overlapping occurrences of a pattern p with no dashes, if we only know the e.g.f. for the number of permutations that avoid p. In many cases, this gives nice generating functions.

We also give alternative proofs, using inclusion-exclusion, of some of the results of Elizalde and Noy [ElizNoy]. Our proofs result in explicit formulas for the e.g.f. in terms of infinite series whereas Elizalde and Noy obtained differential equations for the same e.g.f..

2. Definitions and Preliminaries

A partially ordered generalized pattern (POGP) is a GP where some of the letters can be incomparable. Example 1. The simplest non-trivial example of a POGP that differs from the ordinary GPs is p = 1′ − 2 − 1′′, where the second letter is the greatest one and the first and the last letters are incomparable to each other. The permutation 3142 has two occurrences of p, namely, the subwords 342 and 142.

It is easy to see that the number of permutations that avoid p in Example 1 is equal to 2^{n−1}. Indeed, if π = a_{1} … a_{n} and a_{i} is the leftmost letter in π that is smaller than its successor, then all letters to the right of a_{i} must be in increasing order. So any permutation π avoiding p can be written as π_{1}1π_{2} , where π_{1} is decreasing and π_{2} is increasing and there are 2^{n−1} ways to pick the permutation π_{1}, which determines π. Definition 2. If the number of permutations in S_{n}, for each n, that avoid a POGP p is equal to the number of permutations that avoid a POGP q, then p and q are said to be equivalent and we write p ≡ q in this case.

If A_{n} is the number of n-permutations that avoid a pattern p, then the exponential generating function, or e.g.f., of the class of such permutations is

A(x) = ∑_{n≥0} A_{n} \frac{x^{n}}{n!} .

We will talk about bivariate generating functions, or b.g.f., exclusively as generating functions of the form

A(u, x) = ∑_{π} u^{p(π)} \frac{x^{|π|}}{|π|!} = ∑_{n,k≥0} A_{n,k}u^{k} \frac{x^{n}}{n!} ,

were A_{n,k} is the number of n-permutations with k occurrences of the pattern p.

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 any pattern p is equivalent to 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 patterns 231, 312 and 213, respectively.

It is convenient to introduce the following definition. Definition 3. Let p be a GP without internal dashes. A permutation π quasi-avoids p if π has exactly one occurrence of p and this occurrence consists of the |p| rightmost letters of π.

For example, the permutation 51342 quasi-avoids the pattern p = 231, whereas the permutations 54312 and 45231 do not. Indeed, 54312 ends with 312, which is not an occurrence of the pattern p, and 45231 has an occurrence of p, namely 452, in a forbidden place.

Proposition 4. Let p be a non-empty GP with no dashes. Let A(x) (resp. A^{⋆}(x)) be the e.g.f. for the number of permutations that avoid (resp. quasi-avoid) p. Then

A^{⋆}(x) = (x − 1)A(x) + 1.

Proof. We first show that

(1)  A_{n}^{⋆} = nA_{n−1} − A_{n}.

If we consider all (n − 1)-permutations that avoid p and all possible extending of these permutations to the n-permutations by writing one more letter to the right, then the number of obtained permutations will be nA_{n−1}. Obviously, the set of these permutations is a disjoint union of the set of all n-permutations that avoid p and the set of all n-permutations that quasi-avoid p. Thus we get (1). Multiplying both sides of (1) with x^{n}/n! and summing over all natural numbers n, observing that A_{0}^{⋆} = 0, we get the desired result. □

Definition 5. Suppose {σ_{0}, σ_{1}, …, σ_{k}} is a set of GPs with no dashes and p = σ_{1} − σ_{2} − ⋯ − σ_{k} where each letter of σ_{i} is incomparable with any letter of σ_{j} whenever i ≠ j. We call such POGPs multi-patterns.

Definition 6. Suppose {σ_{0}, σ_{1}, …, σ_{k}} is a set of GPs with no dashes and a_{1}a_{2} … a_{k} is a permutation of k letters. We define a shuffle pattern to be a pattern of the form

σ_{0} − a_{1} − σ_{1} − a_{2} − ⋯ − σ_{k−1} − a_{k} − σ_{k},

where for any i and j, the letter a_{i} is greater than any letter of σ_{j} and for any i ≠ j each letter of σ_{i} is incomparable with any letter of σ_{j}. We also allow σ_{0} and σ_{k}, but not the other σ_{i}, to be empty patterns.

The pattern from Example 1 is an example of a shuffle pattern. It follows from the definitions that we can get a multi-pattern from a shuffle pattern by removing all the a_{i}.

Let S_{∞} denote the disjoint union of the S_{n} for all n ∈ ℕ. The POGPs (which include the GPs, as well as the classical patterns), can be considered as functions from S_{∞} to ℕ that count the number of occurrences of the pattern in a permutation in S_{∞}. This allows us to write a POGP (as a function) as a linear combination of GPs. For example,

1′ − 2 − 1′′ = (1 − 3 − 2) + (2 − 3 − 1),

from which, in particular, we see that to avoid 1′ − 2 − 1′′ is the same as to avoid simultaneously the patterns 1 − 3 − 2 and 2 − 3 − 1. A straightforward argument leads to the following proposition.

Proposition 7. For any POGP p there exists a set S of GPs such that a permutation π avoids p if and only if π avoids all the patterns in S.

The following theorem can be easily proved by induction on k:

Theorem 8. Let p_{1} = σ_{0} − a_{1} − σ_{1} − a_{2} − ⋯ − σ_{k−1} − a_{k} − σ_{k} (resp. p_{2} = σ_{0} − σ_{1} − ⋯ − σ_{k}) be an arbitrary shuffle pattern (resp. multi-pattern) with |σ_{i}| = ℓ_{i} for all i = 0, …, k. Then to avoid the pattern p_{1} (resp. p_{2}) is the same as to avoid

∏_{i=1}^{k} \binom{ℓ_{0} + ℓ_{1} + ⋯ + ℓ_{i}}{ℓ_{i}} = \binom{ℓ_{0} + ℓ_{1}}{ℓ_{1}}\binom{ℓ_{0} + ℓ_{1} + ℓ_{2}}{ℓ_{2}} ⋯ \binom{ℓ_{0} + ℓ_{1} + ⋯ + ℓ_{k}}{ℓ_{k}}

ordinary GPs.

Example 9. Let p = 1′2′ − 3 − 1′′. That is σ = 12 and τ = 1. By Theorem 8, to avoid p is the same as to avoid \binom{3}{2} = 3 GPs simultaneously, namely 12 − 4 − 3, 13 − 4 − 2 and 23 − 4 − 1.

There is a number of results on the distribution of several classes of patterns with no dashes. These results can be used as building blocks for some of the results in the present paper. The most important of these is the following result by Elizalde and Noy [ElizNoy]:

Theorem 10. [ElizNoy, Theorem 3.4] Let m and a be positive integers with a ≤ m, let σ = 12 … aτ(a + 1) ∈ S_{m+2}, where τ is any permutation of {a + 2, a + 3, …, m + 2}, and let P (u, z) be the b.g.f. for permutations where u marks the number of occurrences of σ. Then P (u, z) = 1/w(u, z), where w is the solution of

w^{a+1} + (1 − u)\frac{z^{m−a+1}}{(m − a + 1)!}w′ = 0

with w(0) = 1, w′(0) = −1 and w^{(k)}(0) = 0 for 2 ≤ k ≤ a. In particular, the distribution does not depend on τ.

3. GPs with no dashes

In order to apply our results in what follows we need to know how many patterns avoid a given ordinary GP with no dashes. We are also interested in different approaches to studying these patterns. The theorems in this section can be proved using an inclusion-exclusion argument similar to the one given in the proof of Theorem 30 and we omit these proofs. This allows us to get explicit formulas for the e.g.f. in terms of infinite series instead of having to solve differential equations as done by Elizalde and Noy [ElizNoy] for the same e.g.f.. However, in particular cases, we use certain differential equations to simplify our series.

Theorem 11. [GoulJack] Let A_{k}(x) be the e.g.f. for the number of permutations avoiding the pattern p = 123 … k. Then

A_{k}(x) = 1/F_{k}(x),

where F_{k}(x) = ∑_{i≥0} \frac{x^{ki}}{(ki)!} − ∑_{i≥0} \frac{x^{ki+1}}{(ki + 1)!}.

For some k it is possible to simplify the function F_{k}(x) in the theorems above. Indeed, F_{k}(x) satisfies the differential equation F_{k}^{(k)}(x) = F_{k}(x) with the k initial conditions F_{k}(0) = 1, F′_{k}(0) = −1 and F_{k}^{(i)}(0) = 0 for all i = 2, 3, …, k − 1. For instance, if k = 4 then

F_{4}(x) = \frac{1}{2}(cos x − sin x + e^{−x}).

Theorem 12. Let k and a be positive integers with a < k, let p = 12 … aτ(a + 1) ∈ S_{k+1}, where τ is any permutation of the elements {a + 2, a + 3, …, k + 1}, and let A_{k,a}(x) be the e.g.f. for the number of permutations that avoid p. Let

F_{k,a}(x) = ∑_{i≥1} \frac{(−1)^{i+1}x^{ki+1}}{(ki + 1)!} ∏_{j=2}^{i} \binom{jk − a}{k − a}.

Then

A_{k,a}(x) = 1/(1 − x + F_{k,a}(x)).

If k = 2 and a = 1 in the previous theorem, corresponding to the pattern p = 132, then from Theorem 12 the function F_{2,1}(x), which is the same for the patterns p, 231, 312 and 213 because of the trivial bijections, can be written as:

F_{2,1}(x) = ∑_{i≥1} \frac{(−1)^{i+1}x^{ki+1}}{i!(k!)^{i}(ki + 1)} = x − ∫_{0}^{x} e^{−t^{2}/2} dt.

That is

A_{2,1} = \frac{1}{1 − ∫_{0}^{x} e^{−t^{2}/2} dt},

which is a special case of Theorem 4.1 in [ElizNoy].

4. The Shuffle Patterns

We recall that according to Definition 6, a shuffle pattern is a pattern of the form σ_{0} − a_{1} − σ_{1} − a_{2} − ⋯ − σ_{k−1} − a_{k} − σ_{k}, where {σ_{0}, σ_{1}, …, σ_{k}} is a set of GPs with no dashes, a_{1}a_{2} … a_{k} is a permutation of k letters, for any i and j the letter a_{i} is greater than any letter of σ_{j} and for any i ≠ j each letter of σ_{i} is incomparable with any letter of σ_{j}.

Let us consider a shuffle pattern that in fact is an ordinary generalized pattern. This pattern is p = σ − k, where σ is an arbitrary pattern with no dashes that is built on elements 1, 2, …, k − 1. So the last element of p is greater than any other element. Theorem 13. Let p = σ − k and let A(x) (resp. B(x)) be the e.g.f. for the number of permutations that avoid σ (resp. p). Then B(x) = e^{F (x,A(y))}, where

F (x, A(y)) = ∫_{0}^{x} A(y) dy.

Proof. Suppose that π ∈ S_{n+1} and that π avoids p. Suppose the letter (n + 1) is in the i-th position and π = π_{1}(n + 1)π_{2}, where π_{1} and π_{2} might be empty.

Since π is p-avoiding, π_{1} must be σ-avoiding, because otherwise an occurrence of σ in π_{1} together with the letter (n + 1) gives an occurrence of p in π. But if π_{1} is σ-avoiding then there is no interaction between π_{1} and π_{2}, that is, if π_{2} is p-avoiding and π_{1} is σ-avoiding then π is p-avoiding. To see this it is enough to see that if an occurrence of σ in π contains the letter (n + 1), then this occurrence of σ can not lead to an occurrence of p = σ − k containing the letter (n + 1).

From the above, considering all possible positions of (n + 1), we get the recurrence relation

B_{n+1} = ∑_{i} \binom{n}{i}A_{i}B_{n−i},

where B_{j} (resp. A_{j}) is the number of j-permutations that avoid p (resp. σ), because we can choose the elements of π_{1} in \binom{n}{i} ways.

Multiplying both sides of the equality by x^{n}/n! we get

\frac{B_{n+1}}{n!} x^{n} = ∑_{i} \frac{A_{i}}{i!} x^{i} \frac{B_{n−i}}{(n − i)!}x^{n−i}.

Taking the sum over all natural numbers n leads us to

B′(x) = A(x)B(x)

where the derivative of B is with respect to x. Since B(0) = 1, the solution of the differential equation is B(x) = e^{F (x,A(y))}. □

Example 14. Let p = 1 − 2. Here σ = 1, so A(x) = 1 since A_{n} = 0 for all n ≥ 1 and A_{0} = 1. So

B(x) = e^{F (x,1)} = e^{x}.

This corresponds to the fact that for each n ≥ 1 there is exactly one permutation that avoids the pattern p, namely π = n(n − 1) … 1. Example 15. Suppose p = 12−3. Here σ = 12, so A(x) = e^{x}, since there is exactly one permutation that avoids the pattern σ. So

B(x) = ∑_{n≥0} \frac{B_{n}}{n!} x^{n} = e^{F (x,e^{y})} = e^{e^{x}−1}.

According to [Claes, Proposition 2], for all n ≥ 1, B_{n} is the n-th Bell number and the e.g.f. for the Bell numbers is e^{e^{x}−1}.

The table below gives the initial values of B_{n} for several patterns p = σ − k. These numbers were obtained by expanding the corresponding B(x). The functions A(x) are taken from the previous section.

pattern  initial values for B_{n}
132-4 1, 2, 6, 23, 107, 585, 3671, 25986, 204738
123-4 1, 2, 6, 23, 108, 598, 3815, 27532, 221708
1234-5 1, 2, 6, 24, 119, 705, 4853, 38142, 336291
12345-6 1, 2, 6, 24, 120, 719, 5022, 40064, 359400

Theorem 16. Let p be the shuffle pattern σ − k − τ. So k is the greatest letter of the pattern, and each letter of σ is incomparable with any letter of τ. Let A(x), B(x) and C(x) be the e.g.f. for the number of permutations that avoid σ, τ and p respectively. Then C(x) is the solution of the differential equation

C′(x) = (A(x) + B(x))C(x) − A(x)B(x),

with C(0) = 1.

Proof. As before, we consider the symmetric group S_{n+1} and a permutation π ∈ S_{n+1} that avoids p. Suppose the letter (n + 1) is in the i-th position and π = π_{1}(n + 1)π_{2}, where π_{1} and π_{2} might be empty.

There are exactly four mutually exclusive possibilities:

1) π_{1} does not avoid σ, π_{2} does not avoid τ.

2) π_{1} avoids σ, π_{2} does not avoid τ;

3) π_{1} does not avoid σ, π_{2} avoids τ;

4) π_{1} avoids σ, π_{2} avoids τ; Obviously, the situation 1) is impossible, since an occurrence of σ in π_{1} with (n + 1) and with

an occurrence of τ in π_{2} gives us an occurrence of p in π. On the other hand, if p occurs in π then it is easy to see that the letter (n + 1) cannot be one of the letters in the occurrences of σ or τ, so all p-avoiding permutations are described by the possibilities 2)–4). We count these permutations in the following way.

In \binom{n}{i} ways we choose first i elements from the letters 1, 2 … n, that is, the elements of π_{1}. Let A_{i}, B_{i} and C_{i} be the number of i-permutations that avoid σ, τ and p respectively.

If π_{1} is σ-avoiding, we let π_{2} be any p-avoiding permutation of the remaining (n − i + 1) letters. This accounts for all ”good” permutations from the possibilities 2) and 4). There are \binom{n}{i}A_{i}C_{n−i} such permutations.

If π_{2} is τ-avoiding, we let π_{1} be any p-avoiding permutation of chosen i letters. This covers all “good” permutations from 3) and 4). There are \binom{n}{i}B_{i}C_{n−i} such permutations.

But we have counted p-avoiding permutations that correspond to 4) twice, so we must subtract \binom{n}{i}A_{i}B_{n−i}, which is the number of such permutations.

So we have

C_{n+1} = ∑_{i} \binom{n}{i}(A_{i}C_{n−i} + B_{i}C_{n−i} − A_{i}B_{n−i}).

Multiplying both sides of the equality by x^{n}/n! we get

\frac{C_{n+1}}{n!} x^{n} = ∑_{i} (\frac{A_{i} + B_{i}}{i!} x^{i} \frac{C_{n−i}}{(n − i)!}x^{n−i} − \frac{A_{i}}{i!} x^{i} \frac{B_{n−i}}{(n − i)!}x^{n−i}) ,

so

C′(x) = (A(x) + B(x))C(x) − A(x)B(x).
□

Example 17. Let p = 1′ − 2 − 1′′. That is, σ = 1 and τ = 1. So A(x) = B(x) = 1 and we need to solve the equation

C′(x) = 2C(x) − 1

with C(0) = 1. The solution of this equation is C(x) = \frac{1}{2}(e^{2x} + 1), so for all n ≥ 1 we have C_{n} = 2^{n−1}, as in Example 1.

In the table below we record the initial values of C_{n} for several patterns p = σ − k − τ.

σ  τ  initial values for C_{n}
1  12  1, 2, 6, 21, 82, 354, 1671, 8536, 46814
1 132 1, 2, 6, 24, 116, 652, 4178, 30070, 240164
1 123 1, 2, 6, 24, 116, 657, 4260, 31144, 253400
1 1234 1, 2, 6, 24, 120, 715, 4946, 38963, 344350
12 12 1, 2, 6, 24, 114, 608, 3554, 22480, 152546
12 132 1, 2, 6, 24, 120, 710, 4800, 36298, 302780
12 123 1, 2, 6, 24, 120, 710, 4815, 36650, 308778
12 1234 1, 2, 6, 24, 120, 720, 5025, 39926, 355538
123 123 1, 2, 6, 24, 120, 720, 5020, 39790, 352470
123 132 1, 2, 6, 24, 120, 720, 5020, 39755, 351518
132 132 1, 2, 6, 24, 120, 720, 5020, 39720, 350496

Remark 18. The pattern p = σ−k from Theorem 13 is a particular case of the pattern p = σ−k−τ from Theorem 16 when τ is the empty word. The e.g.f. for the number of permutations that avoid the empty word is zero, because no permutation avoids the empty word. So if τ is empty, we can use Theorem 16 to get Theorem 13. Indeed, B(x) = 0, and after renaming C with B we get in Theorem 16 exactly the same differential equation as we have in Theorem 13.

We now give two corollaries to Theorem 16. Corollary 19. Suppose we have the shuffle pattern p = σ − k − τ. We consider the pattern φ(p) = φ_{1}(σ) − k − φ_{2}(τ), where φ_{1} and φ_{2} are any trivial bijections. Then p ≡ φ(p).

Proof. We just observe that if A(x) (resp. B(x)) is the e.g.f. for the number of permutations that avoid σ (resp. τ) then A(x) (resp. B(x)) is the e.g.f. for the number of permutations that avoid φ_{1}(σ) (resp. φ_{2}(τ)). □

Corollary 20. We have σ − k − τ ≡ τ − k − σ.

Proof. This follows directly from the differential equation of Theorem 16 (A(x) and B(x) are symmetric in that equation), but we can also obtain this as a corollary to Corollary 19. By Corollary 19, the pattern σ − k − τ is equivalent to the pattern σ − k − R(τ). Reversing the pattern σ − k − R(τ), we obtain the pattern

R(σ − k − R(τ)) = R(R(τ)) − k − R(σ) = τ − k − R(σ),

which thus is equivalent to σ − k − τ. Finally, we use Corollary 19 one more time to get

τ − k − R(σ) ≡ τ − k − R(R(σ)) = τ − k − σ.
□

5. The Multi-Patterns

We recall that according to Definition 5, a multi-pattern is a pattern p = σ_{1} − σ_{2} − ⋯ − σ_{k}, where {σ_{0}, σ_{1}, …, σ_{k}} is a set of GPs with no dashes and each letter of σ_{i} is incomparable with any letter of σ_{j} whenever i ≠ j.

We first discuss patterns of the type p = σ − τ which are a particular case of the multi-patterns to be treated in this section.

If σ or τ is the empty word then we are dealing with ordinary GPs with no dashes, some of which were investigated in [ElizNoy] and Section 3. The analysis of the case when σ or τ is equal to 1 can also be reduced to the analysis of ordinary GPs. For example, suppose that σ = 1, that is, p = 1−τ, and we want to count the number of permutations in S_{n} that avoid p. We can choose the leftmost letter of a permutation avoiding p in n ways, then the remainder of the permutation must avoid τ, so we multiply n by the number of permutations in S_{n−1} that avoid τ. For instance, if p = 1 − 1′2′ then the number of permutations in S_{n} avoiding p is exactly n. Theorem 21. Let p = σ − τ and q = φ_{1}(σ) − φ_{2}(τ), where φ_{1} and φ_{2} are any of the trivial bijections. Then p and q are equivalent.

Proof. The theorem is equivalent to the following statement:

Let p = σ − τ and q = σ − φ(τ), where φ is a trivial bijection. Then p and q are equivalent. It is obvious that the statement follows from Theorem 21. Conversely, suppose we have p = σ −τ.

We observe that any two trivial bijections commute, that is for any trivial bijection ψ, we have ψ(R(x)) = R(ψ(x)). This observation, the statement and the fact that x ≡ R(x) give

p = σ − τ ≡ σ − φ_{2}(τ) ≡ R(φ_{2}(τ)) − R(σ) ≡ R(φ_{2}(τ)) − φ_{1}(R(σ)) ≡
R(φ_{2}(τ)) − R(φ_{1}(σ)) ≡ φ_{1}(σ) − φ_{2}(τ).

So to prove the theorem we now prove the statement.

Let p = σ − τ and q = σ − φ(τ), where φ is a trivial bijection. Let A_{n} (resp. B_{n}) be the number of n-permutations that avoid p (resp. q). We are going to prove that A_{n} = B_{n}.

Suppose π avoids p and π = π_{1}σ′π_{2}, where π_{1}σ′ has exactly one occurrence of the pattern σ, namely σ′. Then π_{2} must avoid τ, φ(π_{2}) must avoid φ(τ) and π_{φ} = π_{1}σ′φ(π_{2}) avoids q. The converse is also true, that is, if π_{φ} has no occurrences of q then π has no occurrences of p. If π has no occurrences of σ then π has no occurrences of p as well as no occurrences of q. Since any permutation either avoids σ or can be factored as above, we have a bijection between the class of permutations that avoid p and the class of permutations that avoid q. Thus A_{n} = B_{n}. □

We get the following corollary to Theorem 21: Corollary 22. The pattern σ − τ is equivalent to the pattern τ − σ.

Proof. We proceed as in the proof of Corollary 20. From Theorem 21 we have:

σ − τ ≡ σ − R(τ) ≡ R(R(τ)) − R(σ) ≡ τ − R(R(σ)) ≡ τ − σ.
□

We observe that the presence of the dash in the patterns in Theorem 21 is essential. That is, generally speaking, the pattern στ is not equivalent to the pattern φ_{1}(σ)φ_{2}(τ) for any trivial bijections φ_{1} and φ_{2}. For example, there are 66 permutations in S_{5} that avoid the pattern 122′1′ but only 61 that avoid 121′2′. In Section 6 we investigate the pattern 122′1′.

Theorem 23 and Corollary 24 generalise Theorem 21 and Corollary 22: Theorem 23. Suppose we have multi-patterns p = σ_{1} − σ_{2} − ⋯ − σ_{k} and q = τ_{1} − τ_{2} − ⋯ − τ_{k}, where τ_{1}τ_{2} … τ_{k} is a permutation of σ_{1}σ_{2} … σ_{k}. Then p and q are equivalent.

Proof. We proceed by induction on k. If k = 2 then the statement is true by Corollary 22. Suppose the statement is true for all k′ < k. Suppose p has exactly k blocks. If a permutation π avoiding p has no occurrences of σ_{1} then it obviously avoids both p and q. Otherwise we factor π as π = π_{1}σ′_{1}π_{2} where π_{1}σ_{1}′ has exactly one occurrence of the pattern σ_{1}, namely σ_{1}′. Then π_{2} must avoid σ_{2} − ⋯ − σ_{k}. Moreover it is irrelevant from which letters π_{1}σ_{1}′ is built and therefore we can apply the inductive hypothesis. We can rearrange σ′_{2} … σ′_{k} of σ_{2} … σ_{k} in such a way that the blocks in τ_{1}τ_{2} … τ_{k} corresponding to σ_{2}, …, σ_{k} are arranged in the same order as the τ’s. Now we consider separately two cases: τ_{k} ≠ σ_{1} and τ_{k} = σ_{1}. In the first case we use the following equivalences:

p = σ_{1} − σ_{2} − ⋯ − σ_{k} ≡ σ_{1} − σ_{2}′ − ⋯ − σ′_{k} ≡ R(σ′_{k}) − ⋯ − R(σ′_{2}) − R(σ_{1}).

For the pattern R(σ′_{k}) − ⋯ − R(σ′_{2}) − R(σ_{1}) we use the factorisation of a permutation π avoiding this pattern, where the role of σ_{1} is played by R(σ′_{k}). So by the inductive hypothesis we put the pattern R(σ_{1}) in the right place somewhere to the left of R(σ′_{2}) and apply R to get that p ≡ q.

In the second case we have:

p ≡ R(σ′_{k}) − ⋯ − R(σ′_{2}) − R(σ_{1}) ≡ R(σ′_{k}) − ⋯ − R(σ_{1}) − R(σ′_{2}) ≡
σ′_{2} − σ_{1} − ⋯ − σ′_{k} ≡ σ′_{2} − ⋯ − σ′_{k} − σ_{1} = q

The first equivalence here is taken from the considerations above; the second one uses the inductive hypothesis; then we use the fact that R(R(x)) = x and apply the inductive hypothesis again. □

Corollary 24. Suppose we have multi-patterns p = σ_{1} − σ_{2} − ⋯ − σ_{k} and q = φ_{1}(σ_{1}) − φ_{2}(σ_{2}) − ⋯ − φ_{k}(σ_{k}), where each φ_{i} is an arbitrary trivial bijection. Then p and q are equivalent.

Proof. We use induction on k, Theorem 23 and the factorisation of permutations, which is discussed in the proof of Theorem 23. If k = 2 then the statement is true by Theorem 21. Suppose the statement is true for all k′ < k. Then

p = σ_{1} − σ_{2} − ⋯ − σ_{k} ≡ σ_{1} − φ_{2}(σ_{2}) − ⋯ − φ_{k}(σ_{k}) ≡
φ_{2}(σ_{2}) − σ_{1} − ⋯ − φ_{k}(σ_{k}) ≡ φ_{2}(σ_{2}) − φ_{1}(σ_{1}) − ⋯ − φ_{k}(σ_{k}) ≡
φ_{1}(σ_{1}) − φ_{2}(σ_{2}) − ⋯ − φ_{k}(σ_{k}) = q,

where first we apply the inductive hypothesis then Theorem 23 then the inductive hypothesis and finally Theorem 23 again. □

Theorem 25. Suppose p = σ − p′, where p′ is an arbitrary POGP, and the letters of σ are incomparable to the letters of p′. Let C(x) (resp. A(x), B(x)) be the e.g.f. for the number of permutations that avoid p (resp. σ, p′). Moreover let A^{⋆}(x) be the e.g.f. for the number of permutations that quasi-avoid σ. Then

C(x) = A(x) + B(x)A^{⋆}(x).

Proof. Let A_{n}, B_{n}, C_{n} be the number of n-permutations that avoid the patterns σ, p′ and p respectively. Also A_{n}^{⋆} is the number of n-permutations that quasi-avoid σ. If a permutation π avoids σ then it avoids p. Otherwise we find the leftmost occurrence of σ in π. We assume that this occurrence consists of the |σ| rightmost letters among the i leftmost letters of π. So the subword of π beginning at the (i + 1)st letter must avoid p′. From this we conclude

C_{n} = A_{n} + ∑_{i=|σ|}^{n} \binom{n}{i}A_{i}^{⋆}B_{n−i}.

We observe that we can change the lower bound in the sum above to 0, because A_{i}^{⋆} = 0 for i = 0, 1, …, |σ| − 1. Multiplying both sides by x^{n}/n! and taking the sum over all n we get the desired result. □

Corollary 26. Suppose p = σ_{1} − σ_{2} − ⋯ − σ_{k} is a multi-pattern where |σ_{i}| = 2 for all i, so each σ_{i} is equal to either 12 or 21. If B(x) is the e.g.f. for the number of permutations that avoid p then

B(x) = \frac{1 − (1 + (x − 1)e^{x})^{k}}{1 − x} .

Proof. We use Theorem 25, induction on k and the fact that A(x) = e^{x} and A^{⋆}(x) = 1+(x−1)e^{x}. □

The following corollary to Corollary 26 can be proved combinatorially. Theorem 27. There are (n − 2)2^{n−1} + 2 permutations in S_{n} that avoid the pattern p = 12 − 1′2′ or, according to Theorem 21, the pattern p = 12 − 2′1′.

One more corollary to Theorem 25 is the following theorem that is the basis for calculating the number of permutations that avoid a multi-pattern, and therefore is the main result for multipatterns in this paper. Theorem 28. Let p = σ_{1} − σ_{2} − ⋯ − σ_{k} be a multi-pattern and let A_{i}(x) be the e.g.f. for the number of permutations that avoid σ_{i}. Then the e.g.f. B(x) for the number of permutations that avoid p is

B(x) = ∑_{i=1}^{k} A_{i}(x) ∏_{j=1}^{i−1}((x − 1)A_{j}(x) + 1).

Proof. We use Theorem 25 and prove by induction on k that

B(x) = ∑_{i=1}^{k} A_{i}(x) ∏_{j=1}^{i−1} A_{j}^{⋆}(x).

Then we use Proposition 4 to get the desired result. □

Remark 29. One can consider the function B(x) from Theorem 28 as a function in k variables B(x) = B(A_{1}(x), A_{2}(x), …, A_{k}(x)). Then, by Theorem 23, this function is symmetric in the variables A_{1}(x), A_{2}(x), …, A_{k}(x). That means that we can rename the variables, which may simplify the calculation of B(x).

6. Patterns of the Form στ

Theorem 30. Let B(x) be the e.g.f. for the number of permutations that avoid the pattern p = 122′1′. Then

B(x) = \frac{1}{2} + \frac{1}{4} tan x(1 + e^{2x} + 2e^{x} sin x) + \frac{1}{2}e^{x} cos x.

Proof. Let B_{n} be the number of n-permutations that avoid p and A_{n} be the number of n-permutations that avoid p and begin with the pattern 12. Let also A(x) be the e.g.f. for the numbers A_{n}. We set B_{0} = A_{0} = A_{1} = 1. Suppose π is a (n + 1)-permutation that avoids p. There are three mutually exclusive possibilities:

1) π = (n + 1)π_{2};

2) π = π_{1}(n + 1);

3) π = π_{1}(n + 1)π_{2} and π_{1}, π_{2} ≠ ε. Obviously, in 1) and 2) the letter (n + 1) does not affect the rest of the permutation π, and

therefore in each of these cases we have B_{n} permutations that avoid p. In 3), it is easy to see that if π_{1} has more than one letter then π_{1} must end with a 21 pattern whereas if π_{2} has more than one letter then π_{2} must begin with a 12 pattern. The key observation is that the number of n-permutations that avoid p and end with a 21 pattern is the same as the number of n-permutations that avoid p and begin with a 12 pattern. To see this it is enough to apply the reverse function to any n-permutation π that begins with 12-pattern and avoids p and observe that R(p) = p, that is, R(π) avoids p and ends with a 21 pattern. Obviously this is a bijection. So if |π_{1}| = i then we can choose the letters of π_{1} in \binom{n}{i} ways and then choose a permutation π_{1} in A_{i} ways and a permutation π_{2} in A_{n−i} ways, since the letters of π_{1} and π_{2} do not affect each other. From all this we get

B_{n+1} = 2B_{n} + ∑_{i=1}^{n−1} \binom{n}{i}A_{i}A_{n−i} = 2B_{n} + ∑_{i=0}^{n} \binom{n}{i}A_{i}A_{n−i} − 2A_{n}.

We multiply both sides of the last equality by x^{n}/n! to get

B_{n+1} \frac{x^{n}}{n!} = 2B_{n} \frac{x^{n}}{n!} + ∑_{i=0}^{n} \frac{A_{i}}{i!} x^{i} \frac{A_{n−i}}{(n − i)!}x^{n−i} − 2A_{n} \frac{x^{n}}{n!} .

Summing both sides over all natural numbers n we get:

(2)  B′(x) = 2B(x) + A^{2}(x) − 2A(x).

To solve this differential equation with the initial condition B(0) = 1, we need to determine A(x). One can observe that if a permutation π avoids p and begins with the pattern 12 then π has the structure π = a_{1}b_{1}a_{2}b_{2}a_{3}b_{3} ⋯, where a_{i} < b_{i} for all i. Moreover, if b_{1} < a_{2} then we must have a_{1} < b_{1} < a_{2} < b_{2} < a_{3} < ⋯ since otherwise we obviously have an occurrence of the pattern p. A first approximation is that A_{n} = \binom{n}{2}A_{n−2}, because we can choose a_{1}b_{1} in π in \binom{n}{2} ways and then pick an arbitrary (n − 2)-permutation that avoids p and begins with the pattern 12, to be a_{2}b_{2}a_{3}b_{3} …, in A_{n−2} ways. But it is possible that b_{1} < a_{2} in which case b_{1}a_{2}b_{2}a_{3} can be an occurrence of p in π, and it is an occurrence of p unless a_{2} < b_{2} < a_{3} < · · ·. So in order to avoid this we must subtract the number of permutations of the form abcdπ′, where a < b < c < d and π′ is any (n − 4)-permutation that avoids p, from the first approximation of A_{n}. Thus the second approximation is that A_{n} = \binom{n}{2}A_{n−2} − \binom{n}{4}A_{n−4}. We observe that in the second approximation we do not count the increasing permutation 123 … n. Moreover, among the permutations counted by \binom{n}{4}A_{n−4}, there are the permutations that begin with 6 increasing letters. Except for the increasing permutation, such permutations are not counted by \binom{n}{2}A_{n−2}. We must therefore add the number of such permutations. So the third approximation is that A_{n} = \binom{n}{2}A_{n−2} − \binom{n}{4}A_{n−4} + \binom{n}{6}A_{n−6} and so on. That is,

(3) A_{n} = \binom{n}{2}A_{n−2} − \binom{n}{4}A_{n−4} + \binom{n}{6}A_{n−6} − \binom{n}{8}A_{n−8} + ⋯ = ∑_{i≥1}(−1)^{i+1}\binom{n}{2i}A_{n−2i}.

We observe that if n = 4k or n = 4k + 1 then we do not count the increasing permutation in our sum. This, together with Equation 3, gives us

∑_{i≥0}(−1)^{i}\binom{n}{2i}A_{n−2i} = \{ \begin{matrix}1, & if n = 4k or n = 4k + 1, \\ 0, & if n = 4k + 2 or n = 4k + 3. \end{matrix}

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

(A_{0} + A_{1}x + \frac{A_{2}}{2!} x^{2} + ⋯)(1 − \frac{x^{2}}{2!} + \frac{x^{4}}{4!} − \frac{x^{6}}{6!} + ⋯) = ∑_{k=0}^{∞} (\frac{x^{4k}}{(4k)!} + \frac{x^{4k+1}}{(4k + 1)!}) .

The left hand side of this equality is equal to A(x) cos x. Let F (x) be the function in the right hand side of the equality. Then it is easy to see that F (x) is the solution to the differential equation F^{(4)}(x) = F (x) with the initial conditions F (0) = F′(0) = 1, F^{(2)}(0) = F^{(3)}(0) = 0. So F (x) = \frac{1}{2}(cos x + sin x + e^{x}) and

A(x) = \frac{1}{2} (1 + tan x + \frac{e^{x}}{cos x}) .

Now we solve the differential equation (2) and get

B(x) = \frac{1}{2} + \frac{1}{4} tan x(1 + e^{2x} + 2e^{x} sin x) + \frac{1}{2}e^{x} cos x.
□

Remark 31. The series expansion of B(x) in Theorem 30 begins with

B(x) = 1 + x + x^{2} + x^{3} + \frac{3}{4}x^{4} + \frac{11}{20}x^{5} + \frac{7}{20}x^{6} + \frac{7}{30}x^{7} + \frac{103}{720}x^{8} + · · · .

That is, the initial values for B_{n} are 1, 2, 6, 18, 66, 252, 1176, 5768.

7. The Distribution of Non-Overlapping GPs

A descent in a permutation π = a_{1}a_{2} … a_{n} is an i such that a_{i} > a_{i+1}. The number of descents in a permutation π is denoted des π (and is equivalent to the generalized pattern 21). Any statistic with the same distribution as des is said to be Eulerian. The Eulerian numbers A(n, k) count permutations in the symmetric group S_{n} with k descents and they are the coefficients of the Eulerian polynomials A_{n}(t) defined by A_{n}(t) = ∑_{π∈S_{n}} t^{1+des π}. The Eulerian polynomials satisfy the identity

∑_{k≥0} k^{n}t^{k} = \frac{A_{n}(t)}{(1 − t)^{n+1}} .

Two descents i and j overlap if j = i + 1. We define a new statistic, namely the maximum number of non-overlapping descents, or MND, in a permutation. For instance, MND(321) = 1 whereas MND(41532) = 2. One can find the distribution of this new statistic by using Corollary 26. This distribution is given in Example 33. However, we prove a more general theorem: Theorem 32. Let p be a GP with no dashes. Let A(x) be the e.g.f. for the number of permutations

that avoid p. Let D(x, y) = ∑_{π} y^{N(π)} \frac{x^{|π|}}{|π|!} where N(π) is the maximum number of non-overlapping

occurrences of p in π. Then

D(x, y) = \frac{A(x)}{1 − y((x − 1)A(x) + 1)}.

Proof. We fix the natural number k and consider an auxiliary multi-pattern P_{k} = p − p − ⋯ − p with k copies of p. If a permutation avoids P_{k} then it has at most k −1 non-overlapping occurrences of p. From Theorem 28, the e.g.f. B_{k}(x) for the number of permutations avoiding P_{k} is equal to

∑_{i=1}^{k} A(x) ∏_{j=1}^{i−1}((x − 1)A(x) + 1). If we subtract B_{k}(x) from the e.g.f. B_{k+1}(x) = ∑_{i=1}^{k+1} A(x) ∏_{j=1}^{i−1}((x −

1)A(x)+1) for the number of permutations avoiding P_{k+1}, which is obtained by applying Theorem 28 to the pattern P_{k+1}, then we get the e.g.f. D_{k}(x) for the number of permutations that have exactly k non-overlapping occurrences of the pattern p. So

D_{k}(x) = ∑_{n} D_{n,k} \frac{x^{n}}{n!} = B_{k+1}(x) − B_{k}(x) = A(x)((x − 1)A(x) + 1)^{k}.

Now

D(x, y) = ∑_{n,k≥0} D_{n,k}y^{k} \frac{x^{n}}{n!} = ∑_{k} D_{k}(x)y^{k} = \frac{A(x)}{1 − y((x − 1)A(x) + 1)}.

□

All of the following examples are corollaries to Theorem 32. Example 33. If we consider descents then A(x) = e^{x}, hence the distribution of MND is given by the formula:

D(x, y) = \frac{e^{x}}{1 − y(1 + (x − 1)e^{x})}.

Example 34. Theorems 11 and 32 give the distribution of the maximum number of non-overlapping occurrences of the increasing subword of length k (the pattern 123 … k), which is equal to

D(x, y) = \frac{1}{(1 − x)y + (1 − y)F_{k}(x)},

were F_{k}(x) = ∑_{i≥0} \frac{x^{ki}}{(ki)!} − ∑_{i≥0} \frac{x^{ki+1}}{(ki + 1)!}.

Example 35. If we consider the maximum number of non-overlapping occurrences of the pattern 132 then the distribution of these numbers is given by the formula

D(x, y) = \frac{1}{1 − yx + (y − 1) ∫_{0}^{x} e^{−t^{2}/2} dt}.

Example 36. The distribution of the maximum number of non-overlapping occurrences of the pattern from Theorem 12 is given by the formula:

D(x, y) = \frac{1}{1 − x + (1 − y)F_{k,a}(x)},

where F_{k,a}(x) = ∑_{i≥1} \frac{(−1)^{i+1}x^{ki+1}}{(ki + 1)!} ∏_{j=2}^{i} \binom{jk − a}{k − a}.

References

matics 175 (1997), 55-67.

exactly one dash, preprint CO/0107044.

[BabStein] E. Babson, E. Steingrímsson: Generalized permutation patterns and a classification of the Mahonian

statistics, Séminaire Lotharingien de Combinatoire, B44b:18pp, 2000.

[Bon1] M. Bóna: Exact enumeration of 1342-avoiding permutations; A close link with labeled trees and planar maps,

Journal of Combinatorial Theory, Series A, 80 (1997) 257-272.

[Bon2] M. Bóna: Permutations avoiding certain patterns; The case of length 4 and generalisations, Discrete Mathe- [Bon3] M. Bóna: Permutations with one or two 132-subsequences, Discrete Mathematics 181 (1998), 267-274.

[Claes] A. Claesson: Generalised Pattern Avoidance, European Journal of Combinatorics 22 (2001), 961-971.

[ClaesMans] A. Claesson and T. Mansour: Permutations avoiding a pair of generalized patterns of length three with [ElizNoy] S. Elizalde and M. Noy: Enumeration of Subwords in Permutations, Proceedings of FPSAC 2001.

[GoulJack] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, A Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons Inc., New York, (1983).

[Kit] S. Kitaev: Multi-avoidance of generalised patterns, preprint. http://www.math.chalmers.se/~kitaev/papers.html [Knuth] D. E. Knuth: The Art of Computer Programming, 2nd ed. Addison Wesley, Reading, MA, (1973).

[Mans] T. Mansour: Restricted 1-3-2 permutations and generalized patterns, preprint CO/0110039.

[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