SIMULTANEOUS AVOIDANCE OF GENERALIZED PATTERNS

SERGEY KITAEV AND TOUFIK MANSOUR

Abstract. In [BabStein] 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. In [Kit1] Kitaev considered simultaneous avoidance (multi-avoidance) of two or more 3-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. There either an explicit or a recursive formula was given for all but one case of simultaneous avoidance of more than two patterns.

In this paper we find the exponential generating function for the remaining case. Also we consider permutations that avoid a pattern of the form x − yz or xy − z and begin with one of the patterns 12 … k, k(k − 1) … 1, 23 … k1, (k − 1)(k − 2) … 1k or end with one of the patterns 12 … k, k(k − 1) … 1, 1k(k−1) … 2, k12 … (k−1). For each of these cases we find either the ordinary or exponential generating functions or a precise formula for the number of such permutations. Besides we generalize some of the obtained results as well as some of the results given in [Kit3]: we consider permutations avoiding certain generalized 3-patterns and beginning (ending) with an arbitrary pattern having either the greatest or the least letter as its rightmost (leftmost) letter.

1. Introduction and Background

Permutation patterns: 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. Let α ∈ S_{n} and τ ∈ S_{k} be two permutations. We say that α contains τ if there exists a subsequence 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n such that (α_{i_{1}}, …, α_{i_{k}}) is order-isomorphic to τ, that is, for all j and m, τ_{j} < τ_{m} if and only if a_{i_{j}} < a_{i_{m}}; in such a context τ is usually called a pattern. We say that α avoids τ, or is τ-avoiding, if α does not contain τ. The set of all τ-avoiding permutations in S_{n} is denoted by S_{n}(τ). For an arbitrary finite collection of patterns T, we say that α avoids T if α avoids each τ ∈ T; the corresponding subset of S_{n} is denoted by S_{n}(T).

While the case of permutations avoiding a single pattern has attracted much attention, the case of multiple pattern avoidance remains less investigated. In particular, it is natural, as the next step, to consider permutations avoiding pairs of patterns τ_{1}, τ_{2}. This problem was solved completely for τ_{1}, τ_{2} ∈ S_{3} (see [SchSim]), for τ_{1} ∈ S_{3} and τ_{2} ∈ S_{4} (see [W]), and for τ_{1}, τ_{2} ∈ S_{4} (see [B, K] and references therein). Several recent papers [CW, MV1, Kr, MV3, MV2] deal with the case τ_{1} ∈ S_{3}, τ_{2} ∈ S_{k} for various pairs τ_{1}, τ_{2}.

Generalized permutation patterns: 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. 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. Thus, a pattern with no dashes corresponds to a contiguous subword anywhere in a permutation.

The motivation for introducing these patterns was the study of Mahonian statistics. A number of results on GPs were obtained by Claesson, Kitaev and Mansour. See for example [Claes], [Kit1, Kit2, Kit3] and [Mans1, Mans2, Mans3].

As in [SchSim], dealing with the classical patterns, one can consider the case when permutations have to avoid two or more generalized patterns simultaneously. A complete solution for the number of permutations avoiding a pair of 3-patterns of type (1,2) or (2,1), that is, the patterns having one internal dash, is given in [ClaesMans]. In [Kit1] Kitaev gives either an explicit or a recursive formula for all but one case of simultaneous avoidance of more than two patterns. This is the case of avoiding the GPs 123, 231 and 312 simultaneously. In Theorem 1 we find the exponential generating function (e.g.f.) for the number of such permutations.

As it was discussed in [Kit3], if a permutation begins (resp. ends) with the pattern p = p_{1}p_{2} … p_{k}, that is, the k leftmost (resp. rightmost) letters of the permutation form the pattern p, then this is the same as avoidance of k!−1 patterns simultaneously. For example, beginning with the pattern 123 is equivalent to the simultaneous avoidance of the patterns [132), [213), [231), [312) and [321) in the Babson-Steingrímsson notation. Thus demanding that a permutation must begin or end with some pattern, in fact, we are talking about simultaneous avoidance of generalized patterns. The motivation for considering additional restrictions such as beginning or ending with some patterns is their connection to some classes of trees. An example of such a connection can be found in [Kit3, Theorem 5]. There it was shown that there is a bijection between n-permutations avoiding the pattern 132 and beginning with the pattern 12 and increasing rooted trimmed trees with n + 1 nodes. We recall that a trimmed tree is a tree where no node has a single leaf as a child (every leaf has a sibling) and in an increasing rooted tree, nodes are numbered and the numbers increase as we move away from the root. The avoidance of a generalized 3-pattern p with no dashes and, at the same time, beginning or ending with an increasing or decreasing pattern was discussed in [Kit3]. Theorem 2 generalizes some of these results to the case of beginning (resp. ending) with an arbitrary pattern avoiding p and having the greatest or least letter as the rightmost (resp. leftmost) letter.

Propositions 4 – 15 (resp. 16 – 27) give a complete description for the number of permutations avoiding a pattern of the form x−yz or xy−z and beginning with one of the patterns 12 … k or k(k − 1) … 1 (resp. 23 … k1 or (k − 1)(k − 2) … 1k). For each of these cases we find either the ordinary or exponential generating functions or a precise formula for the number of such permutations. Theorem 28 generalizes some of these results. Besides, the results from Propositions 4–27 give a complete description for the number of permutations that avoid a pattern of the form x − yz or xy − z and end with one of the patterns 12 … k, k(k − 1) … 1, 1k(k − 1) … 2 and k12 … (k − 1). To get the last one of these we only need to apply the reverse operation discussed in the next section. The results of Theorems 2 and 28 can also be used to get the case of ending with a pattern from the sets Δ_{k}^{min} or Δ_{k}^{max} introduced in the next section.

Except for the empty permutation, every permutation ends and begins with the pattern p = 1. To simplify the discussion we assume that the empty permutation also begin with the pattern 1. This does not course any harm since, to count the generating functions in question for this, we need only subtract 1 from the generating functions obtained in this paper.

2. Preliminaries

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

In this paper we denote the nth Catalan number by C_{n}; the generating function for these numbers by C(x); the nth Bell number by B_{n}.

Also, N_{q}^{p}(n) denotes the number of permutations that avoid the pattern q and begin with the pattern p; G_{q}^{p}(x) (resp. E_{q}^{p}(x)) denotes the ordinary (resp. exponential) generating function for the number of such permutations. Besides, Γ_{k}^{min} (resp. Γ_{k}^{max}) denotes the set of all k-patterns with no dashes such that the least (resp. greatest) letter of a pattern is the rightmost letter; Δ_{k}^{min} (resp. Δ_{k}^{max}) denotes the set of all k-patterns with no dashes such that the least (resp. greatest) letter of a pattern is the leftmost letter.

Recall the following properties of C(x):

(1)  C(x) = \frac{1 − \sqrt{1 − 4x}}{2x} = \frac{1}{1 − xC(x)}.

3. Simultaneous avoidance of 123, 231 and 312

The Entringer numbers E(n, k) (see [SloPlo, Sequence A000111/M1492]) are the number of permutations on 1, 2, …, n + 1, starting with k + 1, which, after initially falling, alternately fall then rise. The Entringer numbers (see [Ent]) are given by

E(0, 0) = 1, E(n, 0) = 0,

together with the recurrence relation

E(n, k) = E(n, k + 1) + E(n − 1, n − k).

The numbers E(n) = E(n, n), are the secant and tangent numbers given by the generating function

sec x + tan x.

The following theorem completes the consideration of multi-avoidance of more than two generalized 3-patterns with no dashes made in [Kit1]. Theorem 1. Let E(x) be the e.g.f. for the number of permutations that avoid 123, 231 and 312 simultaneously. Then

E(x) = 1 + x(sec(x) + tan(x)).

Proof. Let s(n; i_{1}, …, i_{m}) denote the number of permutations π ∈ S_{n}(123, 231, 312) such that π_{1}π_{2} … π_{m} = i_{1}i_{2} … i_{m} and f : S_{n} → S_{n} be a map defined by

f(π_{1}π_{2} … π_{n}) = (π_{1} + 1)(π_{2} + 1) … (π_{n} + 1),

where the addition is modulo n. Using f one can see that for all a = 1, 2, …, n − 1,

(2)  s(n; a) = s(n; a + 1).

Thus, |S_{n}(123, 231, 312)| = ns(n; 1) and we only need to prove that s(n; 1) = E_{n−1}, where E_{n} is the nth Euler number (see [SloPlo, Sequence A000111/M1492]).

Suppose π ∈ S_{n}(123, 231, 312) is an n-permutation such that π_{1} = 1 and π_{2} = t. Since π avoids 123, we get π_{3} ≤ t − 1 and it is easy to see that

s(n; 1, t) = ∑_{j=2}^{t−1} s(n; 1, t, j) = ∑_{j=1}^{t−2} s(n − 1; t − 1, j),

so

s(n; 1, t + 1) = s(n; 1, t) + ∑_{j=1}^{t−1} s(n − 1; t, j) − ∑_{j=1}^{t−2} s(n − 1; t − 1, j).

Using (2) we get

s(n; 1, t+1) = s(n; 1, t)+s(n−1; t, 1)+∑_{j=2}^{t−1} s(n−1; t−1, j −1)−∑_{j=1}^{t−2} s(n−1; t−1, j),

and by (2) again, we have for all t = 2, 3, …, n − 1,

s(n; 1, t + 1) = s(n; 1, t) + s(n − 1; 1, n − t + 1).

Besides, by the definition, it is easy to see that s(n; 1, 2) = 0 for all n ≥ 3, hence

using the definition of Entringer numbers [Ent] we get s(n; 1) = ∑_{t=2}^{n} s_{n;1,t} = E_{n−1},

as required. □

4. Avoiding a 3-pattern with no dashes and beginning with a pattern whose rightmost letter is the greatest or smallest

The following theorem generalizes Theorems 7 and 8 in [Kit3]. Recall the definition of E_{q}^{p} in Section 2. Theorem 2. Suppose p_{1}, p_{2} ∈ Γ_{k}^{min} and p_{1} ∈ S_{k}(132), p_{2} ∈ S_{k}(123). Thus, the complements C(p_{1}), C(p_{2}) ∈ Γ_{k}^{max} and C(p_{1}) ∈ S_{k}(312), C(p_{2}) ∈ S_{k}(321). Then, for k ≥ 2,

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

and

E_{123}^{p_{2}}(x) = E_{321}^{C(p_{2})}(x) = \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} )}.

Proof. To prove the theorem, it is enough to copy the proofs of Theorems 7 and 8 in [Kit3], since the fact that the first k −1 letters of p are possibly not in decreasing order is immaterial for the proofs of that theorems. Thus we can get the formula for E_{132}^{p}(x) and E_{123}^{p}(x), and automatically, using properties of the complement, the formula for E_{312}^{C(p)}(x) and E_{321}^{C(p)}(x), directly from these theorems. However we give here a proof of the formula for E_{132}^{p}(x) and refer to [Kit3, Theorem 8] for a proof of the formula for E_{123}^{p}(x).

If k = 1, we have no additional restrictions, that is, we are dealing only with the avoidance of 132 and, according to [ElizNoy, Theorem 4.1] or [Kit2, Theorem 12],

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

Also, according to [Kit3, Theorem 6],

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

Let R_{n,k} (resp. F_{n,k}) denote the number of n–permutations that avoid the pattern 132 and begin with a decreasing (resp. increasing) subword of length k > 1 and let π be such a permutation of length n + 1. Suppose π = σ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, 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}F_{n−i,2} such permutations with the right properties, where i indicates

the length of σ. 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 F_{n−k+1,2} ways. Thus

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

We observe that (3) 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}F_{n−k+1,2}, which counts the number of such permutations, is zero, whereas there is one “good” (n + 1)–permutation in 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 equality (4)), we get

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

with the initial condition E_{132}^{p}(0) = 0. We solve this equation and get

E_{132}^{p}(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.

□

Remark 3. It is obvious that if in the previous theorem p_{1} ∉ S_{k}(132) and p_{2} ∉ S_{k}(123), then E_{132}^{p_{1}}(x) = E_{123}^{p_{2}}(x) = 0.

5. Avoiding a pattern x-yz and beginning with an increasing or decreasing pattern

In this section we consider avoidance of one of the patterns 1 − 23, 1 − 32, 2 − 31, 2 − 13, 3 − 12 and 1 − 32 and beginning with a decreasing pattern. We get all the other cases, that is, avoidance of one of these patterns and beginning with an increasing pattern, by the complement operation. For instance, we have E_{1−23}^{k(k−1)...1}(x) = E_{3−21}^{12...k}(x). Proposition 4. We have

E_{1−23}^{k(k−1)...1}(x) = E_{1−32}^{k(k−1)...1}(x) = \{ \begin{matrix}(e^{e^{x}}/(k − 1)!) ∫_{0}^{x} t^{k−1}e^{−e^{t}+t} dt, & if k ≥ 2, \\ e^{e^{x}−1}, & if k = 1. \end{matrix}

Proof. We prove the statement for the pattern 1 − 23. All the arguments we give for this pattern are valid for the pattern 1 − 32. The only difference is that instead of decreasing order in τ (see below), we have increasing order.

Suppose k ≥ 2. Let B_{n,k} denote the number of n–permutations that avoid the pattern 1 − 23 and begin with a decreasing subword of length k. Suppose π = σ1τ be one of such permutations of length n + 1. Obviously, the letters of τ must be in decreasing order since otherwise we have an occurrence of 1 − 23 in π starting from the letter 1. If |σ| = i then we can choose the letters of σ in \binom{n}{i} ways. Since the letters of τ are in decreasing order, they do not affect σ and thus there are B_{i,k} possibilities to choose σ. Besides, if |σ| = k − 1 and letters of σ are in decreasing order, we get \binom{n}{k−1} additional possibilities to choose π. Thus

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

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

\frac{d}{dx}E_{1−23}^{k(k−1)...1}(x) = (E_{1−23}^{k(k−1)...1}(x) + \frac{x^{k−1}}{(k − 1)!})e^{x}

with the initial condition E_{1−23}^{k(k−1)...1}(0) = 0. The solution to this equation is given by

(5)  E_{1−23}^{k(k−1)...1}(x) = (e^{e^{x}}/(k − 1)!) ∫_{0}^{x} t^{k−1}e^{−e^{t}+t} dt.

If k = 1, then there is no additional restriction. According to [Claes, Prop. 2] (resp. [Claes, Prop. 5]), the number of n-permutations that avoid the pattern 1-23 (resp. 1-32) is the nth Bell number and the e.g.f. for the Bell numbers is e^{e^{x}−1}. However, all the arguments used for k ≥ 2 remain the same for the case k = 1 except for the fact that we do not count the empty permutation, which, of course, avoids 1-23. So, if k = 1, we need to add 1 to the right-hand side of (5):

E_{1−23}^{1}(x) = e^{e^{x}} ∫_{0}^{x} e^{−e^{t}+t} dt + 1 = e^{e^{x}−1}.
□

Proposition 5. We have

E_{3−12}^{k(k−1)...1}(x) = \{ \begin{matrix}e^{e^{x}} ∫_{0}^{x} e^{−e^{t}} ∑_{n≥k−1} \frac{t^{n}}{n!} dt, & if k ≥ 2, \\ e^{e^{x}−1}, & if k = 1. \end{matrix}

Proof. Suppose k ≥ 2. Let B_{n,k} denote the number of n–permutations that avoid the pattern 3 − 12 and begin with a decreasing subword of length k. Suppose π = σ(n + 1)τ be such a permutation of length n + 1. Obviously, the letters of τ must be in decreasing order since otherwise we have an occurrence of the pattern 3 − 12 in π starting from the letter (n + 1). If |σ| = i then we can choose the letters of σ in \binom{n}{i} ways. Since the letters of τ are in decreasing order, they do not affect σ and thus there are B_{i,k} possibilities to choose σ. Besides, if n ≥ k − 1, then π can be decreasing, that is, (n + 1) can be in the leftmost position. Thus

B_{n+1,k} = ∑_{i≥0} \binom{n}{i}B_{i,k} + δ_{n,k},

where

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

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

\frac{d}{dx}E_{3−12}^{k(k−1)...1}(x) = e^{x}E_{3−12}^{k(k−1)...1}(x) + ∑_{n≥k−1} \frac{x^{n}}{n!}

with the initial condition E_{3−12}^{k(k−1)...1}(0) = 0. The solution to this equation is given by

(6)  E_{3−12}^{k(k−1)...1}(x) = e^{e^{x}} ∫_{0}^{x} e^{−e^{t}} ∑_{n≥k−1} \frac{t^{n}}{n!} dt.

If k = 1, then there is no additional restriction. In [Claes, Prop. 5] it is shown that E_{1−32}^{1}(x) = e^{e^{x}−1}. Using the complement, the number of n-permutations that avoid 1 − 32 is equal to the number of n-permutations that avoid 3 − 12. We get that E_{3−12}^{1}(x) = e^{e^{x}−1}. However, all the arguments used for the case k ≥ 2 remain the same for the case k = 1 except the fact that we do not count the empty permutation, which avoids 3-12. So, if k = 1, we need to add 1 to the right-hand side of (6):

E_{3−12}^{1}(x) = e^{e^{x}} ∫_{0}^{x} e^{−e^{t}}e^{t} dt + 1 = e^{e^{x}−1}.
□

Proposition 6. We have

E_{3−21}^{k(k−1)...1}(x) = \{ \begin{matrix}0, & if k ≥ 3, \\ e^{e^{x}} ∫_{0}^{x} e^{−e^{t}}(e^{t} − 1) dt, & if k = 2, \\ e^{e^{x}−1}, & if k = 1. \end{matrix}

Proof. For k ≥ 3, the statement is obviously true. If k = 1, then the statement follows from [Claes, Prop. 2] and the fact that there are as many n-permutations avoiding the pattern 1 − 23, as n-permutations avoiding the pattern 3 − 21. For the case k = 2, we can use exactly the same arguments as those in the proof of Proposition 5 to get the same recurrence relation and thus the same formula, which, however, is valid only for k = 2. □

Recall the definition of N_{q}^{p} in Section 2. Proposition 7. We have

N_{2−13}^{k(k−1)...1}(n) = \{ \begin{matrix}C_{n−k+1}, & if n ≥ k, \\ 0, & else. \end{matrix}

Proof. If k = 1, then the statement follows from [Claes, Prop. 22]. Suppose k ≥ 2 and let π = σnτ be an n-permutation avoiding 2 − 31 and beginning with the pattern k(k − 1) … 1. Suppose, without loss of generality that σ consists of the letters 1, 2, …, ℓ. Now ℓ must be the rightmost letter of σ, since otherwise ℓ, the rightmost letter of σ and n form the pattern 2 − 13. Also, the letter (ℓ − 1) must be next to the rightmost letter of σ since otherwise the letter (ℓ − 1), next to the rightmost letter of σ and the letter ℓ form the pattern 2 − 13. And so on. Thus σ must be increasing, which contradicts the fact that π must begin with a decreasing pattern of length greater than 1. So |σ| = 0 and τ must begin with the pattern (k − 1)(k − 2) … 1. Now, we can consider the letter (n − 1) and, by the same reasoning, get that it must be in the second position of π. Then we consider (n − 2), and so on up to the letter (n − k + 2). Finally, we get that π = n(n − 1) … (n − k + 2)π′, where π′ must avoid the pattern 2 − 13 and thus, there are C_{n−k+1} ways to choose π ([Claes, Prop. 22]). □

Recall that C(x) is the generating function for the Catalan numbers. Also recall the definition of G_{q}^{p} in Section 2.

Proposition 8. We have

G_{2−31}^{k(k−1)...1}(x) = \{ \begin{matrix}x^{k}C^{k+1}(x), & if k ≥ 2 \\ C(x), & if k = 1. \end{matrix}

Proof. If k = 1, then there is no additional restriction, and thus G_{2−31}^{1}(x) = C(x) (applying the complement operation to [Claes, Prop. 22]).

Suppose k ≥ 2. Using the reverse, we see that beginning with k(k − 1) … 1 and avoiding 2 − 31 is equivalent to ending with 12 … k and avoiding 13 − 2, which by [Claes] is equivalent to ending with 12 … k and avoiding 1 − 3 − 2.

Suppose π = π′nπ′′ ends with 12 … k and avoids 1 − 3 − 2. Each letter of π′ must be greater than any letter of π′′, since otherwise we have an occurrence of the pattern 1 − 3 − 2 involving the letter n. Also, π′ and π′′ avoid the pattern 1 − 3 − 2, and π′′ ends with the pattern 12 … k. In terms of generating functions (the generating function for the number of permutations ending with 12 … k and avoiding 1 − 3 − 2 is, of course, G_{2−31}^{k(k−1)...1}(x)) this means that

(7)  G_{2−31}^{k(k−1)...1}(x) = xC(x)G_{2−31}^{k(k−1)...1}(x) + xG_{2−31}^{(k−1)...1}(x),

where the rightmost term corresponds to the case when π′′ is empty. Now, (1) and (7) give

G_{2−31}^{k(k−1)...1}(x) = x^{k}C(x)/(1 − xC(x))^{k} = x^{k}C^{k+1}(x).
□

6. Avoiding a pattern xy-z and beginning with an increasing or decreasing pattern

First of all we state the following well-known binomial identity

(8)  ∑_{i=1}^{n−m−k+1} \binom{n − m − i}{k − 1}\binom{m + i − 1}{m} = \binom{n}{m + k}.

Let s_{q}(n) denote the cardinality of the set S_{n}(q) and s_{q}(n; i_{1}, i_{2}, … i_{m}) denote the number of permutations π ∈ S_{n}(q) with π_{1}π_{2} … π_{m} = i_{1}i_{2} … i_{m}.

In this section we consider avoidance of one of the patterns 12-3, 13-2 and 23-1 and beginning with an increasing or decreasing pattern. We get all the other cases, which are avoidance of one of the patterns 32-1, 31-2 and 21-3 and beginning with an increasing or decreasing pattern, by the complement operation. For instance, we have N_{13−2}^{12...k}(n) = N_{31−2}^{k(k−1)...1}(n).

6.1. The pattern 12−3. We first consider beginning with the pattern p = k … 21. In [ClaesMans, Lemma 9] it was proved that

s_{12−3}(n; i) = ∑_{j=0}^{i−1} \binom{i − 1}{j}s_{12−3}(n − 2 − j),

together with s_{12−3}(n; n) = s_{12−3}(n; n − 1) = s_{12−3}(n − 1).

On the other hand, from the definitions, it is easy to see that

N_{12−3}^{k(k−1)...1}(n) = ∑_{i=1}^{n−k+1} \binom{n − i}{k − 1}s_{12−3}(n − k + 1; i).

Hence, using (8) and the fact shown in [Claes] that s_{12−3}(n) equals B_{n}, we get the following proposition.

Proposition 9. For all n ≥ k + 1, we have

\begin{matrix}N_{12−3}^{k(k−1)...1}(n) = (k + 1)B_{n−k}+ \\ + ∑_{j=0}^{n−k−2} (\binom{n}{k+j} − k\binom{n−k−1}{j} − \binom{n−k}{j}) B_{n−k−1−j}, \end{matrix}

together with N_{12−3}^{k(k−1)...1}(k) = 1 and N_{12−3}^{k(k−1)...1}(n) = 0 for all n ≤ k − 1.

Now, let us consider beginning with the pattern p = 12 … k. From the definitions, it is easy to see that N_{12−3}^{12...k}(n) = 0 for all n, where k ≥ 3, and N_{12−3}^{1}(n) = s_{12−3}(n) = B_{n} (see [ClaesMans, Prop. 10]). Thus, we only need to consider the case k = 2.

Suppose π ∈ S_{12−3}(n) is a permutation with π_{1} < π_{2}. It is easy to see that π_{2} = n. Hence N_{12−3}^{12}(n) = (n − 1)s_{12−3}(n − 2), for all n ≥ 2, and by [ClaesMans, Prop. 10], we get the truth of the following Proposition 10. We have

E_{12−3}^{12...k}(x) = \{ \begin{matrix}0, & if k ≥ 3, \\ x^{2} ∑_{j=0}^{k}(1 − jx)^{−1} ∑_{d≥0} \frac{x^{d}}{(1 − x)(1 − 2x) … (1 − dx)}, & if k = 2, \\ ∑_{d≥0} \frac{x^{d}}{(1 − x)(1 − 2x) … (1 − dx)}, & if k = 1. \end{matrix}

6.2. The pattern 13 − 2. Let us introduce an object that plays an important role in the proof of the main result in this case. For n ≥ m + 1 ≥ 0, we define

A(n; m) = ∑_{1≤i_{m}<···<i_{2}<i_{1}<n−1} s_{1−3−2}(n; i_{1}, i_{2}, …, i_{m}).

We extend this definition to m = 0 by A(n; 0) = s_{1−3−2}(n). Lemma 11. For all n ≥ m ≥ 0,

A(n; m) = ∑_{j≥0}(−1)^{j}\binom{m + 1 − j}{j}s_{1−3−2}(n − j).

Proof. For m = 0 the lemma holds by definitions. Let m ≥ 0; so

A(n; m) = ∑_{1≤i_{m}<···<i_{2}<i_{1}<n−1} ∑_{j=1}^{n} s_{1−3−2}(n; i_{1}, i_{2}, …, i_{m}, j),

= A(n; m + 1) + ∑_{1≤i_{m}<···<i_{2}<i_{1}<n−1} s_{1−3−2}(n; i_{1}, i_{2}, …, i_{m}, n),

= A(n; m + 1) + ∑_{1≤i_{m}<···<i_{2}<i_{1}<n−1} s_{1−3−2}(n − 1; i_{1}, i_{2}, …, i_{m}),

= A(n; m + 1) + ∑_{1≤i_{m}<···<i_{2}<n−2} s_{1−3−2}(n − 1; n − 1, i_{2}, …, i_{m})+

+ ∑_{1≤i_{m}<···<i_{2}<i_{1}<n−2} s_{1−3−2}(n − 1; i_{1}, i_{2}, …, i_{m}),

= A(n; m + 1) + A(n − 1; m)+

+ ∑_{1≤i_{m−1}<···<i_{1}<n−2} s_{1−3−2}(n − 2; i_{1}, …, i_{m−1}),

= ⋯ = A(n; m + 1) + A(n − 1; m) + ⋯ + A(n − m − 1; 0).

Hence, using induction on m, we get

\begin{matrix}A(n; m + 1) = ∑_{j≥0}(−1)^{j}\binom{m + 1 − j}{j}s_{1−3−2}(n − j) \\ − ∑_{d=0}^{m} ∑_{j≥0}(−1)^{j}\binom{m − d + 1 − j}{j}s_{1−3−2}(n − 1 − d − j). \end{matrix}

Using the identity \binom{r}{0} − \binom{r}{1} + ⋯ + (−1)^{s}\binom{r}{s} = \binom{r−1}{s}, we get

\begin{matrix}A(n; m + 1) = ∑_{j≥0}(−1)^{j}\binom{m + 1 − j}{j}s_{1−3−2}(n − j) \\ − ∑_{d=0}^{m}(−1)^{d}\binom{m − d}{d}s_{1−3−2}(n − 1 − d). \end{matrix}

Now using the identity \binom{n}{k} + \binom{n}{k−1} = \binom{n+1}{k}, we get

A(n; m + 1) = ∑_{j≥0}(−1)^{j}\binom{m + 2 − j}{j}s_{1−3−2}(n − j),

which means that the lemma holds for m + 1. □

Now we find N_{13−2}^{k(k−1)...1}(n). Proposition 12. Let k ≥ 1. For all n ≥ 0,

N_{13−2}^{k(k−1)...1}(n) = C_{n+1−k} + ∑_{d=0}^{k−2} ∑_{j≥0}(−1)^{j}\binom{k + 1 − d − j}{j}C_{n−d−j}.

Proof. Claesson [Claes] proved that the set of permutations that avoid the pattern 13 − 2 is the same as the set of permutations that avoid the pattern 1 − 3 − 2, hence

(9)  N_{13−2}^{k(k−1)...1}(n) = N_{1−3−2}^{k(k−1)...1}(n).

If the leftmost letter of a permutation avoiding 13-2 and beginning with the pattern k(k − 1) … 1 is n, then, obviously, there are N_{1−3−2}^{(k−1)(k−2)...1}(n − 1) such permutations. Otherwise, it is easy to see that there are A(n; k) such permutations. So, by Lemma 11 and the considerations above, also using the fact that the number of (1 − 3 − 2)-avoiding n-permutations in S_{n} is C_{n}, we get

N_{13−2}^{k(k−1)...1}(n) = N_{13−2}^{(k−1)(k−2)...1}(n − 1) + ∑_{j≥0}(−1)^{j}\binom{k + 1 − j}{j}C_{n−j}.

Moreover, using the definitions and Equation (9), we have N_{13−2}^{1}(n) = s_{1−3−2}(n) = C_{n}, for all n ≥ 0. Hence, by induction on k, the proposition holds. □

Now, let us consider the case of N_{13−2}^{12...k}(n). Proposition 13. Let k ≥ 1. For all n ≥ k, we have

N_{13−2}^{12...k}(n) = C_{n+1−k}.

Proof. Suppose π = π′nπ′′ is a permutation in S_{n}(13 − 2) = S_{n}(1 − 3 − 2) (see (9)), such that π_{1} < π_{2} < ⋯ < π_{k}. It is easy to see that there exists an m such that

π = (m + 1)(m + 2) … (m + k − 1)βnπ′′,

where β is a 1−3−2-avoiding permutation on the letters m+k, m+k+1, …, n−1, and π′′ ∈ S_{m}(1 − 3 − 2). Hence, in terms of generating functions, we get

∑_{n≥0} N_{13−2}^{12...k}(n)x^{n} = x^{k}C^{2}(x).

The rest is easy to check using the identity xC^{2}(x) = C(x) − 1. □

6.3. The pattern 23 − 1. We first consider beginning with the pattern p = k(k − 1) … 1. Proposition 14. For all k ≥ 1,

E_{23−1}^{k(k−1)...1}(x) = x^{k−1} (∑_{d≥0} \frac{x^{d}}{(1 − x)(1 − 2x) ⋯ (1 − dx)} − 1) .

Proof. Let π ∈ S_{n}(23 − 1) be a permutation such that π_{1} < π_{2} < ⋯ < π_{k}. Since π avoids 23−1, we have π_{j} = j, for each j = 1, 2, …, k−1. Hence π = 12 … (k−1)π′, where π′ is a non-empty 23 − 1-avoiding permutation in S_{n+1−k}. The rest is easy to get by using [ClaesMans, Prop. 17]. □

Now let us consider beginning with the pattern p = 12 … k. Proposition 15. Suppose k ≥ 1. For all n ≥ k + 1,

N_{23−1}^{12...k}(n) = (1 + \binom{n − 1}{k − 1}) B_{n−k} + ∑_{j=0}^{n−k−2} [\binom{n − 1}{k + j} − \binom{n − k − 1}{j}] B_{n−k−1−j},

with N_{23−1}^{12...k}(k) = 1.

Proof. In [ClaesMans, Lemma 16] proved that for all 2 ≤ i ≤ n − 1,

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

together with s_{23−1}(n; n) = s_{23−1}(n; 1) = s_{23−1}(n − 1) = B_{n−1}.

On the other hand, by the definitions, it is easy to see that

N_{23−1}^{12...k}(n) = ∑_{i=1}^{n−k+1} \binom{n − i}{k − 1}s_{23−1}(n − k + 1; i).

Hence, using (8) and the fact that [Claes] s_{23−1}(n) is given by B_{n}, we get the desired result. □

7. Avoiding a pattern xy-z and beginning with the pattern (k − 1)(k − 2) … 1k or 23 … k1

In this section we consider avoidance of one of the patterns 12−3, 13−2, 23−1, 21 − 3, 31 − 2 and 13 − 2 and beginning with the pattern (k − 1)(k − 2) … 1k. The case when a permutation begins with the pattern 23 … k1 and avoids a pattern xy − z can be obtained then by the complement operation.

7.1. Avoiding 12 − 3 and beginning with (k − 1)(k − 2) … 1k. Proposition 16. We have

N_{12−3}^{(k−1)(k−2)...1k}(n) = \binom{n − 1}{k − 1}B_{n−k}.

Proof. Suppose π = π′nπ′′ avoids the pattern 12 − 3 and begins with the pattern (k − 1)(k − 2) … 1k. We have that π′ must be decreasing, since otherwise we have an occurrence of the pattern 12−3 involving the letter n, and π′′ must avoid 12−3. Also, since π begins with (k − 1) … 21k, the length of π′ is k − 1. Hence, by [Claes] (the number of permutations in S_{n}(12 − 3) is given by B_{n}), we have

N_{12−3}^{(k−1)(k−2)...1k}(n) = \binom{n − 1}{k − 1}B_{n−k}.

□

7.2. Avoiding 13 − 2 and beginning with (k − 1)(k − 2) … 1k. By [Claes], a permutation π avoids the pattern 13 − 2 if and only if π avoids 1 − 3 − 2.

Suppose π = π′nπ′′ is an n-permutation avoiding 1 − 3 − 2 and beginning with (k − 1)(k − 2) … 1k. Obviously, π′ and π′′ avoid 1 − 3 − 2 and each letter of π′ is greater than any letter of π′′, since otherwise we have an occurrence of the pattern 1−3−2 involving the letter n. Also, π′ begins with the pattern (k −1)(k −2) … 1k or π′ = (k − 1)(k − 2) … 1.

By [Knuth], the generating function for the number of permutations that avoid 1 − 3 − 2 is C(x), hence, using the considerations above,

G_{13−2}^{(k−1)(k−2)...1k}(x) = xG_{13−2}^{(k−1)(k−2)...1k}(x)C(x) + x^{k}C(x).

Therefore, by (1), we get the following. Proposition 17. We have

G_{13−2}^{(k−1)(k−2)...1k}(x) = x^{k}C^{2}(x).

Hence

N_{13−2}^{(k−1)(k−2)...1k}(n) = \{ \begin{matrix}C_{n−(k−1)}, & if n ≥ k \\ 0, & else. \end{matrix}

7.3. Avoiding 21 − 3 and beginning with (k − 1)(k − 2) … 1k. If k ≥ 3 then, by the definitions, we have N_{21−3}^{(k−1)(k−2)...1k}(n) = 0.

If k = 1 then, by the definitions and [Claes], we have N_{21−3}^{1}(n) = B_{n}.

Suppose k = 2 and π = π′nπ′′ is an n-permutation avoiding the pattern 21 − 3 and beginning with the pattern (k − 1)(k − 2) … 1k = 12. It is easy to see that π′ must be increasing, and the length of π′ is at least 1. Thus, using the fact that the number of permutations in S_{n}(21 − 3) is given by B_{n} (see [Claes]), we have

(10)  N_{21−3}^{(k−1)(k−2)...1k}(n) = ∑_{j=1}^{n−1} \binom{n − 1}{j}B_{n−1−j}.

Since B_{n} = ∑_{j=0}^{n−1} \binom{n − 1}{j}B_{n−1−j}, equality (10) gives that

N_{21−3}^{(k−1)(k−2)...1k}(n) = B_{n} − B_{n−1}.

Thus we have proved the following. Proposition 18.

N_{21−3}^{(k−1)(k−2)...1k}(n) = \{ \begin{matrix}0, & if k ≥ 3 \\ B_{n} − B_{n−1}, & if k = 2, \\ B_{n}, & if k = 1. \end{matrix}

7.4. Avoiding 23 − 1 and beginning with (k − 1)(k − 2) … 1k. Proposition 19. We have

N_{23−1}^{(k−1)...1k}(n) = \{ \begin{matrix}B_{n−k} + ∑_{t=2}^{n−k+2} \binom{t + k − 3}{k − 2} ∑_{j=0}^{t−2} \binom{t − 2}{j}B_{n−k−1−j}, & if k ≥ 3 \\ B_{n−1}, & if k = 2, \\ B_{n}, & if k = 1. \end{matrix}

Proof. Suppose k = 2. We are interested in the permutations π ∈ S_{n}(23 − 1) that begin with the pattern 12. It is easy to see that π_{1} = 1, hence B_{12}^{23−1}(n) = B_{n−1} for all n ≥ 2.

Suppose k ≥ 3. We recall that s_{23−1}(n; t) is the number of permutations in S_{n}(23 − 1) having t as the first letter. By [ClaesMans], s(n; 1) = B_{n−1} and for t ≥ 2, we have

s(n; t) = ∑_{j=0}^{t−2} \binom{t − 2}{j}B_{n−2−j}.

On the other hand, if a permutation π = π′1tπ′′ avoids 23 − 1 and begins with the pattern (k − 1)(k − 2) … 1k, then π′ is decreasing of length k − 2, and using s(n; t), we get

N_{23−1}^{(k−1)(k−2)...1k}(n) = B_{n−k} + ∑_{t=2}^{n−k+2} \binom{t + k − 3}{k − 2} ∑_{j=0}^{t−2} \binom{t − 2}{j}B_{n−k−1−j}.

□

7.5. Avoiding 31 − 2 and beginning with (k − 1)(k − 2) … 1k. By [Claes], a permutation π avoids the pattern 31−2 if and only if π avoids the pattern 3−1−2.

Suppose π = π′1π′′ is an n-permutation avoiding 3 − 1 − 2 and beginning with (k − 1)(k − 2) … 1k. Obviously, π′ and π′′ avoid 3 − 1 − 2 and each letter of π′ is smaller than any letter of π′′, since otherwise we have an occurrence of the pattern 3−1−2 involving the letter 1. Also, π′ begins with the pattern (k −1)(k −2) … 1k or π′ = (k−1)(k−2) … 2 and π′′ is not empty. So, using the generating function for the number of permutations avoiding the pattern 3−1−2, which is C(x) ([Knuth]), we get

G_{31−2}^{(k−1)(k−2)...1k}(x) = xG_{31−2}^{(k−1)(k−2)...1k}(x)C(x) + x^{k−1}(C(x) − 1).

Therefore, using (1), we get the following. Proposition 20. We have

G_{31−2}^{(k−1)(k−2)...1k}(x) = \{ \begin{matrix}x^{k}C^{3}(x), & if k ≥ 2, \\ C(x), & if k = 1. \end{matrix}

Hence

N_{31−2}^{(k−1)(k−2)...1k}(n) = \{ \begin{matrix}C_{n−k+2} − C_{n−k+1}, & if k ≥ 2, \\ C_{n}, & if k = 1. \end{matrix}

7.6. Avoiding 32 − 1 and beginning with (k − 1)(k − 2) … 1k. Proposition 21.

N_{32−1}^{(k−1)(k−2)...1k}(n) = \{ \begin{matrix}0, & if k ≥ 4 \\ B_{n−1} − (n − 2)B_{n−3}, & if k = 3 and n ≥ 3, \\ B_{n} − (n − 1)B_{n−2}, & if k = 2 and n ≥ 2, \\ B_{n}, & if k = 1. \end{matrix}

Proof. Using the definitions and [Claes], it is easy to see that the statement is true for k = 1, 2 and k ≥ 4.

Suppose now that k = 3 and π = π′1π′′ is an n-permutation avoiding the pattern 32 − 1 and beginning with the pattern (k − 1)(k − 2) … 1k = 213. We have that π′ must be increasing, since otherwise we have an occurrence of the pattern 32 − 1 involving the letter 1, and π′′ must avoid 32−1. Moreover, since π begins with 213, the length of π is 1 and the rightmost letter of π′′ is greater than the letter of π′. Also, it is easy to see that the number of permutations in S_{n−1}(32 − 1) beginning with the pattern 12 is the same as the number of permutations in S_{n}(32 − 1) beginning with the pattern 213 (one can see it by placing 1 in the second position). Hence N_{32−1}^{(k−1)...21k}(n) = B_{n−1} − (n − 2)B_{n−3} for all n ≥ 3. □

8. Avoiding a pattern x-yz and beginning with the pattern (k − 1)(k − 2) … 1k or 23 … k1

In this section we consider avoidance of one of the patterns 1−23, 1−32, 2−31, 2 − 13, 3 − 12 and 1 − 32 and beginning with the pattern (k − 1)(k − 2) … 1k. The case when a permutation begins with the pattern 23 … k1 and avoids a pattern x − yz can be obtained by the complement operation. Proposition 22. We have

E_{1−32}^{(k−1)(k−2)...1k}(x) = \{ \begin{matrix}e^{e^{x}} ∫_{0}^{x} e^{−e^{t}} ∑_{n≥k−1} \frac{t^{n}}{n!} dt, & if k ≥ 2, \\ e^{e^{x}−1}, & if k = 1. \end{matrix}

Proof. Suppose k ≥ 2. Let B_{n,k} denote the number of n–permutations that avoid the pattern 1−32 and begin with the pattern (k−1)(k−2) … 1k. Suppose π = σ1τ is such a permutation of length n+1. Obviously, the letters of τ must be in increasing order, since otherwise we have an occurrence of the pattern 1 − 32 in π starting from the letter 1. If |σ| = i, then we can choose the letters of σ in \binom{n}{i} ways. Since the letters of τ are in increasing order, they do not affect σ and thus there are B_{i,k} possibilities to choose σ. Also, if n ≥ k − 1, then 1 can be in the (k − 1)th position, and in this case, since π begins with the pattern (k − 1)(k − 2) … 1k, it must be that π = (k − 1)(k − 2) … 21k(k + 1) … (n + 1). Thus, in the last case we have only one permutation. This leads to the recurrence relation

B_{n+1,k} = ∑_{i≥0} \binom{n}{i}B_{i,k} + δ_{n,k},

where

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

This recurrence relation is identical to the one given in the proof of Proposition 5, so using this proof we get the desired result. □

Proposition 23. We have

E_{1−23}^{(k−1)(k−2)...1k}(x) = \{ \begin{matrix}e^{e^{x}} ∫_{0}^{x} ∫_{0}^{t} \frac{r^{k−2}}{(k−2)!}e^{r−e^{t}} drdt, & if k ≥ 2, \\ e^{e^{x}−1}, & if k = 1. \end{matrix}

Proof. If k = 1, then the statement is true due to Proposition 4.

Suppose k ≥ 2. Let B_{n,k} denote the number of n-permutations that avoid the pattern 1 − 23 and begin with the pattern (k − 1)(k − 2) … 1k. Suppose π = σ1τ is such a permutation of length n+1. Obviously, the letters of τ must be in decreasing order since otherwise we have an occurrence of the pattern 1−23 in π starting from the letter 1. If |σ| = i, then we can choose the letters of σ in \binom{n}{i} ways. Since the letters of τ are in the decreasing order, they do not affect σ and thus there are B_{i,k} possibilities to choose σ. Besides, if n ≥ k − 1, then 1 can be in the (k − 1)th position, and in this case, since π begins with the pattern (k − 1)(k − 2) … 1k and τ is decreasing, it must be that the kth letter of π is (n + 1) and there are \binom{n−1}{k−2} ways to choose the letters of σ and then write them in decreasing order. Thus,

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

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

\frac{d}{dx}E_{1−23}^{(k−1)(k−2)...1k}(x) = E_{1−23}^{(k−1)(k−2)...1k}e^{x} + ∑_{n≥0} \binom{n − 1}{k − 2}\frac{x^{n}}{n!} ,

with the initial condition E_{1−23}^{(k−1)(k−2)...1k}(0) = 0. If F (x) denotes the last term, then it is easy to see that F′(x) = \frac{x^{k−2}}{(k−2)!}e^{x}, and thus

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

Now, the solution to the equation above is given by

(11) E_{1−23}^{(k−1)(k−2)...1k}(x) = e^{e^{x}} ∫_{0}^{x} e^{−e^{t}}F (t) dt = e^{e^{x}} ∫_{0}^{x} ∫_{0}^{t} \frac{r^{k−2}}{(k − 2)!}e^{r−e^{t}} drdt.

For example, if k = 2, then (k − 1)(k − 2) … 1k = 12 and (11) gives

E_{1−23}^{12} = e^{e^{x}} ∫_{0}^{x} e^{−e^{t}}(e^{t} − 1) dt,

which is a particular case of Proposition 6, since the number of n-permutations that avoid the pattern 3 − 21 and begin with the pattern 21 is equal to the number of n-permutations that avoid the pattern 1 − 23 and begin with the pattern 12 by applying the complement. □

Proposition 24. We have

G_{2−13}^{(k−1)(k−2)...1k}(x) = \{ \begin{matrix}0, & if k ≥ 3 \\ x^{2}C^{3}(x), & if k = 2 \\ C(x), & if k = 1. \end{matrix}

Hence

N_{2−13}^{(k−1)(k−2)...1k}(n) = \{ \begin{matrix}0, & if k ≥ 3 \\ C_{n−1} − C_{n−2}, & if k = 2 \\ C_{n}, & if k = 1. \end{matrix}

Proof. For the case k = 1, see Proposition 7. If k ≥ 3, then the statement is true, since in this case the pattern (k − 1)(k − 2) … 1k does not avoid 2 − 13.

Suppose now that k = 2. Using the reverse, we see that beginning with the pattern 12 and avoiding 2 − 13 is equivalent to ending with the pattern 21 and avoiding 31 − 2, which by [Claes] is equivalent to ending with the pattern 21 and avoiding the pattern 3 − 1 − 2.

Let π = π′1π′′ be an n-permutation avoiding 3 − 1 − 2 and ending with the pattern 21. Obviously, π′ and π′′ avoid 3 − 1 − 2 and each letter of π′ is less than any letter of π′′, since otherwise we have an occurrence of 3 − 1 − 2 involving the letter 1. Also, π′′ ends with the pattern 21 or |π′′| = 1. So, using the generating function for the number of permutations avoiding 3−1−2, which is C(x) ([Knuth]), we have

G_{2−13}^{12}(x) = xG_{2−13}^{12}(x)C(x) + x(C(x) − 1).

Therefore, using (1), we get the desired result. □

Proposition 25. We have

G_{2−31}^{(k−1)(k−2)...1k}(x) = x^{k}C^{2}(x).

Hence

N_{2−31}^{(k−1)(k−2)...1k}(n) = \{ \begin{matrix}C_{n−(k−1)}, & if n ≥ k \\ 0, & else. \end{matrix}

Proof. Using the reverse, we see that beginning with the pattern (k−1)(k−2) … 1k and avoiding the pattern 2−31 is equivalent to ending with the pattern k12 … (k−1) and avoiding the pattern 13 − 2, which, by [Claes], is equivalent to ending with the pattern k12 … (k − 1) and avoiding the pattern 1 − 3 − 2.

Let π = π′nπ′′ be an n-permutation avoiding the pattern 1 − 3 − 2 and ending with the pattern k12 … (k − 1). Obviously, π′ and π′′ avoid the pattern 1 − 3 − 2 and each letter of π′ is greater than any letter of π′′, since otherwise we have an occurrence of the pattern 1 − 3 − 2 involving the letter n. Also, π′′ ends with the pattern k12 … (k − 1) or π′′ = 12 … (k − 1).

Using the reverse operation, the generating function for the number of permutations ending with the pattern k12 … (k − 1) and avoiding 1 − 3 − 2 is equal to G_{2−31}^{(k−1)(k−2)...1k}(x). In terms of generating functions, the considerations above lead to

G_{2−31}^{(k−1)(k−2)...1k}(x) = xG_{2−31}^{(k−1)(k−2)...1k}(x)C(x) + x^{k}C(x).

Therefore, by (1), we get the desired result. □

Proposition 26. We have

E_{3−12}^{(k−1)(k−2)...1k}(x) = \{ \begin{matrix}(e^{e^{x}}/(k − 1)!) ∫_{0}^{x} t^{k−1}e^{−e^{t}+t} dt, & if k ≥ 2, \\ e^{e^{x}−1}, & if k = 1. \end{matrix}

Proof. Suppose k ≥ 2. Let B_{n,k} denote the number of n-permutations that avoid the pattern 3 − 12 and begin with a decreasing subword of length k. Let π = σ(n + 1)τ be such a permutation of length n + 1. Obviously, the letters of τ must be in decreasing order since otherwise we have an occurrence of 3 − 12 in π starting from the letter (n+1). If |σ| = i then we can choose the letters of σ in \binom{n}{i} ways. Since the letters of τ are in decreasing order, they do not affect σ and thus there are B_{i,k} possibilities to choose σ. Also, if |σ| = k − 1 and the letters of σ are in decreasing order, we get \binom{n}{k−1} additional ways to choose π. Thus

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

This recurrence relation is identical to the one given in the proof of Proposition 4, and we get the desired result using that proof. □

Proposition 27.

E_{3−21}^{(k−1)(k−2)...1k}(n) = \{ \begin{matrix}0, & if k ≥ 4 \\ (e^{e^{x}}/(k − 1)!) ∫_{0}^{x} t^{k−1}e^{−e^{t}+t} dt, & if k = 2 or k = 3, \\ e^{e^{x}−1}, & if k = 1. \end{matrix}

Proof. If k ≥ 4 then the statement is true, since in this case the pattern (k − 1)(k − 2) … 1k does not avoid the pattern 3 − 21. In the other cases, we use the same arguments as we have in the proof of Proposition 26. The only difference is that instead of decreasing order in τ, we have increasing order. □

9. Conclusions

The goal of our paper is to give a complete description for the numbers of permutations avoiding a pattern of the form x−yz or xy −z and either beginning with one of the patterns 12 … k, k(k − 1) … 1, 23 … k1, (k − 1)(k − 2) … 1k, or ending with one of the patterns 12 … k, k(k − 1) … 1, 1k(k − 1) … 2, k12 … (k − 1). This description is given in Sections 5–8. However, some of our results can be generalized to beginning with a pattern belonging to Γ_{k}^{min} or Γ_{k}^{max}, and thus to the ending with a pattern belonging to Δ_{k}^{min} or Δ_{k}^{max} (see Section 2 for definitions). An example of such a generalisation is given in Theorem 28 below. This theorem generalizes Propositions 4 and 26 and can be proved by using the same considerations as we do in the proofs of these propositions. Theorem 28. Suppose p_{1}, p_{2} ∈ Γ_{k}^{min} and p_{1} ∈ S_{k}(1 − 23), p_{2} ∈ S_{k}(1 − 32). Thus, the complements C(p_{1}), C(p_{2}) ∈ Γ_{k}^{max} and C(p_{1}) ∈ S_{k}(1 − 23), C(p_{2}) ∈ S_{k}(3 − 12). Then, we have

E_{1−23}^{p_{1}}(x) = E_{3−21}^{C(p_{1})}(x) = E_{1−32}^{p_{2}}(x) = E_{3−12}^{C(p_{2})}(x) =

\{ \begin{matrix}(e^{e^{x}}/(k − 1)!) ∫_{0}^{x} t^{k−1}e^{−e^{t}+t} dt, & if k ≥ 2, \\ e^{e^{x}−1}, & if k = 1. \end{matrix}

Acknowledgments: The authors are grateful to Einar Steingímsson for his helpful suggestions and comments.

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.

[B] M. Bóna: The permutation classes equinumerous to the smooth class. Electron. J. Combin. 5 (1998), no. 1, Research Paper 31, 12 pp. (electronic).

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

[Claes] A. Claesson: Generalised Pattern Avoidance, European J. Combin. 22 (2001), 961-971. [ClaesMans] A. Claesson and T. Mansour: Permutations avoiding a pair of generalized 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.

[Ent] R. Entringer: A Combinatorial Interpretation of the Euler and Bernoulli Numbers, Nieuw. Arch. Wisk. 14 (1966), 241–246.

[Kit1] S. Kitaev: Multi-avoidance of generalised patterns, Discrete Math., to appear (2002).

[Kit2] S. Kitaev: Partially ordered generalized patterns, Discrete Math., to appear (2002).

[Kit3] S. Kitaev: Generalized pattern avoidance, 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).

[Kr] C. Krattenthaler: Permutations with restricted patterns and Dyck paths, Adv. in Appl. Math. 27 (2001), 510–530.

[K] D. Kremer: Permutations with forbidden subsequnces and a generalized Schröder number, Discrete Math. 218 (2000), 121–130.

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

[Mans3] T. Mansour: Restricted 1-3-2 permutations and generalized patterns, Annals of Combinatorics 6 (2002), 1–12.

[MV1] T. Mansour and A. Vainshtein: Restricted permutations, continued fractions, and Chebyshev polynomials, Electron. J. Combin. 7 (2000) no. 1, Research Paper 17, 9 pp. (electronic).

[MV2] T. Mansour and A. Vainshtein: Restricted 132-avoiding permutations, Adv. in Appl. Math. 126 (2001), no. 3, 258–269.

[MV3] T. Mansour and A. Vainshtein: Layered restrictions and Chebyshev polynomials, Annals of Combinatorics 5 (2001), 451–458.

[MV4] T. Mansour and A. Vainshtein: Restricted permutations and Chebyshev polyonomials, Séminaire Lotharingien de Combinatoire 47 (2002), Article B47c.

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

[RWZ] A. Robertson, H. Wilf, and D. Zeilberger: Permutation patterns and continued fractions, Electron. J. Combin. 6 (1999), no. 1, Research Paper 38, 6 pp. (electronic).

[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, Vol. 1, Cambridge University Press, (1997).

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

[W] J. West: Generating trees and forbidden subsequences, Discrete Math. 157 (1996), 363–372.

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

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

LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France

   E-mail address: toufik@labri.fr