THE ENUMERATION OF PERMUTATIONS WITH A PRESCRIBED NUMBER OF “FORBIDDEN” PATTERNS

John Noonan and Doron Zeilberger

Abstract. We initiate a general approach for the fast enumeration of permutations with a prescribed number of occurrences of ‘forbidden’ patterns, that seems to indicate that the enumerating sequence is always P-recursive. We illustrate the method completely in terms of the patterns ‘abc’,‘cab’ and ‘abcd’.

0. Introduction

The only increasing permutation on {1, 2, …, n}, [1, 2, …, n], has the property that it has no decreasing subsequence of length 2, i.e. there are no i and j such that 1 ≤ i < j ≤ n, and π[i] > π[j]. Thus one measure of how scrambled a permutation is, is its number of inversions, inv(π), which is the number of occurrences of the ‘pattern’ ba.

This can be generalized to an arbitrary set of patterns. Given a permutation on {1, …, n}, we define a pattern as a permutation on {1, …, r} where r ≤ n. For r ≤ n, we say that a permutation σ ∈ S_{n} has the pattern π ∈ S_{r} if there exist 1 ≤ i_{1} < i_{2} < ⋯ < i_{r} ≤ n such that π ≡ [σ(i_{1}), σ(i_{2}), …, σ(i_{r})] in reduced form.

The reduced form of a permutation σ on a set {j_{1}, j_{2}, …, j_{n}} where j_{1} < j_{2} < ⋯ < j_{n} is the permutation σ_{1} ∈ S_{n} obtained by renaming the objects of the permutation σ in the obvious way, so that j_{1} is renamed 1 and j_{2} is renamed 2 and so on. Thus the reduced form of the permutation 25734 is 14523 and the reduced form of 579 is 123.

To simplify things, when discussing a particular pattern, we will use its alphabetic equivalent. Thus an increasing subsequence of length 3 is an abc pattern, an inversion is a ba pattern and a decreasing subsequence of length 4 is a dcba pattern. Other patterns we will discuss include abcd, bac and cab.

The number of permutations which contain no increasing subsequence of length three (i.e. abc avoiding) is known to be C_{n} := \frac{1}{n+1} \binom{2n}{n}, the Catalan numbers. It is also known [6] that given any pattern of length three, the number of permutations avoiding that pattern is also C_{n}.

Herb Wilf raised the question: For any pattern π, what can you say about a_{π}(n), the number of permutations on {1 … n} that avoid the pattern π?

It follows from the Robinson-Schenstead algorithm and the hook-length formula[3] that for any r, the number of permutations with no increasing subsequence of length r, is a certain binomial-coefficient multisum, from which it follows immediately [8] that it is P-recursive (holonomic) (i.e., it satisfies a linear recurrence with polynomial coefficients in n).

Typeset by AMS-TEX

A natural conjecture is: For any given finite set of patterns, P AT, the sequence

a_{P AT} (n) := |{σ ∈ S_{n} : σ has no occurrences of the given patterns}|

is P -recursive. More generally, for any such set of patterns P AT = {pat_{1}, pat_{2}, …, pat_{r}} and any specified sequence of integers m_{p}, one for each pattern p ∈ P AT,

a_{P AT}^{{m_{1},m_{2},...,m_{r}}}(n) := |{σ ∈ S_{n} : σ has exactly m_{i} occurrences of the pattern pat_{i}, 1 ≤ i ≤ r}|,

is P-recursive.

In this paper, we will present a method for the ‘fast’ (polynomial time in n) enumeration of such sequences a(n), that seems to support our conjecture that it should always be P-recursive (holonomic) in n.

Until later in the paper, we will consider only one pattern, as the main ideas are already present there. The natural object is the generating function:

F_{n}^{π}(q) = ∑_{σ∈S_{n}} q^{φ(σ)} = ∑ c_{i}(n)q^{i}

where φ(σ) denotes the number of subsequences, x_{1}x_{2} … x_{r}, present in σ that reduce to the given pattern π. We will later show how to derive a recursive functional equation, from which it should be possible to extract efficient recurrences for the coefficients c_{i}(n) of F_{n}^{π}(q) for small i. As we said above, our approach seems to indicate that each c_{i}(n) is P -recursive in n. It is easy to see that it cannot be also P −recursive in i.

Another possibility is to expand the polynomials around q = 1, so that we have

F_{n}^{π}(q) = ∑_{i=0}^{degree} b_{i}(n)(q − 1)^{i}.

Here b_{0}(n) is the total number of permutations, n!. b_{1}(n) is the total number of π = x_{1}x_{2} … x_{r} patterns present in all the permutations of set S_{n}. The average number of x_{1}x_{2} … x_{r} patterns present in the permutations on \{1 … n\} would simply be \frac{b_{1}(n)}{n!}. It is easy to see [9] that it is always a polynomial in n, as are all the other coefficients b_{i}(n), for each fixed i. Thus, we can compute the first few coefficients b_{i}(n) of F_{n}^{π}(q +1) by brute force. However to get the full F_{n}^{π}(q) we would need the full F_{n}^{π}(q + 1), and the coefficients b_{i}(n), while always polynomials in n, get increasingly complicated as i grows bigger.

Instead we will answer a more general question: How many permutations on {1 … n} avoid π = x_{1}x_{2} … x_{r} and {π_{i}}_{i=1}^{m} where {π_{i}} is a set of other forbidden patterns for which one or more of the entries in the forbidden subsequence is specified. Among the π_{i} might be the pattern ab4 which simply describes an abc pattern in which the last entry is 4. Another might be a 3b pattern which would be a non-inversion in which the first entry is 3.

Once we have such a method, we would also like to compute the number of permutations of a given size which avoid a given set of patterns and compute the number of permutations of a given size which have occurences of patterns from the given set, a prescribed number of times. We may ask how many permutations on {1 … n} avoid both abc and cab?; how many avoid abc and have exactly 1 cab?; etc.

THE ENUMERATION OF PERMUTATIONS WITH A PRESCRIBED NUMBER OF “FORBIDDEN” PATTERNS 3

1 Counting Permutations with a Presribed Number of abc Patterns 1.0 Definitions

Definition 1.1. Given σ ∈ S_{n}, an abc pattern is a sequence i, j, k where 0 < i < j < k ≤ n and σ(i) < σ(j) < σ(k). Definition 1.2. φ_{abc}(σ):= the number of abc patterns of σ.

For example φ_{abc}(4321) = 0, φ_{abc}(1234) = 4, and φ_{abc}(2314) = 1. Definition 1.3. Given σ ∈ S_{n}, an aj pattern is a sequence i, k where 0 < i < k ≤ n and σ(i) < σ(k) = j.

For example φ_{4}(15342) = 2. Definition 1.4. φ_{j}(σ) := the number of aj patterns of σ. Definition 1.5. P^{(r)}(n, I) is the number of permutations on {1 … n} with exactly r abc patterns and no aj patterns for j ≤ I.

We will use P (n, I) to denote P^{(0)}(n, I), i.e. the number of permutations on {1 … n} with no abc patterns and no aj patterns for j ≤ I.

Using the above definitions, the polynomial F_{n}^{π}(q) described earlier would for this example be defined as

F_{n}^{123}(q) := ∑_{σ∈S_{n}} q^{φ_{abc}(σ)}.

So, e.g., F_{1}^{123}(q) = 1 , F_{2}^{123}(q) = 2 , F_{3}^{123}(q) = 5 + q , F_{4}^{123}(q) = 14 + 6q + 3q^{2} + q^{4}. Definition 1.6. For σ ∈ S_{n}, define:

wt(σ) := q^{φ_{abc}(σ)}q_{2}^{φ_{2}(σ)}q_{3}^{φ_{3}(σ)}q_{4}^{φ_{4}(σ)} … q_{n}^{φ_{n}(σ)}.

For example, wt(2314) = q^{1}q_{2}^{0}q_{3}^{1}q_{4}^{3} = qq_{3}q_{4}^{3}. Definition 1.7.

P_{n}(q_{2}, q_{3}, …, q_{n}; q) := ∑_{σ∈S_{n}} wt(σ).

P_{n} is the ‘generalized’ form of F_{n}^{123}. Comparing the two we see that F_{n}^{123}(q) = P_{n}(1, 1 …, 1; q).

1.1 The functional equation

In order to illustrate the present method, we will treat the simplest non-trivial case, by rederiving the well-known formula for the number of permutations on {1 … n} with no abc patterns by first obtaining a method to compute the number of permutations on {1 … n} with no abc patterns and no aj patterns for j < I where I is any integer between 0 and n. We then merely set I = 0 and obtain the desired sequence.

4 JOHN NOONAN AND DORON ZEILBERGER

In order to find explicit or recursive descriptions for the coefficients of F_{n}^{123}, we will establish a recursive functional equation for P_{n}. Let σ ∈ S_{n}, σ(n) = i ≠ 1. Let σ_{1} be the permutation on {1..i − 1, i + 1..n} obtained by removing the last entry of σ, i.e.

σ_{1}(j) := σ(j), 1 ≤ j ≤ n − 1.

Then

wt(σ) = wt(σ_{1})q_{i}^{i−1}q^{∑_{j=2}^{i−1} φ_{j}(σ_{1})},

hence

wt(σ) = q^{φ_{abc}(σ)} ∏_{j=1}^{n} q_{j}^{φ_{j}(σ)} = q^{abc(σ_{1})}q_{i}^{i−1} ∏_{j<i}(qq_{j})^{φ_{j}(σ_{1})} ∏_{j>i} q_{j}^{φ_{j}(σ_{1})}.  (1)

If σ(n) = 1, then defining σ_{1} as above with i = 1, we have

wt(σ) = wt(σ_{1}).

Summing over all σ ∈ S_{n} on the left hand side of (1) is equivalent to summing first over i, then over σ_{1} ∈ S_{n−1} on the right. Making the necessary shift in variables to account for the fact that σ_{1} above is a permutation on [1, .., i − 1, i + 1, .., n], we have

\begin{aligned}∑_{σ∈S_{n}} wt(σ) = ∑_{i=1}^{n} ∑_{{σ(n)=i \atop σ∈Sn}} wt(σ) & = ∑_{σ_{1}∈S_{n−1}^{(1)}} wt(σ_{1}) \\ & + ∑_{i=2}^{n} ∑_{σ_{1}∈S_{n−1}^{(i)}} q_{i}^{i−1} [ ∑_{σ_{1}∈S_{n−1}} q^{abc(σ_{1})} ∏_{j<i}(qq_{j})^{φ_{j}(σ_{1})} ∏_{j>i} q_{j}^{φ_{j}(σ_{1})}] \end{aligned}

where S_{n−1}^{(i)} is the set of permutations on {1, 2, …, i − 1, i + 1, …, n − 1, n}.

Hence

P_{n}(q_{2}, q_{3}, …, q_{n}; q) = P_{n−1}(q_{3}, q_{4}, …, q_{n}; q) + ∑_{i=2}^{n} q_{i}^{i−1}P_{n−1}(qq_{2}, qq_{3}, …, qq_{i−1}, q_{i+1}, …, q_{n}; q). (2)

This recurrence for P_{n} is the basis for all that follows.

1.2 A recurrence for P (n, I)

We note that from our definition of P_{n}, P_{n}(\overbrace{0, 0, …, 0}^{I−1}, \overbrace{1, …, 1}^{n−I−1}; 0) is the number of permutations on \{1 … n\} with no abc patterns and no aj patterns for j ≤ I. So P_{n}(1, 1, …, 1; 0) is a_{123}(n), the number of permutations

on n elements with no abc patterns, and P_{n}(\overbrace{0, 0, …, 0}^{I−1}, \overbrace{1, …, 1}^{n−I−1}; 0) = P (n, I). We first tackle the question of a recurrence for a_{123}(n) = P_{n}(1, 1, …, 1; 0). Using (2), we have

P_{n}(1, 1, …, 1; 0) = P_{n−1}(1, 1, …, 1; 0) + ∑_{i=2}^{n} P_{n−1}(\overbrace{0, 0, …, 0}^{i−2}, \overbrace{1, …, 1}^{n−i−1}; 0).  (3)

THE ENUMERATION OF PERMUTATIONS WITH A PRESCRIBED NUMBER OF “FORBIDDEN” PATTERNS 5

It would be too much to hope for a nice clean recurrence on the first try, we seem to have picked up a few uninvited guests, namely the P_{n−1}(0, 0, …, 0, 1, …, 1; 0). By (2) again,

P_{n}(\overbrace{0, 0, …, 0}^{I−1}, \overbrace{1, …, 1}^{n−I−1}; 0) = P_{n−1}(\overbrace{0, 0, …, 0}^{I−2}, \overbrace{1, …, 1}^{n−I−1}; 0) + ∑_{i=I+1}^{n} P_{n−1}(\overbrace{0, 0, …, 0}^{i−2}, \overbrace{1, …, 1}^{n−i−1}; 0).  (4)

In terms of P (n, I), (4) becomes

P (n, I) = P (n − 1, I − 1) + ∑_{i=I+1}^{n} P (n − 1, i − 1) = ∑_{i=I}^{n} P (n − 1, i − 1).  (5)

The number of permutations on n elements with no abc patterns is P_{n}(1, 1, …, 1; 0) = P (n, 1) = a_{123}(n). Unfortunately when we try to use (5) to find P (n, 1) we are required to define P (n, 0). To do so, one needs only look as far as (2). By (2), we have

P (n, 1) = P (n − 1, 1) + ∑_{i=2}^{n} P (n − 1, i − 1).

Comparing this with (5) we see that we should define P (n, 0) = P (n, 1). Using this definition, (5) is valid for n ≥ 1, i > 0. To complete the scheme, we need some form of initial conditions. These are readily supplied by the observation that the number of permutations on n elements with no abc patterns and no aj patterns 2 ≤ j ≤ n is 1, namely the permutation [n, n − 1, …, 3, 2, 1], so P (n, n) = 1.

Finally, we may simplify (5) by examining P (n, I) − P (n, I + 1) = ∑_{i=I}^{n} P (n − 1, i − 1) − ∑_{i=I+1}^{n} P (n − 1, i − 1) = P (n − 1, I − 1) which gives us

P (n, I) = \{ \begin{matrix}1, & if n = I \\ P (n, 1), & if I = 0 \\ P (n, I + 1) + P (n − 1, I − 1), & otherwise \end{matrix}  (6)

Using this recurrence, we may quickly generate a large number of P (n, I).

Table 1 Values of P (n, I)

n I=0 1 2 3 4 5 6 7
0  1
1  1  1
2  2  2  1
3  5  5  3  1
4  14  14  9  4  1
5  42  42  28  14  5  1
6  132  132  90  48  20  6  1
7  429  429  297  165  75  27  7  1
8  1430  1430  1001  572  275  110  35  8
9  4862  4862  3432  2002  1001  429  154  44
10  16796  16796  11934  7072  3640  1638  637  208

6 JOHN NOONAN AND DORON ZEILBERGER

This enables us to conjecture, and immediately prove (by verifying (6) and the initial conditions), the closed form P (n, I) = \frac{I+1}{n+1} \binom{2n−I}{n}, the celebrated ballot numbers[3]. Evaluating at I = 1 yields yet another proof of the well known fact that the number of permutations on {1 … n} with no abc patterns, a_{123}(n), equals C_{n}, the Catalan number. This proof is longer and far less elegant than the combinatorial proofs of [6]. Its only virtue is that it illustrates a general method.

1.3 The number of permutations with exactly one abc pattern.

Recently one of us [4] proved that the number of permutations on {1 … n} with exactly one abc pattern is \frac{3}{n} \binom{2n}{n+3}. We will now present an alternative proof using the present method.

The number of permutations with exactly one abc pattern is the constant term of the derivative of the function F = ∑_{σ∈S_{n}} q^{φ_{abc}(σ)}. By differentiating (2) with respect to q, we find a recurrence for \frac{∂}{∂q} P_{n},

\frac{∂}{∂q} P_{n}(q_{2}, …, q_{n}; q) = \frac{∂}{∂q} P_{n−1}(q_{3}, …, q_{n}; q) + ∑_{i=2}^{n} q_{i}^{i−1} \frac{∂}{∂q} P_{n−1}(qq_{2}, qq_{3}, …, qq_{i−1}, q_{i+1}, …, q_{n}; q). (7)

Here things begin to get a bit tricky and we will need to employ the chain rule. We will evaluate the right side of the above equation in terms of partial derivatives with respect to the positions that q occupies. For example,

\frac{∂}{∂q} P_{3}(qq_{2}, q_{3}; q) = q_{2} \frac{∂}{∂q_{2}} P_{3}| \begin{matrix}q_{2} → qq_{2} \\ q_{3} → q_{3} \\ q → q \end{matrix} + \frac{∂}{∂q} P_{3}| \begin{matrix}q_{2} → qq_{2} \\ q_{3} → q_{3} \\ q → q \end{matrix} .

The preceding notation means: “first find the partial derivative of the function P_{3} then make the necessary substitutions for q_{i}.” Continuing we have

\frac{∂}{∂q} P_{n}(q_{2},q_{3}, …, q_{n}; q) = \frac{∂}{∂q} P_{n−1}(q_{3}, q_{4}, …, q_{n}; q)
+ ∑_{i=2}^{n} q_{i}^{i−1} [\frac{∂}{∂q} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} + ∑_{j=2}^{i−1} q_{j} \frac{∂}{∂q_{j}} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} ] .  (8)

We are now ready to tackle \frac{∂}{∂q} P_{n}| \begin{matrix}q → 0 \\ q_{i} → 1, 2≤i≤n \end{matrix}

\begin{aligned}\frac{∂}{∂q} P_{n} & | \begin{matrix}q_{k}→1, 2≤k≤n \\ q→0 \end{matrix} \\ & = \frac{∂}{∂q} P_{n−1}| \begin{matrix}q_{k}→1, 2≤k≤n−1 \\ q→0 \end{matrix} + ∑_{i=2}^{n} [\frac{∂}{∂q} P_{n−1}| \begin{matrix}q_{k}→0, 2≤k<i \\ q_{k}→1, i≤k≤n−1 \\ q→0 \end{matrix} + ∑_{j=2}^{i−1} \frac{∂P_{n−1}}{∂q_{j}} | \begin{matrix}q_{k}→0, 2≤k<i \\ q_{k}→1, i≤k≤n−1 \\ q→0 \end{matrix} ] . \end{aligned}

It is readily seen that P^{(1)}(n, I), the number of permutations on {1 … n} with exactly one abc pattern and no aj patterns for j ≤ I can be expressed as:

P^{(1)}(n, I) = \frac{∂}{∂q} P_{n}| \begin{matrix}q_{k} → 0, 2 ≤ k < I + 1 \\ q_{k} → 1, I + 1 ≤ k ≤ n \\ q → 0 \end{matrix} .

THE ENUMERATION OF PERMUTATIONS WITH A PRESCRIBED NUMBER OF “FORBIDDEN” PATTERNS 7

Furthermore, to simplify notation, let

P_{j}^{(1)}(n, I) := \frac{∂P_{n}}{∂q_{j}} | \begin{matrix}q_{k} → 0, 2 ≤ k < I + 1 \\ q_{k} → 1, I + 1 ≤ k ≤ n \\ q → 0 \end{matrix} .

The actual meaning of P_{j}^{(1)}(n, I) is immaterial, but the astute reader will see that combinatorially, P_{j}^{(1)}(n, I) is the number of permutations on {1 … n} with no abc patterns, no ak patterns for k ≤ I, k ≠ j, and exactly 1 aj pattern if j ≤ I or at least one aj pattern if j > I. The recurrence for P^{(1)}(n, I) follows from (8):

P^{(1)}(n, I) = P^{(1)}(n − 1, I − 1) + ∑_{i=I+1}^{n} [P^{(1)}(n − 1, i − 1) + ∑_{j=I+1}^{i−1} P_{j}^{(1)}(n − 1, i − 1)] .  (9)

Disregarding for a moment that we do not yet know what P_{j}^{(1)}(n, I) is, we can state ‘initial’ conditions for this recurrence. First we should define P^{(1)}(n, 0) = P^{(1)}(n, 1). We can easily compute P^{(1)}(n, n − 2). P^{(1)}(n, n−2) is the number of permutations on {1 … n} with exactly 1 abc pattern and no aj patterns for j ≤ n−2. If σ is one such permutation then σ has the form [n−2, n−1, n−3, …, n−i, n, n−i−1, …, 2, 1], for some i. There are exactly n − 2 such permutations, hence P^{(1)}(n, n − 2) = n − 2. Our ‘initial’ conditions (perhaps they should be called ‘boundary’ conditions) for this recurrence are P^{(1)}(n, 0) = P^{(1)}(n, 1), P^{(1)}(n, n − 2) = n − 2.

To obtain a recurrence for P_{j}^{(1)}(n, I) we must return to (2) and take the partial derivative with respect to q_{j}. We begin for the case when j ≥ 3.

\frac{∂}{∂q_{j}} P_{n}(q_{2}, …, q_{n}; q)

= \frac{∂}{∂q_{j−1}} P_{n−1}| \begin{matrix}q_{k} → q_{k+1} \\ q → q \end{matrix} + ∑_{i=2}^{j−1} q_{i}^{i−1} \frac{∂}{∂q_{j−1}} P_{n−1}| \begin{matrix}q_{k} → qq_{k}, 2 ≤ k < i \\ q_{k} → q_{k+1}, i < k ≤ n − 1 \\ q → q \end{matrix}

+ ∑_{i=j+1}^{n} qq_{i}^{i−1} \frac{∂}{∂q_{j}} P_{n−1}| \begin{matrix}q_{k} → qq_{k}, 2 ≤ k < i \\ q_{k} → q_{k+1}, i < k ≤ n−1 \\ q → q \end{matrix} +(j−1)q_{j}^{j−2}P_{n−1}(qq_{2}, …, qq_{j−1}, q_{j+1}, …, q_{n}; q) .

For j ≥ 3 it follows that

P_{j}^{(1)}(n, I) = P_{j−1}^{(1)}(n − 1, I − 1) + ∑_{i=I+1}^{j−1} P_{j−1}^{(1)}(n − 1, i − 1) + (j−1)χ(j > I)P (n − 1, j − 1).

where χ(statement) = { 0, statement is false 1, statement is true . We see that in (9), we only need to know the values of P_{j}^{(1)}(n, I) for which j ≤ I so we have

P_{j}^{(1)}(n, I) = P_{(j−1)}^{(1)}(n − 1, I − 1).  (10)

When j = 2 we have

P_{2}^{(1)}(n, I) = \frac{∂}{∂q_{2}} P_{n}| \begin{matrix}q_{k} → 0, 2 ≤ k < I + 1 \\ q_{k} → 1, I ≤ k ≤ n \\ q → 0 \end{matrix} = P_{n−1}(\overbrace{0, …, 0}^{I−2}, \overbrace{1, …, 1}^{n−I}; 0)
= P (n − 1, I − 1)  (11)

8 JOHN NOONAN AND DORON ZEILBERGER

Using (11), the recurrence (10) simplifies to

\begin{aligned}P_{j}^{(1)}(n, I) & = P_{j−1}^{(1)}(n − 1, I − 1) = P_{j−2}^{(1)}(n − 2, I − 2) = ⋯ = P_{2}^{(1)}(n − j + 2, I − j + 2) \\ & = P (n − j + 1, I − j + 1). \end{aligned}

Now we can summarize our results so far in a recurrence for P^{(1)}(n, I) (see (9)).

P^{(1)}(n, I) = ∑_{i=I}^{n} [P^{(1)}(n − 1, i − 1) + ∑_{j=I+1}^{i−1} P (n − j, i − j)] .  (12)

From (12) it follows that

P^{(1)}(n, I) − P^{(1)}(n, I + 1) = P^{(1)}(n − 1, I − 1) + ∑_{i=I}^{n} ( ∑_{j=I+1}^{i−1} P (n − j, i − j) − ∑_{j=I+2}^{i−1} P (n − j, i − j))

= P^{(1)}(n − 1, I − 1) + ∑_{i=I+2}^{n} P (n − I − 1, i − I − 1)

= P^{(1)}(n − 1, I − 1) + P (n − I, 2).

The last equation follows from (5). Finally we have the following recursion for P^{(1)}(n, I):

P^{(1)}(n, I) = \{ \begin{matrix}P^{(1)}(n, 1), & if I = 0 \\ n − 2, & if I = n − 2 \\ P^{(1)}(n, I + 1) + P^{(1)}(n − 1, I − 1) + P (n − I, 2), & otherwise \end{matrix}

Table 2 Values of P^{(1)}(n, I)

n I=0 1 2 3 4 5 6 7 8 9 10
0  0
1  0  0
2  0  0  0
3  1  1  0  0
4  6  6  2  0  0
5  27  27  12  3  0  0
6  110  110  55  19  4  0  0
7  429  429  229  91  27  5  0  0
8  1638  1638  912  393  136  36  6  0  0
9  6188  6188  3549  1614  612  191  46  7  0  0
10  23256  23256  13636  6447  2601  897  257  57  8  0  0

From this, one conjectures that P^{(1)}(n, I) is given by the expression

g(n, I) := \binom{2n−I−1}{n}−\binom{2n−I−1}{n+3}+\binom{2n−2I−2}{n−I−4}−\binom{2n−2I−2}{n−I−1}+\binom{2n−2I−3}{n−I−4}−\binom{2n−2I−3}{n−I−2}.

Since it is readily verified that g(n, I) also satisfies the same recurrence and initial conditions, we have a rigorous proof that P^{(1)}(n, I) = g(n, I). Plug in I = 1 and we find that a_{123}^{(1)}(n) = g(n, 1) = \frac{3}{n} \binom{2n}{n+3} as first proved in [4].

THE ENUMERATION OF PERMUTATIONS WITH A PRESCRIBED NUMBER OF “FORBIDDEN” PATTERNS 9

1.4 The number of permutations with exactly 2 abc patterns

We now will compute a_{123}^{(2)} = the number of permutations in S_{n} containing exactly two increasing subsequences of length 3. If

F_{n}^{123} = ∑_{σ∈S_{n}} q^{φ_{abc}(σ)} = a_{123}(n) + a_{123}^{(1)}(n)q + a_{123}^{(2)}(n)q^{2} + …

then

\frac{d^{2}F_{n}^{123}}{dq^{2}} = 2a_{123}^{(2)}(n) + 6a_{123}^{(3)}(n)q + ….

So a_{123}^{(2)}(n) is half the constant term of \frac{d^{2}F_{n}^{123}}{dq^{2}} . Similarly, by our definition of P^{(r)}(n, I) (definition 1.5), we see that

P^{(2)}(n, I) = \frac{1}{2}Φ^{(2)}(n, I).

where

Φ^{(2)}(n, I) := \frac{∂^{2}}{∂q^{2}} P_{n}| \begin{matrix}q_{k}→0, 2≤k<i \\ q_{k}→1, i≤k≤n−1 \\ q→0 \end{matrix} .

We will find a recursive formula for Φ^{(2)}(n, I).

From (8), we have

\frac{∂^{2}}{∂q^{2}} P_{n}(q_{2}, q_{3}, …, q_{n}; q) = \frac{∂^{2}}{∂q^{2}} P_{n−1}(q_{3}, q_{4}, …, q_{n}; q)

+ ∑_{i=2}^{n} q_{i}^{i−1} [\frac{∂^{2}}{∂q^{2}} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} + ∑_{j=2}^{i−1} q_{j} \frac{∂}{∂q_{j}} \frac{∂}{∂q} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix}

+ ∑_{j=2}^{i−1} q_{j} (\frac{∂}{∂q} \frac{∂}{∂q_{j}} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} + ∑_{m=2}^{i−1} q_{m} \frac{∂}{∂q_{m}} \frac{∂}{∂q_{j}} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} )] .(13)

Let Φ_{(1,j)}^{(2)}(n, I) = \frac{∂}{∂q} \frac{∂}{∂q_{j}} P_{n}| \begin{matrix}q_{k}→0, 2≤k<i \\ q_{k}→1, i≤k≤n−1 \\ q→0 \end{matrix} and Φ_{(j,m)}^{(2)}(n, I) = \frac{∂^{2}}{∂q_{j}} \frac{∂}{∂q_{m}} P_{n}| \begin{matrix}q_{k}→0, 2≤k<i \\ q_{k}→1, i≤k≤n−1 \\ q→0 \end{matrix} . Then

from (13) it follows that

Φ^{(2)}(n, I) = ∑_{i=I}^{n} [Φ^{(2)}(n − 1, i − 1) + ∑_{j=I+1}^{i−1} (2Φ_{(1,j)}^{(2)}(n − 1, i − 1) + ∑_{m=I+1}^{i−1} Φ_{(j,m)}^{(2)}(n − 1, i − 1))] .

Subtracting successive terms:

Φ^{(2)}(n, I) − Φ^{(2)}(n, I + 1) = Φ^{(2)}(n − 1, I − 1)

+ ∑_{i=I+2}^{n} [Φ_{(I+1,I+1)}^{(2)}(n − 1, i − 1) + 2Φ_{(1,I+1)}^{(2)}(n − 1, i − 1)]

+ ∑_{i=I+2}^{n} ∑_{j=I+2}^{i−1} 2Φ_{(I+1,j)}^{(2)}(n − 1, i − 1)  (14)

10 JOHN NOONAN AND DORON ZEILBERGER

We note now that to compute Φ^{(2)}(n, I) we must also compute Φ_{(1,j)}^{(2)}(n, I) and Φ_{(m,j)}^{(2)}(n, I), but we do not need to compute these for all n, I, j, m. We need only compute them for j, m ≤ I. We use (8) to obtain a recursive formula for Φ_{(1,j)}^{(2)}(n, I), j ≤ I.

\frac{∂}{∂q} \frac{∂}{∂q_{j}} P_{n}(q_{2}, q_{3}, …, q_{n}; q)

= ∑_{i=2}^{j−1} q_{i}^{i−1} [ ∑_{m=2}^{i−1} q_{m} \frac{∂}{∂q_{m}} \frac{∂}{∂q_{j−1}} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} + \frac{∂}{∂q} \frac{∂}{∂q_{j−1}} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} ]

+ q ∑_{i=j+1}^{n} q_{i}^{i−1} [ ∑_{m=2}^{i−1} q_{m} \frac{∂}{∂q_{m}} \frac{∂}{∂q_{j}} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} + \frac{∂}{∂q} \frac{∂}{∂q_{j}} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} ]

+ (j − 1)q_{j}^{j−2} [∑_{i=2}^{j−1} q_{i} \frac{∂}{∂q_{i}} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<j \\ q_{k}→q_{k+1}, j ≤ k<n \\ q→q \end{matrix} + \frac{∂}{∂q} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<j \\ q_{k}→q_{k+1}, j ≤ k<n \\ q→q \end{matrix} ]

+ ∑_{i=j+1}^{n} q_{i}^{i−1} \frac{∂}{∂q_{j}} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} + \frac{∂}{∂q} \frac{∂}{∂q_{j−1}} P_{n−1}| \begin{matrix}q_{k} → q_{k+1} \\ q → q \end{matrix}  (15)

From this, we have

Φ_{(1,j)}^{(2)}(n, I) = \{ \begin{matrix}∑_{i=I+1}^{n} P_{(2)}^{(1)}(n − 1, i − 1) + P^{(1)}(n − 1, I − 1), & if j = 2 \\ ∑_{i=I+1}^{n} P_{(j)}^{(1)}(n − 1, i − 1) + Φ_{(1,j−1)}^{(2)}(n − 1, I − 1), & if 2 < j ≤ I \end{matrix}

where P_{(j)}^{(1)}(n, I) = \frac{∂}{∂q_{j}} P_{n}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<I \\ q_{k}→q_{k+1}, I ≤ k<n \\ q→q \end{matrix} . This recurrence can be further simplified using (12) to

Φ_{(1,j)}^{(2)} = P^{(1)}(n − j + 1, I − j + 1) + ∑_{k=2}^{j} ( ∑_{i=I+k−j+1}^{n−j+k} P (n − j, i − k)) , for j ≤ I.  (16)

We may do the same for Φ_{(m,j)}^{(2)}(n, I) and obtain

Φ_{(m,j)}^{(2)}(n, I) = \{ \begin{matrix}0, & if j = m = 2 \\ 2P (n − 1, I − 1), & if j = m = 3 ≤ I \\ Φ_{(j−1,j−1)}^{(2)}(n − 1, I − 1), & if j = m ≤ I \\ P_{(j−1)}^{(1)}(n − 1, I − 1), & if j > m = 2 \\ Φ_{(m−1,j−1)}^{(2)}(n − 1, I − 1), & if j > m, m ≤ I \end{matrix}

which collapses down to the 3 cases

Φ_{(m,j)}^{(2)}(n, I) = \{ \begin{matrix}0, & if j = m = 2 \\ 2P (n − j + 1, I − j + 1), & if j = m ≤ I \\ P_{(j−m+1)}^{(1)}(n − m + 1, I − m + 1), & if j > m, m ≤ I \end{matrix} .  (17)

THE ENUMERATION OF PERMUTATIONS WITH A PRESCRIBED NUMBER OF “FORBIDDEN” PATTERNS 11

One might think that we have overlooked a few cases here, for what if j > m > I or j = m > I? Examining (14) it is apparent that to compute Φ^{(2)}(n, I), we need only compute Φ_{(m,j)}^{(2)} and Φ_{(1,j)}^{(2)} when j, m ≤ I. We now use (5),(12),(16) and (17) to simplify (14):

\begin{aligned}Φ^{(2)}(n, I) & = Φ^{(2)}(n − 1, I − 1) + Φ^{(2)}(n, I + 1) \\ & + 2P^{(1)}(n − I, 2) + 2IP (n − I, 3) + 2P (n − i − 1, 2) + χ(I > 1)2P (n − I + 1, 3) \end{aligned}

We may now make the substitution P^{(2)}(n, I) = \frac{1}{2}Φ^{(2)}(n, I). Our recurrence for P^{(2)}(n, I) can be stated as

P^{(2)}(n, I) = \{ \begin{matrix}P^{(2)}(n, 1), & if I = 0 \\ n − 3, & if I = n − 2 \\ P^{(2)}(n − 1, I − 1) + P^{(2)}(n, I + 1) + P^{(1)}(n − I, 2) \\ +P (n − i − 1, 2) + IP (n − I, 3) + χ(I > 1)P (n − I + 1, 3), & if 0 < I < n − 2, n > 3 \end{matrix} .

Table 3 Values of P^{(2)}(n, I)

n  I=0  1  2  3  4  5  6  7  8  9  10
0  0  0  0  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0  0  0  0
2  0  0  0  0  0  0  0  0  0  0  0
3  0  0  0  0  0  0  0  0  0  0  0
4  3  3  1  0  0  0  0  0  0  0  0
5  24  24  12  2  0  0  0  0  0  0  0
6  133  133  74  23  3  0  0  0  0  0  0
7  635  635  371  141  36  4  0  0  0  0  0
8  2807  2807  1688  709  227  51  5  0  0  0  0
9  11864  11864  7276  3248  1168  334  68  6  0  0  0
10  48756  48756  30340  14121  5459  1771  464  87  7  0  0

Using ordi of [10] or gfun[5] we conjecture that

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

It is very likely that one should be able to conjecture an explicit expression for P^{(2)}(n, I), which would be routine to prove, and from which the above conjecture would follow.

2 The Method

We may now outline the method described in this paper.

To determine the number of permutations on {1 … n} having exactly r occurrences of the pattern x_{1}x_{2} … x_{k},

12 JOHN NOONAN AND DORON ZEILBERGER

1. Determine the best way to obtain a recurrence for this pattern.

There are basically four ways to do this.

a) by removing the last entry of the permutation, as in the abc example.

b) by removing the first entry of the permutation, which is what we will do in the next example.

c) by removing n from the permutation.

d) by removing 1 from the permutation.

2. Identify the other parameters needed in order to describe the recurrence.

In our first example, we found a recurrence for the number of permutations with a given number of abc patterns by looking at what happened to a permutation from which we removed its last object. As a consequence, we were forced to consider the number of abc patterns present in each permutation, but also the number of aj patterns present. Note that we could arrive at this requirement by noting the result of removing the last object from the pattern abc. abc becomes ab. Since only some choices of b result in a true abc pattern for a given c, we must be specific, and count the number of aj patterns for every j. We count the number of aj by using the parameter q_{j} in our weight function.

3. Define P_{n} = ∑_{σ∈S_{n}} wt(σ).

Here wt(σ) = q^{φ}(σ) ∏ q_{j}^{φ_{j}(σ)} where φ_{j}(σ) is the number of times the pattern associated with q_{j} can be found in σ and φ(σ) is the number of x_{1}x_{2} … x_{r} in σ.

4. Determine the functional equation.

Using the recurrence described in 1, determine a recurrence in n for P_{n}.

5. Take the r^{th} derivative of the functional equation with respect to q.

6. Let q = 0, and q_{j} = 1 for all other parameters of P_{n}.

For all intents and purposes, you are now done, for you have obtained a (perhaps complicated) recurrence for the number of permutations on {1 … n} containing exactly k x_{1}x_{2} … x_{r}’s. This recurrence probably involves other terms, but each of these have their own recurrences which can be determined from the functional equation. After all is said and done, you frequently are able to simplify this recurrence, eliminating many of these unwanted terms, but for now, you have achieved your goal.

3 The forbidden pattern cab

3.1 Definitions

As with each of the examples we examine, the definitions for P, P^{(k)}, φ_{j} and wt should be taken as being local to the problem at hand.

Definition 3.1. Given σ ∈ S_{n}, a cab pattern is a sequence i, j, k where 1 ≤ i < j < k ≤ n and σ(j) < σ(k) < σ(i).

THE ENUMERATION OF PERMUTATIONS WITH A PRESCRIBED NUMBER OF “FORBIDDEN” PATTERNS 13

Definition 3.2. For σ ∈ S_{n}, let φ_{cab}(σ) be the number of cab patterns of σ.

The number of permutations on {1 … n} having no cab patterns will be the constant term of the polynomial F = ∑_{σ∈S_{n}} q^{φ_{cab}(σ)}. As we saw earlier, we may add any number of parameters to this polynomial, as long as we know what to do with them to obtain the constant term. In this case, we will use the parameters q_{2}, ..., q_{n} as we did with abc.

Definition 3.3. Given σ ∈ S_{n},

wt(σ) = q^{φ_{cab}(σ)} ∏_{j=2}^{n} q^{φ_{j}(σ)}.

3.2 No cab’s

Let σ(n) = i. A functional equation results from examining σ_{1}(k) = σ(k), 1 ≤ k < n,

wt(σ) = wt(σ_{1})q^{∑_{j<i} φ_{j}(σ_{1})} ∏_{j>i} q_{j}

Summing over all σ ∈ S_{n} we have

P_{n}(q, q_{2}, q_{3}, …, q_{n}) = ∑_{i=2}^{n} [(∏_{j>i} q_{j}) P_{n−1}(q, qq_{2}, …, qq_{i−1}, q_{i+1}, …, q_{n})] + (∏_{j} q_{j}) P_{n−1}(q, q_{3}, …, q_{n}).

(18)

Not surprisingly, if we let P (n, I) = P_{n}(0; \overbrace{0, 0, …, 0}^{I−1}, \overbrace{1, …, 1}^{n−I−1}), then we obtain the following recurrence for P (n, I),

P (n, I) = \{ \begin{matrix}1  , & if n = I \\ P (n, 1)  , & if I = 0 \\ P (n, I + 1) + P (n − 1, I − 1), & otherwise \end{matrix}

Which is identical to (6). So we have reproved that the number of permutations on {1 … n} with no abc subsequences is equal to the number with no cab subsequences.

3.3 Permutations with one cab

Though the number of permutations with no abc’s is equal to the number with no cab’s, we will find that this is not the case when we examinee the number of permutations with one cab. we follow the same procedure outlined for the abc case, with the goal of finding \frac{∂}{∂q} P_{n}| \begin{matrix}q → 0 \\ q_{j} → 1, 1 ≤ j ≤ n \end{matrix} . Taking derivatives

of both sides of (18) with respect to q, we have

\begin{aligned}\frac{∂}{∂q} P_{n} & = ∑_{i=1}^{n} (∏_{j>i} q_{j}) [∑_{j=2}^{i−1} q_{j} \frac{∂}{∂q_{j}} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} + \frac{∂}{∂q} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} ] \\ & + (∏_{j} q_{j}) \frac{∂}{∂q} P_{n−1}| \begin{matrix}q → q \\ q_{k} → q_{k+1}, 1 ≤ k ≤ n − 1 \end{matrix} . \end{aligned}

We do the same for the derivative with respect to q_{j}:

\begin{aligned}\frac{∂}{∂q_{j}} P_{n} & = ∑_{i=2}^{j−1} (∏_{{k>i \atop k≠j}} q_{k}) P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} + ∑_{i=1}^{j−1} (∏_{k>i} q_{k}) \frac{∂}{∂q_{j−1}} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} \\ & + ∑_{i=j+1}^{n} (∏_{k>i} q_{k}) q \frac{∂}{∂q_{j}} P_{n−1}| \begin{matrix}q_{k}→qq_{k}, 2 ≤ k<i \\ q_{k}→q_{k+1}, i ≤ k<n \\ q→q \end{matrix} . \end{aligned}

Here we let P^{(1)}(n, I) = \frac{∂}{∂q} P_{n}| \begin{matrix}q → 0 \\ q_{k} → 0, k ≤ I \\ q_{k} → 1, k > I \end{matrix} and P_{(j)}^{(1)}(n, I) = \frac{∂}{∂q_{j}} P_{n}| \begin{matrix}q → 0 \\ q_{k} → 0, k ≤ I \\ q_{k} → 1, k > I \end{matrix} . We obtain the

following recursions:

P_{(j)}^{(1)}(n, I) = \{ \begin{matrix}0, & if n − I < 0 or j < I \\ P_{(j)}^{(1)}(n, 1), & if I = 0 \\ P (n − 1, I − 1), & if j = I \\ ∑_{k=i}^{j−1} P (n − 1, k − 1), & if j > I \end{matrix} ,

P^{(1)}(n, I) = \{ \begin{matrix}I, & if I = n − 2 \\ P^{(1)}(n, 1), & if I = 0 \\ ∑_{i=I}^{n} [∑_{j=I+1}^{i−1} P_{(j)}^{(1)}(n − 1, i − 1) + P^{(1)}(n − 1, i − 1)] , & otherwise \end{matrix} .

We combine these two recurrences and localize to obtain

P^{(1)}(n, I) = \{ \begin{matrix}I, & if I = n − 2 \\ P^{(1)}(n, 1), & if I = 0 \\ P^{(1)}(n, I + 1) + P^{(1)}(n − 1, I − 1) + P (n − 2, I), & otherwise \end{matrix} .

Table 4 Values of P^{(1)}(n, I)

n I=0 1 2 3 4 5 6 7 8 9 10
0  0
1  0  0
2  0  0  0
3  1  1  0  0
4  5  5  2  0  0
5  21  21  11  3  0  0
6  84  84  49  19  4  0  0
7  330  330  204  92  29  5  0  0
8  1287  1287  825  405  153  41  6  0  0
9  5005  5005  3289  1705  715  235  55  7  0  0
10  19448  19448  13013  7007  3146  1166  341  71  8  0  0

Using ordi[10] or gfun[5] we conjecture that a_{312}^{(1)}(n), the number of permutations on {1, 2, …, n} containing exactly one cab subsequence, = \frac{n−2}{2n} \binom{2n−2}{n−1}.

THE ENUMERATION OF PERMUTATIONS WITH A PRESCRIBED NUMBER OF “FORBIDDEN” PATTERNS 15

4 Counting abcd’s

Lest the reader think that the methods outlined in this paper will only help us gain information about permutations avoiding forbidden patterns of length three, here we examine the forbidden pattern abcd.

4.1 Definitions

Definition 4.1. An abcd pattern of a permutation σ is a sequence 1 ≤ i < j < k < l ≤ n with σ(i) < σ(j) < σ(k) < σ(l). Definition 4.2. φ_{abcd}(σ) = the number of abcd patterns which can be found in σ.

As before, we have Definition 4.3. φ_{aj}(σ) = the number of aj patterns of σ.

Here we must also define the following. Definition 4.4. An abj pattern is a sequence 1 ≤ i_{1} < i_{2} < i_{3} ≤ n with σ(i_{1}) < σ(i_{2}) < σ(i_{3}) = j. Definition 4.5. φ_{abj}(σ) = the number of abj patterns of σ. Definition 4.6. Let σ ∈ S_{n} then

wt(σ) = q^{φ_{abcd}(σ)} ∏_{j=3}^{n} q_{j}^{φ_{abj}(σ)} ∏_{j=2}^{n} ξ_{j}^{φ_{aj}(σ)}.

The number of permutations with no abcd

Let σ_{1}(j) = σ(j), 1 ≤ j ≤ n − 1. If σ(n) = i then

wt(σ) = wt(σ_{1})q^{∑_{j=3}^{i−1} φ_{abj}(σ_{1})}q_{i}^{∑_{j=2}^{i−1} φ_{aj}(σ_{1})}ξ_{i}^{i−1}.  (19)

Let P_{n}(q; q_{3}, …, q_{n}; ξ_{2}, …, ξ_{n}) = ∑_{σ∈S_{n}} wt(σ). Using (19), we have

P_{n}(q; q_{3}, …, q_{n}; ξ_{2}, …, ξ_{n}) = ∑_{i=3}^{n} ξ_{i}^{i−1}P_{n−1}(q; qq_{3}, …, qq_{i−1}, q_{i+1}, …, q_{n}; q_{i}ξ_{2}, …, q_{i}ξ_{i−1}, ξ_{i+1}, …, ξ_{n})
+ ξ_{2}P_{n−1}(q; q_{4}, …, q_{n}; ξ_{3}, …, ξ_{n}) + P_{n−1}(q; q_{4}, …, q_{n}; ξ_{3}, …, ξ_{n}).  (20)

The number of permutations on {1 … n} with no abcd patterns is

P_{n}(0; 1, …, 1; 1, …, 1) = ∑_{i=3}^{n} P_{n−1}(0; \overbrace{0, …, 0}^{i−2}, \overbrace{1, …, 1}^{n−i−1}; 1, …, 1) + 2P_{n−1}(0; 1, …, 1; 1, …, 1).

We may use (20) twice more to find

P_{n}(1; \overbrace{0, …, 0}^{I_{1}−2}, \overbrace{1, …, 1}^{n−I_{1}−1}; 1, …, 1) = ∑_{i=3}^{I_{1}} P_{n−1}(0; \overbrace{0, …, 0}^{I_{1}−3}, \overbrace{1, …, 1}^{n−I_{1}−1}; \overbrace{0, …, 0}^{i−2}, \overbrace{1, …, 1}^{n−i−1})

+ ∑_{i=I_{1}+1}^{n} P_{n−1}(0; \overbrace{0, …, 0}^{i−3}, \overbrace{1, …, 1}^{n−i−1}; 1, …, 1)

+ 2P_{n−1}(0; \overbrace{0, …, 0}^{I_{1}−3}, \overbrace{1, …, 1}^{n−I_{1}−1}; 1, …, 1)

and

\begin{aligned}P_{n}(1; \overbrace{0, …, 0}^{I_{1}−2}, \overbrace{1, …, 1}^{n−I_{1}−1}; \overbrace{0, …, 0}^{I_{2}−1}, \overbrace{1, …, 1}^{n−I_{2}−1}) & = ∑_{i=I_{2}+1}^{I_{1}} P_{n−1}(0; \overbrace{0, …, 0}^{I_{1}−3}, \overbrace{1, …, 1}^{n−I_{1}−1}; \overbrace{0, …, 0}^{i−2}, \overbrace{1, …, 1}^{n−i−1}) \\ & + ∑_{i=I_{1}}^{n} P_{n−1}(0; \overbrace{0, …, 0}^{i−3}, \overbrace{1, …, 1}^{n−i−1}; \overbrace{0, …, 0}^{I_{2}−2}, \overbrace{1, …, 1}^{n−I_{2}−1}) \\ & + P_{n−1}(0; \overbrace{0, …, 0}^{I_{1}−3}, \overbrace{1, …, 1}^{n−I_{1}−1}; \overbrace{0, …, 0}^{I_{2}−2}, \overbrace{1, …, 1}^{n−I_{2}−1}). \end{aligned} (21)

Let P (n, I_{1}, I_{2}) = P_{n}(1; \overbrace{0, …, 0}^{I_{1}−2}, \overbrace{1, …, 1}^{n−I_{1}−1}; \overbrace{0, …, 0}^{I_{2}−1}, \overbrace{1, …, 1}^{n−I_{2}−1}) for 0 < \{I_{1}, I_{2}\} ≤ n. Observe that P (n, n, n)

is the number of permutations on {1 … n} with no abcd pattern, no abc pattern (for any c) and no aj patterns for any j. There is only one such permutation, namely [n, n − 1, …, 2, 1], thus P (n, n, n) = 1 for all n. Furthermore, it is clear from (21) that when I_{1} < I_{2}, P (n, I_{1}, I_{2}) = P (n, I_{2}, I_{2}). We may define P (n, I_{1}, 0) = P (n, I_{1}, 1) and P (n, 0, I2) = P (n, 1, I2) for all values of n, I_{1} and I_{2}. Using this notation, we have

P (n, I_{1}, I_{2}) = \{ \begin{matrix}P (n, 1, I_{2}), & if I_{1} = 0 \\ P (n, I_{1}, 1), & if I_{2} = 0 \\ P (n, I_{2}, I_{2}), & if I_{1} < I_{2} \\ 1, & if I_{1} = I_{2} = n \\ \begin{aligned}∑_{i=I_{2}+1}^{I_{1}}P (n − 1, I_{1} − 1, i − 1) & + ∑_{i=I_{1}+1}^{n}P (n − 1, i − 1, I_{2}) \\ & + P (n − 1, I_{1} − 1, I_{2} − 1) \end{aligned} , & otherwise \end{matrix} .

Table 5 Values of P (n, I, 1)

n I=0 1 2 3 4 5 6 7 8 9 10
0  0
1  1  1
2  2  2  2
3  6  6  6  5
4  23  23  23  20  14
5  103  103  103  92  70  42
6  513  513  513  466  372  252  132
7  2761  2761  2761  2536  2086  1509  924  429
8  15767 15767 15767 14594 12248  9227  6127  3432  1430
9  94359 94359 94359 87830 74772 57894 40403 24882 12870 4862
10  586590 586590 586590 548325 471795 372565 268909 175474 101036 48620 16796

THE ENUMERATION OF PERMUTATIONS WITH A PRESCRIBED NUMBER OF “FORBIDDEN” PATTERNS 17

Table 6 Values of P (n, 1, I)

n I=0 1 2 3 4 5 6 7 8 9 10
0  1
1  1  1
2  2  2  1
3  6  6  3  1
4  23  23  12  4  1
5  103  103  56  20  5  1
6  513  513  288  110  30  6  1
7  2761  2761  1588  640  190  42  7  1
8  15767 15767  9238  3882 1235  301  56  8 1
9  94359 94359 56094 24358 8187 2163 448 72 9 1
10  586590 586590 352795 157265 55235 15575 3528 636 90 10 1

Using ordi[10], we conjecture that a_{1234}^{(0)}(n) = P (n, 1, 1) satisfies the following recurrence with a_{1234}^{(0)}(0) = 1 and a_{1234}^{(0)}(1) = 1:

a_{1234}^{(0)}(n + 2) = −9\frac{(n + 1)^{2}}{(n + 4)^{2}} a_{1234}^{(0)}(n) + \frac{10n^{2} + 42n + 41}{(n + 4)^{2}}a_{1234}^{(0)}(n + 1)

5 Counting permutations avoiding more than one forbidden pattern

The method outlined in this paper can be used to find recurrences for the number of permutations avoiding 2 or more forbidden patterns. The method is essentially the same, though you have to keep track of more parameters, and recurrences can be more complicated. In the example that follows, we seek the number of permutations on {1 … n} avoiding both abc and bac. Let φ_{bac}(σ) be the number of bac patterns of the permutation σ. Let φ_{ja}(σ) be the number of ja patterns of σ (that is the number of inversions ‘caused’ by j). Let

wt(σ) = q^{φ_{abc}(σ)}ξ^{φ_{bac}(σ)} ∏_{j=2}^{n} (q_{j}^{φ_{aj}(σ)}ξ_{j}^{φ_{ja}(σ)}) .

It may seem a bit wasteful to spend time defining both φ_{aj}(σ) and φ_{ja}(σ) when it is clear that φ_{aj}(σ) + φ_{ja}(σ) = n − 1 but we will see that this ‘complication’ in addition to the introduction of the parameters ξ_{j} will pay off in the end.

P_{n}(q; ξ; q_{2}, …, q_{n}; ξ_{2}, …, ξ_{n}) = ∑_{σ∈S_{n}} wt(σ) = ∑_{i=1}^{n} ∑_{{σ∈Sn \atop σ(n)=i}} wt(σ)

= ∑_{i=2}^{n} q_{i}^{i−1} (∏_{j>i} ξ_{j})P_{n−1}(q; ξ; qq_{2}, …, qq_{i−1}, q_{i+1}, …, q_{n}; ξξ_{2}, …, ξξ_{i−1}, ξ_{i+1}, …, ξ_{n})

+ (∏_{j} ξ_{j}) P_{n−1}(q; ξ; q_{3}, …, q_{n}; ξ_{3}, …, ξ_{n}).

Let P (n, I) = P_{n}(0; 0; \overbrace{0, …, 0}^{I−1}, \overbrace{1, …, 1}^{n−I}; \overbrace{0, …, 0}^{I−1}, \overbrace{1, …, 1}^{n−I}). Note that from our definition, P (n, I) = 0 when

I > 1. Indeed, P (n, I) is the number of permutations on {1 … n} containing no abc, no bac, no aj for j ≤ I and no ja for j ≤ I. If there was a permutation for which this was true for an I¿1 then we merely examinee the positions of the object 1 and 2 in the permutation. Let σ(i) = 1 and σ(j) = 2. If i < j then σ has an a2 pattern. If j < i then σ has a 2a pattern. Thus, σ does not meet the requirements and so P (n, I) = 0 for I > 1. We have the recurrence

P (n, I) = \{ \begin{matrix}P (n, 1), & if I = 0 \\ 0, & if I > 1 \\ 1, & if n = I = 1 \\ ∑_{i=I}^{n} P (n − 1, i − 1), & otherwise \end{matrix} .

This recurrence reduces to

P (n, 1) = \{ \begin{matrix}1, & if n = 1 \\ 2P (n − 1, 1), & if n > 1 \end{matrix} .

So we have reproved the well know result that the number of permutations on {1 … n} with no abc and no bac is 2^{n}.

Conclusion

We saw in the above examples that in order to compute the quantity of interest, a_{n}, say, we naturally introduced extra parameters I_{1}, I_{2}, …, and a new quantity F (n, I_{1}, I_{2}, …) such that a_{n} was the special case F (n, 1, 1, …), in which all the extra parameters I_{1}, I_{2}, …, are set to 1. Since the system of linear recurrence equations always seems to have constant coefficients, the generating function in all the corresponding continuous variables

F̃(z; x_{1}, x_{2}, …) := ∑_{n,I_{1},I_{2},...} F (n, I_{1}, I_{2}, …)z^{n}x_{1}^{I_{1}}x_{2}^{I_{2}} …

should be holonomic (multi-D-finite) in all its variables (because of the nonstandard boundary conditions, it is not always a rational function). It follows from the holonomic theory [9] that any coefficient with respect to x_{1}, x_{2}, …, in particular that of x_{1}^{1}x_{2}^{1} …, is still holonomic (D-finite, i.e. satisfies a linear differential equation with polynomial coefficients), hence f_{n} := F (n, 1, 1, …) is P −recursive.

The method described here works for many patterns and sets of patterns, but it does not seem to work for all patterns. The authors were unable to find a suitable set of parameters (see the method, step 2) to apply this method to the pattern adcb.

Appendix

A maple package which confirms and illustrates many results from this paper is available and can be obtained using your favorite world wide web browser at http://www.math.temple.edu/~noonan or

http://www.math.temple.edu/~zeilberg.

References

1. Kimmo Erikson and Svante Linusson, The size of Fulton’s essential set, The Electronic Journal of Combinatorics 1, R6 (1995), 18pp.

2. V.E. Hoggatt, Jr., and Margorie Bicknell, Catalan and related sequences arising from inverses of Pascal’s triangle matrices, The Fibonacci Quarterly 14 (1976), 395–404.

3. Donald Knuth, The Art of Computer Programming , vol 3, Sorting and Searching, Addison-Wesley, 1973.

4. John Noonan, The number of permutations containing exactly one increasing subsequence of length three, Discrete Mathematics to appear.

5. B.Salvy and P. Zimmermann, Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math. Soft. 20 (1994).

6. Rodica Simion and Frank W. Schmidt, Restricted Permutations, European Journal of Combinatorics 6 (1985), 383–406.

7. Julian West, Permutations with forbidden subsequences and stack sortable permutations, PhD thesis, MIT (1990).

8. Doron Zeilberger, A Holonomic systems approach to special functions identities, J. of Computational and Applied Math. 32 (1990), 321-368.

9. Doron Zeilberger, The Joy of Brute Force, available via world wide web browser at http://www.math.temple.edu/ ~zeil-

   berg/papers1.html.

10. Doron Zeilberger, SCHUTZENBERGER, a package for maple, available via world wide web browser at http://www.math.temple.edu/

   ~zeilberg/programs.html.

Department of Mathematics, Temple University, Philadelphia, PA 19122

  E-mail address: noonan@math.temple.edu, zeilberg@math.temple.edu, WWW homepage:  http://www.math.temple.edu/~noonan,
http://www.math.temple.edu/~zeilberg