REFINED RESTRICTED PERMUTATIONS

Aaron Robertson^{1} Department of Mathematics, Colgate University, Hamilton, NY 13346

                           aaron@math.colgate.edu

Dan Saracino Department of Mathematics, Colgate University, Hamilton, NY 13346

                         dsaracino@mail.colgate.edu

Doron Zeilberger^{2} Department of Mathematics, Rutgers University, New Brunswick, NJ 08903

                         zeilberg@math.rutgers.edu

Dedication: In memory of Rodica Simion (1955-2000)

This article is dedicated to the memory of Rodica Simion, one of the greatest enumerators of the 20^{th} century. Both derangements ([SS2]) and resticted permutations ([SS]) were very dear to her heart, and we are sure that she would have appreciated the present surprising connections between these at-first-sight unrelated concepts.

Abstract

Define S_{n}^{k}(α) to be the set of permutations of {1, 2, …, n} with exactly k fixed points which avoid the pattern α ∈ S_{m}. Let s_{n}^{k}(α) be the size of S_{n}^{k}(α). We investigate S_{n}^{0}(α) for all α ∈ S_{3} as well as show that s_{n}^{k}(132) = s_{n}^{k}(213) = s_{n}^{k}(321) and s_{n}^{k}(231) = s_{n}^{k}(312) for all 0 ≤ k ≤ n.

1 Introduction

Let π ∈ S_{n} be a permutation of {1, 2, …, n} written in one-line notation. Let α ∈ S_{m}. We say that π contains the pattern α if there exist indices i_{1}, i_{2}, …, i_{m} such that π_{i_{1}}π_{i_{2}} … π_{i_{m}} is equivalent to α, where we define equivalence as follows. Define \overline{π}_{i_{j}} = |\{x : π_{i_{x}} ≤ π_{i_{j}}, 1 ≤ x ≤ m\}|. If α = \overline{π}_{i_{1}} \overline{π}_{i_{2}} … \overline{π}_{i_{m}} then we say that α and π_{i_{1}}π_{i_{2}} … π_{i_{m}} are equivalent. For example, if τ = 124635 then τ contains the pattern 132 by noting that τ_{2}τ_{4}τ_{5} = 263 is equivalent to 132. We say that π is α-avoiding if π does not contain the pattern α. In our above example, τ is 321-avoiding.

1Homepage: http://math.colgate.edu/∼aaron/

2Supported in part by the NSF. Homepage: http://www.math.rutgers.edu/∼zeilberg/ 2000 Mathematics Subject Classification: 05A15, 68R15

Define S_{n}(α), α ∈ S_{m}, to the the set of α-avoiding permutations in S_{n}. Let s_{n}(α) be the size of S_{n}(α). Knuth ([Knu]) showed that, regardless of the pattern α ∈ S_{3}, s_{n}(α) = C_{n} = \frac{1}{n+1} \binom{2n}{n}, the n^{th} Catalan number. Bijective results are given in [Kra], [Ric], [SS], and [Wes].

We refine the investigation of S_{n}(α) in the following fashion. Let α ∈ S_{m}. Define S_{n}^{k}(α) to be the set of α-avoiding permutations of {1, 2, …, n}, with exactly k fixed points. Let s_{n}^{k}(α) be the size of S_{n}^{k}(α). We may write D_{n}(α) and d_{n}(α) for S_{n}^{0}(α) and s_{n}^{0}(α), respectively, since we are dealing with derangements.

2 Similarity Relations, Catalan Sequences, and Fine’s Sequence

We begin our investigation with similarity relations. A similarity relation, R, is a binary relation on an ordered set which is reflexive, symmetric, but not necessarily transitive, with the condition that if iRk and i < j < k then iRj and jRk. Furthermore, we have the following definition about the structure of a similarity relation.

Definition 2.1 A similarity relation, R, is said to have k isolated points if k is the number of i ∈ {1, 2, …, n} such that there does not exists j ≠ i with iRj. If k = 0, we say that the similarity relation is nonsingular. We denote by SR_{n}(k) the set of similarity relations on {1, 2, …, n} with k isolated points.

There are two common structures which can be used to view similarity relations: graphs and sequences. We will be using the sequence interpretation of a similarity relation as given by Strehl in [Str]: Let R be a similarity relation on {1, 2, …, n}. Then R corresponds to an integer sequence r_{1}r_{2} … r_{n} defined for any 1 ≤ i ≤ n by r_{i} = i − j, where j is the smallest element of {1, 2, …, n} such that iRj. Throughout this paper we assume that similarity relations are defined on {1, 2, …, n}. To this end, we make the following definition.

Definition 2.2 The set of similarity relations (on {1, 2, …, n}) is given by

SR_{n} = {r_{1}r_{2} ⋯ r_{n} : r_{i} ∈ ℤ, r_{1} = 0 and 0 ≤ r_{i+1} ≤ r_{i} + 1 for 1 ≤ i ≤ n − 1}.

For example SR_{3} = {000, 001, 010, 011, 012}.

It is known ([Rog], [Str]) that for n ≥ 1, |SR_{n}(0)| = F_{n}, where F_{n} is the n^{th} Fine number. The first few values of Fine’s sequence are 0, 1, 2, 6, 18, 57, 186, 622, 2120, …, a sequence first discovered in [Fin].

Looking at SR_{n}(0) a little more closely, we see that s ∈ SR_{n}(0) if and only if s has no occurrence of 00 and does not end with 0. Hence, we say that a nonsingular similarity relation has no double zero, where we consider an ending 0 to be a double zero.

We now state some of the results concerning Fine’s sequence as given in [Rog], [Sha], and [Str].

Theorem 2.1 Let C_{n} = \frac{1}{n+1} \binom{2n}{n} and F_{n} be the n^{th} Catalan number and Fine number, respectively. We have the following for n ≥ 2.

1. |SR_{n}(0)| = F_{n}

2. C_{n} = 2F_{n} + F_{n−1}

3. F_{n} = ∑_{1≤k≤n/2} \binom{2n−2k−1}{n−1} − \binom{2n−2k−1}{n}

4. F_{n} = \frac{1}{2} ∑_{i=0}^{n−2} (\frac{−1}{2})^{i} C_{n−i}

As we can see, the Catalan and Fine numbers are related. This becomes more evident in light of the following definition.

Definition 2.3 The set of Catalan sequences of length n is given by

Cat(n) = {c_{1}c_{2} ⋯ c_{n} : c_{i} ∈ ℤ, 1 ≤ c_{1} ≤ c_{2} ≤ ⋯ ≤ c_{n}, and c_{i} ≤ i for 1 ≤ i ≤ n}

For example: Cat(3) = {111, 112, 113, 122, 123}. It is well-known and easy to see that the cardinality of Cat(n) is the n^{th} Catalan number. It is also well-known and easy to see that the generating function for the Catalan numbers, ψ(t) = ∑_{n=0}^{∞} C_{n}t^{n}, satisfies the quadratic equation ψ(t) = 1 + tψ^{2}(t), and hence that ψ(t) = \frac{1−\sqrt{1−4t}}{2t}.

3 321-Avoiding Derangements and Dyck Paths

The aim of this section is to show that the 321-avoiding derangements are enumerated by Fine’s sequence. We will investigate two bijections, the main one due to Krattenthaler [Kra]. First, we must introduce a few definitions.

Definition 3.1 We say that a permutation π ∈ S_{n} is a backward derangement if π_{n+1−i} ≠ i for all 1 ≤ i ≤ n.

Consequently, a 123-avoiding backward derangement when read from right to left is a 321avoiding derangement.

We will be using a bijection due to Krattenthaler [Kra] from S_{n}(123) to the set of Dyck paths of length 2n, so for completeness we define a Dyck path.

Definition 3.2 A Dyck path is a path in ℝ^{2} from (0, 0) to (2n, 0) consisting of a sequence of steps of length \sqrt{2} and slope ±1. We denote these two types of steps by (1, 1) and (1, −1), called up-steps and down-steps, respectively. We say that the length of such a Dyck path is 2n (its horizontal length) and denote the set of Dyck paths of length 2n by Dyck(2n).

We also have the following definition about certain Dyck paths.

Definition 3.3 We say that a Dyck path contains a hill if it has a peak at height 1. We say that a Dyck path is hill-free is it contains no hill. We denote the set of hill-free Dyck paths of length 2n by Dyck^{hf}(2n).

We now describe a natural bijection from SR_{n} to Dyck paths of length 2n. Let s = s_{1}s_{2} … s_{n} ∈ SR_{n}. This bijection is very similar to one given by Krattenthaler [Kra] from S_{n}(132) to Dyck(2n).

Each s_{i}, 1 ≤ i ≤ n, corresponds to the starting height of an up-step. Proceeding from s_{i} to s_{i+1}, if s_{i+1} > s_{i} then we continue with up-steps. If s_{i+1} ≤ s_{i} we append s_{i} − s_{i+1} + 1 down-steps followed by a single up-step. This assures us that s_{i+1} corresponds to a starting height of s_{i+1} for an up-step. After s_{n} we use as many down-steps as necessary to end at (2n, 0). The inverse bijection is obvious. An example is in order.

Let s = 0120121 ∈ SR_{7}(0). This nonsingular similarity relation corresponds to the following Dyck path, with the entries of s marked on the Dyck path.

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

Dyck path corresponding to 0120121 ∈ SR_{7}(0) and to 6573142 ∈ S_{7}(123)

Using the above bijection and the fact that |Dyck(2n)| = C_{n}, we easily obtain |SR_{n}| = C_{n} (which was shown in [Rog] and [Str]). Furthermore, we get the following theorem (SR_{n}(0) = F_{n} was shown in [Rog] and [Str] while |Dyck^{hf}(2n)| = F_{n} was shown in [Deu] ).

Theorem 3.1 For n ≥ 1, |SR_{n}(0)| = |Dyck^{hf}(2n)| = F_{n}, where F_{n} is the n^{th} Fine number

Proof. Clearly, a hill occurs in a Dyck path if and only if the corresponding similarity relation contains a double zero. □

We are now ready to use Krattenthaler’s bijection ([Kra]), described as follows. Let π = π_{1}π_{2} ⋯ π_{n} ∈ S_{n}(123). Determine the right-to-left maxima of π, i.e. m = π_{i} is a right-to-left maximum if m > π_{j} for all j > i. For example, the right-to-left maxima of 6573142 are in bold type.

Let π have right-to-left maxima m_{1} < m_{2} < ⋯ < m_{s}, so that we may write

π = w_{s}m_{s}w_{s−1}m_{s−1} ⋯ w_{1}m_{1}.

So, for example, in 6573142 we have w_{3} = 65, m_{3} = 7, w_{2} = 31, m_{2} = 4, w_{1} = ∅, m_{1} = 2.

We now generate a Dyck path from (2n, 0) to (0, 0) (generate it backwards) using backward up-steps ((−1, 1)) and backward down-steps ((−1, −1)).

Read π from right to left. For each m_{i} do m_{i} − m_{i−1} up-steps (where we define m_{0} = 0). For each w_{i} do |w_{i}| + 1 down-steps. So, for example, π = 6573142 generates the Dyck path shown above.

We now state the main theorem of this section.

Theorem 3.2 Let π ∈ S_{n}(123) and let D_{π} be the associated Dyck path provided by Krattenthaler’s bijection. Then π is a backward derangement if and only if D_{π} is hill-free.

Proof. We first demonstrate the “only-if” direction. Assume, for a contradiction, that D_{π} has a hill. Notice that the hill cannot be at either end of the Dyck path for otherwise π_{1} = n or π_{n} = 1, both contradicting the fact that π is a backward derangement. Hence, any hill must be an “interior” hill. Let π = π(1)π(2) and D_{π} = D_{π(1)}D_{π(2)} where D_{π(1)} contains a hill on the right end and D_{π(2)} contains no hill. Let D_{π(2)} consist of 2y steps. By construction, π(2) contains the elements 1, 2, …, y. Thus, in order for D_{π(1)} to end with a hill, we must have π_{n−y}(1) = y + 1, i.e. π_{n+1−(y+1)} = y + 1, contradicting the fact that π is a backward derangement.

We now give the “if” direction; we prove the contrapositive. Assume, for a contradiction, that D_{π} has no hill. Let x be the smallest integer such that π_{n+1−x} = x. Write π = π(1)xπ(2). From the above argument, we see that π(2) cannot consist of the elements 1, 2, …, x − 1 only, for otherwise we would have a hill. Hence, there exists y ∈ π(2) such that y > x. Consequently, there exists w ∈ π(1) such that w < x. But then wxy is a 123-pattern, a contradiction. □

Coupling this theorem with Theorem 3.1, we immediately obtain the following corollary.

Corollary 3.3 For n ≥ 1, d_{n}(321) = F_{n}, where F_{n} is the n^{th} Fine number.

We can now investigate the relationship between S_{n}^{k}(321) and similarity relations. To this end, we have the following theorem.

Theorem 3.4 For n ≥ 0, s_{n}^{k}(321) = |SR_{n}(k)|.

Proof. We prove this by induction on k. The case k = 0 is given by Corollary 3.3. Hence, we assume that there exists a bijection γ_{n}^{k} : S_{n}^{k}(321) → SR_{n}(k).

Let π ∈ S_{n}^{k+1}(321) and let f be the smallest fixed point. Write π = π(1)fπ(2) so that π(2) contains k fixed points. Note that since π must be 321-avoiding we must have π(1) ∈ S_{f−1}^{0}(321) on the elements 1, 2, …, f − 1 and π(2) ∈ S_{n−k}^{k}(321) on the elements f + 1, f + 2, …, n. Let γ_{f−1}^{0}(π(1)) = t ∈ SR_{f}(0) and γ_{n−f}^{k}(π(2)) = r ∈ SR_{n−f}(k). Then define γ_{n}^{k+1}(π) = t0r ∈ SR_{n}(k + 1). To show this is a bijection, it is enough to give the inverse. This is obtained by noting that the position of the first 0 in the first occurrence of a double zero in an element of SR_{n}(k + 1) corresponds to the minimal fixed point. □

4 Weighted-Counting of 321-Avoiding Permutations

In order to achieve one of our goals we must enumerate S_{n}^{k}(321) via another approach. Before delving into our approach, we make the following definition.

Definition 4.1 Let S be a finite set with each element s ∈ S having a unique characteristic from C = {c_{1}, c_{2}, …, c_{k}}, written as char(s). The weight-enumerator of S with respect to weight(s) = x^{char(s)} is given by

∑_{i=1}^{k} s_{i}x^{c_{i}},

where s_{i} = |{s ∈ S : char(s) = c_{i}}|.

Applying this to our situation, let A_{n} = S_{n}(321) and let A_{n}(x) be its weight-enumerator with respect to weight(π) = x^{f(π)}, where f(π) is the number of fixed points of π ∈ S_{n}(321).

Recall that Cat(n) is the set of Catalan sequences, defined in Section 2. We will define a bijection T : A(n) → Cat(n) as follows. If n = 1, then T (1) = 1. For n ≥ 2 we define c = T (π) recursively as follows.

Given a 321-avoiding permutation π of length n, let i be the place where n is (i.e. π_{i} = n). If π_{n} = n − 1 then let π′ be π_{1}, …, π_{i−1}, n − 1, π_{i+1}, …, π_{n−2}, otherwise let π′ be π with n removed, i.e. π′ = π_{1}, …, π_{i−1}, π_{i+1}, …, π_{n}. Then c = T (π) is defined to be c′ = T (π′) with i appended at the end.

The inverse bijection S : Cat(n) → A(n) is defined as follows. If n = 1 then S(1) = 1. If n ≥ 2 and c = c_{1} ⋯ c_{n} is a Catalan sequence then π = S(c) is defined recursively as follows. Let c_{n} = i, c_{n−1} = j, and let c′ = c_{1} ⋯ c_{n−2}c_{n−1} be c with its last component removed. Let π′ = S(c′). If i ≤ j then let π be the permutation obtained from π′ by changing the n − 1 into n and appending n − 1 to the end, while if j < i then let π be the permutation obtained from π′ by inserting n at the i^{th} place i.e. π = π′_{1}, …, π′_{i−1}, n, π′_{i}, …, π′_{n−1}.

It is easy to prove, by induction on n, that T S and ST are identity mappings, and hence that T is indeed a bijection. It is also easy to see that if c_{1} ⋯ c_{n} = T (π) then for 1 ≤ i < n, π_{i} = i if and only if c_{i} = i and c_{i+1} = i + 1, and π_{n} = n if and only if c_{n} = n. Hence A_{n}(x) is equal to the weight-enumerator of Catalan sequences with respect to weight(c) = x^{g(c)}, where g(c) is the number of i’s such that c_{i} = i and c_{i+1} = i + 1 (i < n) plus 1 if c_{n} = n.

Given a Catalan sequence c, let

D(c) = {i : 1 ≤ i < n, c_{i} = i, c_{i+1} = i + 1 or i = n and c_{n} = n}.

For example, D(11345558) = {3, 4, 8}, D(11111111) = ∅, and D(112346) = {6}. Note the weight of a Catalan sequence c is x^{|D(c)|}.

In order to weight-enumerate the set of Catalan sequences it would be easier to use the inclusion-exclusion philosophy and consider the larger sets of marked Catalan sequences, which are the sets of pairs (c, S) with S ⊂ D(c) and weight defined by weight(c, S) = (x − 1)^{|S|}. For example weight(11345558, {3, 8}) = (x − 1)^{2} and weight(11345558, {}) = (x − 1)^{0} = 1. Since x^{|D(c)|} = ((x − 1) + 1)^{|D(c)|}= ∑_{S⊂D(c)}(x − 1)^{|S|}, it follows that A_{n}(x) is the weight-enumerator of marked Catalan sequences.

We now derive a recurrence. Given a marked Catalan sequence (c_{1} ⋯ c_{n}, S), if 1 ∈ S (i.e. 1 is marked) then we can get a smaller marked word by deleting c_{1} = 1 and diminishing all indices and elements of S by 1. The weight-enumerator of this case is (x − 1)A_{n−1}(x).

If 1 ∉ S (i.e. 1 is not marked), let i be the smallest i > 1 such that c_{i} = i, if it exists. Then c_{2} ⋯ c_{i−1} is a run-of-the-mill Catalan sequence of length i − 2, while

(c_{i} − (i − 1) c_{i+1} − (i − 1) ⋯ c_{n} − (i − 1), S − (i − 1))

(by S−(i−1) we mean the set S with all of its elements reduced by i−1) is a marked Catalan sequence of length n − i + 1. The weight-enumerator of this, for a given i, is C_{i−2}A_{n−i+1}(x) (2 ≤ i ≤ n). Finally, if c_{i} < i for all 2 ≤ i ≤ n then c_{2} ⋯ c_{n} is a typical Catalan sequence of length n − 1. Hence we get that

A_{n}(x) = (x − 1)A_{n−1}(x) + (∑_{i=2}^{n} C_{i−2}A_{n−i+1}(x)) + C_{n−1},

which can be rewritten as

A_{n}(x) = (x − 1)A_{n−1}(x) + ∑_{i=1}^{n} C_{i−1}A_{n−i}(x).  (4.1)

Introducing the generating function

ϕ(x, t) = ∑_{n=0}^{∞} A_{n}(x)t^{n},

and recalling the generating function for the Catalan numbers ψ(t) = \frac{1−\sqrt{1−4t}}{2t}, (4.1) translates to

ϕ(x, t) = 1 + (x − 1)tϕ(x, t) + tϕ(x, t)ψ(t).

Solving for ϕ(x, t) yields the explicit expression

ϕ(x, t) = \frac{2}{1 − 2(x − 1)t + \sqrt{1 − 4t}}

which, in turn, implies (by multiplying the top and the bottom by 1 − 2(x − 1)t − \sqrt{1 − 4t}) that

ϕ(x, t) = \frac{1 − x + ψ(t)}{2 − x + t(x − 1)^{2}} .

To sum up we have the following theorem.

Theorem 4.1 Let a_{n}(x) be the coefficient of t^{n} in the Maclaurin expansion with respect to t of

\frac{1 − x + ψ(t)}{2 − x + t(x − 1)^{2}} .

Then A_{n}(x) = a_{n}(x).

We now investigate an interesting property of a_{n}(x) that will be used in the next section. Expanding a_{n}(x) in powers of (x − 1) and using (4.1), we may write

a_{n}(x) = (x − 1)^{n} + ∑_{i=0}^{n−1} ∑_{j=1}^{n−i} C_{j−1}a_{n−i−j}(x) · (x − 1)^{i}.  (4.2)

Using (4.2) we prove the following crucial lemma.

Lemma 4.2 Let a_{n}(x) = ∑_{k=0}^{n} b(n, k)(x − 1)^{k} and define b(x, y) = 0 if y > x, x < 0, or y < 0. Then, for n ≥ 1 and k ≠ −1,

b(n, k) = b(n, k + 1) + b(n − 1, k − 1)  (4.3)

where b(0, 0) = 1.

Proof. Note that to render (4.3) valid when n = k = 0, we would have to add a correction term of 1 to the right side, and to render (4.3) valid when n ≥ 0 and k = −1 we would have to add b(n, 0) = C_{n} to the left side.

We now prove (4.3) for n ≥ 1 and k ≠ −1 by induction on n. Since a_{0}(x) = 1 and a_{1}(x) = x, the case n = 1 is true. We now assume that b(n − i, k) = b(n − i, k + 1) + b(n − i − 1, k − 1) for all 1 ≤ i ≤ n − 1 and k ≠ −1.

To establish (4.3) for n and all k ≠ −1 we first note that this is clear if k < −1 or k > n. It is also clear for k = n since b(n, n) = b(n−1, n−1) = 1 by (4.2). To deal with 0 ≤ k ≤ n−1 we use the fact that (4.2) yields

b(n, k) = ∑_{i=0}^{n−1} ∑_{j=1}^{n−i} C_{j−1}b(n − i − j, k − i)  (4.4)

for 0 ≤ k ≤ n − 1.

In particular, for k = n−1 this says that b(n, n−1) = n, so b(n, n−1) = b(n, n)+b(n−1, n−2) and (4.3) holds for k = n − 1.

For 0 ≤ k ≤ n − 2 we take (4.4) and apply (4.3) to each term on the right side, adding a correction term of C_{n−k−1} when i = k and j = n − k (note that this case occurs since k ≠ −1), and correction term − ∑_{i=1}^{n−k−1} C_{i−1}C_{n−k−i−1} when i = k + 1 (note that this case occurs since k ≠ n − 1). Since the correction terms cancel, we have

b(n, k) = ∑_{i=0}^{n−1} ∑_{j=1}^{n−i} C_{j−1}b(n − i − j, k − i + 1) + ∑_{i=0}^{n−1} ∑_{j=1}^{n−i} C_{j−1}b(n − i − j − 1, k − i − 1).

Since k + 1 ≤ n − 1, the first term on the right is b(n, k + 1) by (4.4). By (4.4) again, the second term on the right is b(n − 1, k − 1) except for the terms in the double sum where i = n − 1 or j = n − i. But these terms are all 0 because they involve values of b(x, y) with x < 0. This concludes the proof. □

In [Str], Strehl defines a(n, k), for n ≥ 1 and 1 ≤ k ≤ n, as the number of similarity relations on {1, 2, …, n} that have k zeros. He proves that a(n, k) = a(n, k + 1) + a(n − 1, k − 1) for n ≥ 2, with a(n, 1) = a(n, 2) = C_{n−1}. It follows from Lemma 4.2 that b(n, k) = a(n+1, k−1).

Using Lemma 4.2 we see that the beginning of the b(n, k) table is as follows, where n = 0, 1, … corresponds to row n and k = 0, 1, 2, … is the k^{th} term in from the left. This generates the so-called Catalan Triangle ([Slo]).

1

1  1
2  2  1
5  5  3  1
14  14  9  4  1
42  42  28  14  5  1
132  132  90  48  20  6  1

Beginning of the Catalan triangle; values of b(n, k)

We also use Lemma 4.2 to prove the next lemma, which will be a crucial step in one of our main proofs.

Lemma 4.3 Let a_{n}(x) = ∑_{k=0}^{n} b(n, k)(x − 1)^{k}. Then, for all n, k ≥ 1,

b(n, k) = ∑_{i=1}^{n} C_{i−1}b(n − i, k − 1)

where b(n, 0) = C_{n}, and b(x, y) = 0 if y > x.

Proof. We use double induction; forward on n and backward on k. We start with induction on n. From the table above, this clearly holds for n = 2 and 1 ≤ k ≤ 2. Hence, we assume that it holds for n − 1 and 1 ≤ k ≤ n − 1 to show that it holds for n and 1 ≤ k ≤ n. We now perform backward induction on k. The base case b(n, n) holds since b(n, n) = b(n−1, n−1) = 1. Hence, we assume that the case b(n, k + 1) holds to show that the case b(n, k) holds.

We must do the case k = 1 seperately. This holds by the identity C_{n} = ∑_{i=1}^{n} C_{i−1}C_{n−i} and the fact that b(n, 1) = b(n, 0) = C_{n}.

Now, from Lemma 4.2, we have b(n, k) = b(n, k + 1) + b(n − 1, k − 1) rendering the induction straightforward for k ≥ 2. □

5 Weighted-Counting of 132-Avoiding Permutations

Recall that A_{n} = S_{n}(321) and A_{n}(x) is its weight-enumerator with respect to weight(π) = x^{f(π)}, where f(π) is the number of fixed points of π ∈ S_{n}(321). Let B_{n} = S_{n}(132) and let B_{n}(x) be its weight-enumerator with respect to the same weight. Our goal is to show that for n ≥ 0, A_{n}(x) = B_{n}(x).

We have that B_{n} is the set of 132-avoiding bijections on {1, 2, …, n}. However, in order to weight-enumerate them, we must consider, more generally, the set E_{n,r} of bijections

π : {1, 2, …, n} → {r + 1, r + 2, …, r + n}

that avoid 132. Let E_{n,r}(x) be the weight-enumerator of these bijections, with respect to the same weight. It is easy to see that E_{n,−r}(x) = E_{n,r}(x), and that E_{n,r}(x) = C_{n} if r ≥ n, since in this situation no fixed point can occur. Of course B_{n}(x) = E_{n,0}(x).

We will now establish a recurrence for the E_{n,r}(x). Consider π ∈ E_{n,r}. Let i be the location of n+r, i.e. the index i for which π_{i} = n+r. Now the set of entries before the i^{th} place must consist of the i − 1 largest elements of the range, and the entries after the i^{th} place must consist of the n−i smallest elements, since otherwise a delinquent 132 will be formed. Hence, every member π ∈ E_{n,r} gives rise to a pair (π′, π′′) where π′ ∈ E_{i−1,n−i+r} and π′′ ∈ E_{n−i,r−i} . Furthermore, the weight of π is the product of the weights of π′ and π′′, except when r = 0 and i = n in which case we removed a fixed point, and we have an extra factor of x. Let I_{S} be the characteristic function, i.e. I_{S} = 1 if S is true, and 0 otherwise. The above argument gives the following non-linear recurrence.

E_{n,r}(x) = ∑_{i=1}^{n} E_{i−1,n−i+r}(x)E_{n−i,r−i}(x) + (x − 1)E_{n−1,0}(x)I_{{r=0}}.

Changing E_{n−i,r−i}(x) to E_{n−i,i−r}(x) when i > r and using the fact that E_{i−1,n−i+r}(x) = C_{i−1} when n − i + r ≥ i − 1, i.e. i ≤ ⌊\frac{n+r+1}{2}⌋, and E_{n−i,i−r}(x) = C_{n−i} when i − r ≥ n − i, i.e. i ≥ ⌈\frac{n+r}{2}⌉, we get a simplified recurrence, which is linear in E_{n,r}:

\begin{aligned}E_{n,r}(x) & = ∑_{i=1}^{r} C_{i−1}E_{n−i,r−i}(x) + ∑_{i=r+1}^{⌊ \frac{n+r+1}{2} ⌋} C_{i−1}E_{n−i,i−r}(x) \\ & + ∑_{i=⌊ \frac{n+r+1}{2} ⌋+1}^{n} E_{i−1,n−i+r}(x)C_{n−i} + (x − 1)E_{n−1,0}(x)I_{\{r=0\}}. \end{aligned}

We are now able to prove the following theorem.

Theorem 5.1 Let a_{n}(x) be the weight-enumerator of 321-avoiding permutations with respect to weight(π) = x^{f(π)}, where f(π) is the number of fixed points in π ∈ S_{n}(321). Let E_{n,r}(x) be the weight-enumerator of 132-avoiding bijections from {1, 2, …, n} to {r+1, r+2, …, r+n} with respect to the same weight.

Then, for r ≥ 0,

E_{n,r}(x) = a_{n}(x) + (1 − x) ∑_{i=1}^{r} C_{i−1}a_{n−i}(x),  (5.1)

where we define a_{j}(x) = 0 for j < 0.

Proof. Denote by e_{n,r}(x) the right side of (5.1). We must show for all n (keeping r as a parameter) that

\begin{aligned}e_{n,r}(x) & = ∑_{i=1}^{r} C_{i−1}e_{n−i,r−i}(x) + ∑_{i=r+1}^{⌊ \frac{n+r+1}{2} ⌋} C_{i−1}e_{n−i,i−r}(x) \\ & + ∑_{i=⌊ \frac{n+r+1}{2} ⌋+1}^{n} e_{i−1,n−i+r}(x)C_{n−i} + (x − 1)e_{n−1,0}(x)I_{\{r=0\}}. \end{aligned}

In other words, we have to prove

\begin{aligned}a_{n}(x) + (1 − x) ∑_{i=1}^{r} C_{i−1}a_{n−i}(x) & = ∑_{i=1}^{r} C_{i−1} (a_{n−i}(x) + (1 − x) ∑_{j=1}^{r−i} C_{j−1}a_{n−i−j}(x)) \\ & + ∑_{i=r+1}^{⌊ \frac{n+r+1}{2} ⌋} C_{i−1} (a_{n−i}(x) + (1 − x) ∑_{j=1}^{i−r} C_{j−1}a_{n−i−j}(x)) \\ & + ∑_{i=⌊ \frac{n+r+1}{2} ⌋+1}^{n} C_{n−i} (a_{i−1}(x) + (1 − x) ∑_{j=1}^{n−i+r} C_{j−1}a_{i−j−1}(x)) \\ & + (x − 1)a_{n−1}(x)I_{\{r=0\}}, \end{aligned} ; (5.2)

which has been checked by the Maple package AARON for n ≤ 50. AARON was written by the third author (with additions by the first author) and is available at each of these author’s website (given on the first page).

Let the left side of (5.2) be l_{n}(x) and the right side be r_{n}(x). Write

l_{n}(x) = ∑_{k=0}^{n} s(n, k)(x − 1)^{k} and r_{n}(x) = ∑_{k=0}^{n} t(n, k)(x − 1)^{k}.

If we can show that for any n, s(n, k) = t(n, k) for all 0 ≤ k ≤ n, then we will be done.

We must take care of the case k = 0 seperately. This case holds since b(n, 0) = C_{n} and C_{n} = ∑_{i=1}^{n} C_{i−1}C_{n−i}.

We now use double induction on n ≥ 2 and k ≥ 0; forward induction on n and backward induction on k.

We start by inducting on n. Since Maple has given us the base case, i.e. s(2, k) = t(2, k) for 0 ≤ k ≤ 2, we may assume that s(n − 1, k) = t(n − 1, k) for all 0 ≤ k ≤ n − 1. We must show that s(n, k) = t(n, k) for all 0 ≤ k ≤ n.

We proceed via backward induction on k. For our base case we must show that s(n, n) = t(n, n). Gathering the (x − 1)^{n} terms in (5.2) we have (x − 1)^{n} − (x − 1)^{n}I_{{r≠0}} on the left side of (5.2), and (x − 1)^{n}I_{{r=0}} on the right side of (5.2). Since (x − 1)^{n} = (x − 1)^{n}I_{{r≠0}} + (x − 1)^{n}I_{{r=0}}, we have s(n, n) = t(n, n)

We now assume that s(n, k +1) = t(n, k +1) to show that s(n, k) = t(n, k) for k ≥ 1. Letting a_{n}(x) = ∑_{k=0}^{n} b(n, k)(x − 1)^{k}, with b(0, 0) = 1 and b(x, y) = 0 if y > x, x < 0, or y < 0, we must show that

\begin{aligned}b(n, k) − ∑_{i=1}^{r} C_{i−1}b(n − i, k − 1) & = ∑_{i=1}^{r} C_{i−1} (b(n − i, k) − ∑_{j=1}^{r−i} C_{j−1}b(n − i − j, k − 1)) \\ & + ∑_{i=r+1}^{⌊ \frac{n+r+1}{2} ⌋} C_{i−1} (b(n − i, k) − ∑_{j=1}^{i−r} C_{j−1}b(n − i − j, k − 1)) \\ & + ∑_{i=⌊ \frac{n+r+1}{2} ⌋+1}^{n} C_{n−i} (b(i − 1, k) − ∑_{j=1}^{n−i+r} C_{j−1}b(i − j − 1, k − 1)) \\ & + b(n − 1, k − 1)I_{\{r=0\}}. \end{aligned} ; (5.3)

The cases r ≥ n are straightforward and are left to the reader. Below, we assume that r < n.

Using Lemma 4.2, and the inductive hypothesis for b(n, k + 1) we must show that

b(n − 1, k − 1) − ∑_{i=1}^{r} C_{i−1}b(n − i − 1, k − 2) = ∑_{i=1}^{r} C_{i−1}b(n − i − 1, k − 1)

− ∑_{i=1}^{r} ∑_{j=1}^{r−i} C_{i−1}C_{j−1}b(n − i − j − 1, k − 2)

+ ∑_{i=r+1}^{⌊ \frac{n+r+1}{2} ⌋} C_{i−1}b(n − i − 1, k − 1)

− ∑_{i=r+1}^{⌊ \frac{n+r+1}{2} ⌋} ∑_{j=1}^{i−r} C_{i−1}C_{j−1}b(n − i − j − 1, k − 2)

+ ∑_{i=⌊ \frac{n+r+1}{2} ⌋+1}^{n} C_{n−i}b(i − 2, k − 1)

− ∑_{i=⌊ \frac{n+r+1}{2} ⌋+1}^{n} ∑_{j=1}^{n−i+r} C_{n−i}C_{j−1}b(i − j − 2, k − 2)

− C_{⌊ \frac{n+r+1}{2} ⌋−1}C_{n−⌊ \frac{n+r+1}{2} ⌋−1}I_{\{k=1\}}

+ b(n − 2, k − 2)I_{{r=0}},

where the second to last term occurs for i = ⌊\frac{n+r+1}{2}⌋ and j = n − i in the second double sum of (5.3) (as this gives b(0, 0) which is equal to 1 and not 0 as would be given by the recurrence in Lemma 4.2).

We must consider two cases: n + r even and n + r odd. Assume that n + r is even; the case where n + r is odd is similiar. For n + r even we have ⌊\frac{n+r+1}{2}⌋ = ⌊\frac{n+r}{2}⌋. Using the inductive hypothesis for b(n − 1, k − 1) we are reduced to showing that

C_{n−⌊ \frac{n+r}{2} ⌋−1}b(⌊\frac{n + r}{2}⌋ − 1, k − 1) = C_{⌊ \frac{n+r}{2} ⌋−1}C_{n−⌊ \frac{n+r}{2} ⌋−1}

if k = 1, which holds since b(n, 0) = C_{n}, or

C_{n−⌊ \frac{n+r}{2} ⌋−1}b(⌊\frac{n + r}{2}⌋ − 1, k − 1) = C_{n−⌊ \frac{n+r}{2} ⌋−1} ∑_{i=1}^{⌊ \frac{n+r}{2} ⌋−1} C_{i−1}b(⌊\frac{n + r}{2}⌋ − i − 1, k − 2),

if k ≥ 2, which holds by Lemma 4.3, thereby completing the proof. □

6 D-Wilf Classes and h-Wilf Classes

No discussion of restricted permutations is complete without the discussion of Wilf classes, defined below, where S_{n}(T), T ⊆ S_{m}, is the set of π ∈ S_{n} which avoid all patterns in T and where s_{n}(T) = |S_{n}(T)|.

Definition 6.1 Let S_{1}, S_{2} ⊆ S_{m}. If s_{n}(S_{1}) = s_{n}(S_{2}) for all n ≥ m then we say that S_{1} and S_{2} are in the same Wilf class, or are Wilf equivalent.

Since we have refined the investigation of restricted permutations, we refine the notion of Wilf class with the following definition, where S_{n}^{k}(T), T ⊆ S_{m}, is the set of π ∈ S_{n} with exactly k fixed points which avoid all patterns in T and where s_{n}^{k}(T) = |S_{n}^{k}(T)|. We use D_{n}(T) and d_{n}(T) to represent S_{n}^{0}(T) and s_{n}^{0}(T), respectively.

Definition 6.2 Let S_{1}, S_{2} ⊆ S_{m}. If d_{n}(S_{1}) = d_{n}(S_{2}) for all n ≥ m we say that S_{1} and S_{2} are in the same D-Wilf class, or are D-Wilf equivalent. If s_{n}^{h}(S_{1}) = s_{n}^{h}(S_{2}) for h > 0, for all n ≥ m, h we say that S_{1} and S_{2} are in the same h-Wilf class, or are h-Wilf equivalent.

We will have need of the following lemma in the proofs below.

Lemma 6.1 Let γ ∈ S_{n} be given by γ_{i} = n+1−i for 1 ≤ i ≤ n. For π ∈ S_{n}, let π^{⋆} = γπγ^{−1}. Then, for all π, π and π^{⋆} have the same number of fixed points. Furthermore, the number of occurrences of the pattern 213 (respectively 312) in π equals the number of occurrences of the pattern 132 (respectively 231) in π^{⋆}.

Proof. Since π^{⋆} is obtained from π by conjugation, π and π^{⋆} have the same number of fixed points. If i < j < k are such that π_{i}π_{j}π_{k} is an occurrence of 213 (resp. 312), then γ_{k} < γ_{j} < γ_{i} are such that π_{γ_{k}}^{⋆}π_{γ_{j}}^{⋆}π_{γ_{i}}^{⋆} is an occurrence of 132 (resp. 231). □

We now state some results about refined Wilf classes.

Theorem 6.2 There are exactly three D-Wilf classes of patterns of length 3.

Proof. Applying Theorem 5.1 with r = 0 we see that, in particular, d_{n}(321) = d_{n}(132). Lemma 6.1 gives us d_{n}(132) = d_{n}(213) and d_{n}(231) = d_{n}(312).

Lastly, we note that d_{4}(123) = 7, d_{4}(132) = 6, and d_{4}(231) = 4, thereby giving three D-Wilf classes. □

Theorem 6.3 For any h > 0, there are exactly three h-Wilf classes of patterns of length 3.

Proof. We already have s_{n}^{h}(132) = s_{n}^{h}(213) = s_{n}^{h}(321) and s_{n}^{h}(231) = s_{n}^{h}(312) for all 1 ≤ h ≤ n. We now show that for h > 0, {s_{n}^{h}(132)}_{n≥3}, {s_{n}^{h}(231)}_{n≥3}, and {s_{n}^{h}(123)}_{n≥3} are different sequences, thereby showing that there are three h-Wilf classes for h > 0.

First, since s_{5}^{1}(123) = 20, s_{5}^{1}(231) = 16, s_{5}^{1}(132) = 13, s_{5}^{2}(123) = 2, s_{5}^{2}(231) = 8, and s_{5}^{2}(132) = 6 we have exactly three h-Wilf classes for h = 1, 2. Next, note that for h ≥ 3, s_{n}^{h}(123) = 0 since with three fixed points we have a 123 pattern. We conclude by showing that s_{h+2}^{h}(132) = h + 1 and s_{h+2}^{h}(312) ≥ 2h + 1, thereby giving exactly three h-Wilf classes for all h ≥ 3.

Let π ∈ S_{h+2}^{h}(132). To show that s_{h+2}^{h}(132) = h + 1, note that we can only have two entries of π which are not fixed points. Furthermore, 1 cannot be a fixed point, for otherwise all other entries must be fixed in order to avoid the 132 pattern. Hence, we have the freedom to pick exactly one of 2, 3 …, h + 2 to be a non-fixed point. This gives h + 1 choices.

Next, we show that s_{h+2}^{h}(312) ≥ s_{h+1}^{h−1}(312)+2, which gives s_{h+2}^{h}(312) ≥ 2h+1 since s_{3}^{1}(312) = 3. Consider the following procedure. Let π ∈ S_{h+1}^{h−1}(312). Let π̂_{i} = π_{i} + 1 for 1 ≤ i ≤ h + 1. Construct X = {1π̂_{1}π̂_{2} ⋯ π̂_{h+1}}∪{π_{1}π_{2} ⋯ π_{h+1}(h+2) : π_{1} ≠ 1}. It is clear that these sets are disjoint and that X ⊆ S_{h+2}^{h}(312). All that remains to be shown is that | {π_{1}π_{2} ⋯ π_{h+1}(h+2) : π_{1} ≠ 1} |= 2. To see this, note that S_{3}^{1}(312) = {132, 321, 213} contains two elements with π_{1} ≠ 1. By construction of the above procedure, these two elements beget two elements in S_{4}^{2}(312) such that π_{1} ≠ 1. This concludes the proof. □

We may further show, using Lemma 6.1, another result concerning Wilf classes. First, we remind the reader of the following definition from [Rob].

Definition 6.3 Let S ⊆ S_{m} and let T be a multiset of S_{m}. Define S_{n}(S; T) to be the set of π ∈ S_{n} which avoid all patterns in S and contain each element, including multiplicities, in T exactly once. Let s_{n}(S; T) = |S_{n}(S; T)|. Let S_{1}, S_{2} ⊂ S_{m} and let T_{1}, T_{2} be multisets of S_{m}. If s_{n}(S_{1}; T_{1}) = s_{n}(S_{2}; T_{2}) for all n ≥ m we say that (S_{1}; T_{1}) and (S_{2}; T_{2}) are in the same almost-Wilf class, or are almost-Wilf equivalent. We drop the set notation for a singleton set.

Next, we refine this definition.

Definition 6.4 Define S_{n}^{k}(S; T) to be those permutations in S_{n}(S; T) with exactly k fixed points. Let s_{n}^{k}(S; T) = |S_{n}^{k}(S; T)|. When k = 0 we write D_{n}(S; T), and d_{n}(S; T), respectively. If d_{n}(S_{1}; T_{1}) = d_{n}(S_{2}; T_{2}) for all n ≥ m we say that (S_{1}; T_{1}) and (S_{2}; T_{2}) are in the same almost-D-Wilf class, or are almost-D-Wilf equivalent. If s_{n}^{h}(S_{1}; T_{1}) = s_{n}^{h}(S_{2}; T_{2}) for h > 0 for all n ≥ m, h we say that (S_{1}; T_{1}) and (S_{2}; T_{2}) are in the same almost-h-Wilf class, or are almost-h-Wilf equivalent.

Theorem 6.4 Consider D_{n}(∅, α), α ∈ S_{3}. For these permutations there are exactly four almost-D-Wilf classes.

Proof. We first prove that d_{n}(∅; 321) = 0 for all n ≥ 3. Let cba be a 321 pattern in π ∈ S_{n}. Write π = W cXbY aZ. In order to avoid another 321 pattern we see that for w ∈ W and x ∈ X we must have w, x < b. Furthurmore, for y ∈ Y and z ∈ Z we must have y, z > b. Hence, b is a fixed point. Thus, the restriction of having exactly one 321 pattern implies a fixed point must be present.

Next, using Lemma 6.1, we see that d_{n}(∅; 132) = d_{n}(∅; 213) and d_{n}(∅; 231) = d_{n}(∅; 312). Lastly, since d_{5}(∅; 123) = 14, d_{5}(∅; 132) = 8, and d_{5}(∅; 231) = 6, we have exactly four almost-D-Wilf classes. □

7 Enumeration and Other Results

We start this section by tabulating s_{n}^{k}(α) for n ≤ 8 and 0 ≤ k ≤ 8 for all α ∈ S_{3} using the fact that there are only three D-Wilf classes.

In the following tables let n = 0, 1, … correspond to row n and k = 0, 1, 2, … correspond to the k^{th} term in from the left.

1

0  1
1  0  1
2  2  0  1
6  4  3  0  1
18  13  6  4  0  1
57  40  21  8  5  0  1
186  130  66  30  10  6  0  1
622  432  220  96  40  12  7  0  1

Values of s_{n}^{k}(132) = s_{n}^{k}(321) = s_{n}^{k}(213)

1

0  1
1  0  1
1  3  0  1
4  4  5  0  1
10  16  8  7  0  1
31  44  35  12  9  0  1
94  146  102  59  16  11  0  1
303  464  362  180  87  20  13  0  1

Values of s_{n}^{k}(231) = s_{n}^{k}(312)

0  1
1  0  1
2  3  0  0
7  4  3  0  0
20  20  2  0  0  0
66  48  18  0  0  0  0
218  183  28  0  0  0  0  0
725  552  153  0  0  0  0  0  0

Values of s_{n}^{k}(123)

From Corollary 3.3, Theorem 5.1, and Lemma 6.1 we have d_{n}(132) = d_{n}(321) = d_{n}(213) = F_{n} for n ≥ 1, where F_{n} is the n^{th} Fine number.

From the above triangles it appears that d_{n}(231) < F_{n} and d_{n}(123) > F_{n} for n ≥ 3. Unfortunately, we were unable to prove the latter assertion. However, we can prove the former via a bijection similar to one found in [Kra].

Theorem 7.1 Let F_{n} be the n^{th} Fine number. For all n ≥ 3, d_{n}(231) < F_{n}.

Proof. We first consider the following bijection γ : S_{n}(132) → SR_{n}. Let π ∈ S_{n}(132), π = π_{1}π_{2} ⋯ π_{n}. Let s = s_{n}s_{n−1} ⋯ s_{1} = γ(π) where s_{i} is the number of entries in π_{i+1}π_{i+2} ⋯ π_{n} which are larger than π_{i}. For example, γ(456312) = 010012.

The fact that π is 132-avoiding guarantees that s_{i−1} ≤ s_{i} + 1. Hence, s ∈ SR_{n}. The inverse bijection is obvious.

We now prove that if s ∉ SR_{n}(0) then γ^{−1}(s) is not a backward derangement. By observing that if π ∈ S_{n}(132) is a backward derangement then when π is read from right to left it becomes a member of D_{n}(231), we can conclude that D_{n}(231) ≤ |SR_{n}(0)| = F_{n}.

We must first take care of the case where γ(π) produces s_{1} = 0. In this case, it is obvious that π_{1} = n and hence π is not a backward derangement. We now assume that the first case of a double zero starts with s_{i+1}, i ≠ 0, so that s_{i+1} = s_{i} = 0. The bijection implies that π_{i} > π_{i+1} If there exists π_{k}, k < i, with π_{k} < π_{i+1} then π_{k}π_{i+1}π_{i} is an occurrence of the pattern 132, and hence is not allowed. Thus, all elements less than π_{i+1} are to the right of π_{i+1}. This implies that π_{n+1−π_{i+1}} = π_{i+1}.

We must now prove that the inequality is strict. We do this by giving π ∈ S_{n}(132) which is not a backward derangement for which γ(π) is nonsingular. For n odd γ(123 ⋯ n) = 012 ⋯ n − 1 and for n even γ(234 ⋯ (n − 1)1n) = 01123 ⋯ n − 2. Noting that both of the similarity relations produced by γ are nonsingular and correspond to permutations of S_{n}(132) which are not backward derangements completes the proof. □

We now turn our attention to the patterns 132, 321, and 213 (all of which are in the same D-Wilf class). Using Theorem 5.1, we are able to derive some formulas (recursive and “closed” form) for s_{n}^{k}(α), α ∈ {132, 321, 213}. First, we rederive items 2 and 4 of Theorem 2.1.

Let r = n in Theorem 5.1. Since E_{n,n} = C_{n} we have, using (4.1),

C_{n} = 2a_{n}(x) − xa_{n}(x) + (1 − x)^{2}a_{n−1}(x)  (7.1)

Equating the constant terms gives us C_{n} = 2d_{n}(α) + d_{n−1}(α) for α ∈ {132, 321, 213}. Hence, C_{n} = 2F_{n} + F_{n−1} is rederived. From here the derivation of item 4 in Theorem 2.1 uses either a straightforward induction or telescoping sum.

We can, of course, use (7.1) to derive recurrences for s_{n}^{k}(α), α ∈ {132, 321, 213}, for k ≠ 0. To this end, we have the following.

Theorem 7.2 For 0 ≤ k ≤ n, let F_{n}^{k} = s_{n}^{k}(α), α ∈ {132, 321, 213}. Define F_{n}^{−1} = 0. For n ≥ 2, we have for 0 ≤ k ≤ n,

2F_{n}^{k} + F_{n−1}^{k} = F_{n}^{k−1} + 2F_{n−1}^{k−1} − F_{n−1}^{k−2}.

Proof. Equate the coefficients of x^{k} in (7.1). □

We can now use a telescoping sum to show the following.

Theorem 7.3 Let C_{n} and F_{n} be the n^{th} Catalan and Fine number, respectively. Let α ∈ {132, 321, 213}. For n ≥ 1,

s_{n}^{1}(α) = \frac{1}{4} ∑_{i=0}^{n−1} (\frac{−1}{2})^{i} (C_{n−i} + 3F_{n−i−1}).

Proof. Routine. □

Other formulas for s_{n}^{k}(α), α ∈ {132, 321, 213}, k ≥ 2, similar to the one in Theorem 7.3 (which are based on Catalan and Fine numbers) can be derived using Theorem 7.2. However, these formulas are rather cumbersome. Instead, we present some nicer formulas. First, we have the following lemma, which introduces a generalization of the Catalan numbers.

Lemma 7.4 Let n ≥ 1. Write a_{n}(x) = ∑_{k=0}^{n} b(n, k)(x − 1)^{k}. Then

b(n, k) = \frac{k + 1}{n + 1}\binom{2n − k}{n}.

Proof. Using Lemma 4.2 it is routine to verify the stated formula. □

Since Lemma 7.4 gives us a natural generalization of the Catalan numbers, we define

C_{n}^{(k)} = \frac{k + 1}{n + 1}\binom{2n − k}{n}.  (7.2)

Using Lemma 7.4 it is easy to prove the following formulas. Theorem 7.5 Let α ∈ {132, 321, 213}. For n ≥ 1, 0 ≤ k ≤ n, we have

s_{n}^{k}(α) = ∑_{j=0}^{n−k}(−1)^{j}\binom{j + k}{k}C_{n}^{(k+j)},

i.e.

s_{n}^{k}(α) = ∑_{j=0}^{n−k}(−1)^{j} (\frac{j + k + 1}{n + 1}) \binom{2n − k − j}{n}\binom{j + k}{k}.

Proof. We have a_{n}(x) = ∑_{j=0}^{n} C_{n}^{(j)}(x − 1)^{j}. Expanding (x − 1)^{j} we get

a_{n}(x) = ∑_{j=0}^{n} ∑_{i=0}^{j}(−1)^{j−i}C_{n}^{(j)}\binom{j}{i}x^{i}.

Equating the coefficients of x^{k}, we get

s_{n}^{k}(α) = ∑_{j=k}^{n}(−1)^{j−k}C_{n}^{(j)}\binom{j}{k},

which, after a change of variable, gives the desired result. □ We now harvest some other interesting results. From Theorem 7.5 we have the following corollary which relates C_{n}^{(k)} and C_{n}. Corollary 7.6 Let C_{n} be the n^{th} Catalan number and let C_{n}^{(k)} be as defined in (7.2). Then, for n ≥ 0,

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

Proof. Since ∑_{k=0}^{n} s_{n}^{k}(α) = C_{n} for any α ∈ S_{3}, the result is immediate. □ We can also use Theorem 7.5 to rederive a formula for the Fine numbers given in [Deu].

Corollary 7.7 Let F_{n} be the n^{th} Fine number. For n ≥ 1,

F_{n} = ∑_{j=0}^{n}(−1)^{j}C_{n}^{(j)}.

As a consequence of C_{n} = 2F_{n} + F_{n−1} and the fact that F_{n} = d_{n}(α) for α ∈ {132, 213, 321} we get the following theorem. Theorem 7.8 Let α ∈ {132, 213, 321} and let F (π) be the set of fixed points of π ∈ S_{n}(α). Define

T_{n}(α) = {π ∈ S_{n}(α) : F (π) ∩ {1, 2, …, n − 1} ≠ ∅}.

Then |T_{n}(α)| = F_{n}, where F_{n} is the n^{th} Fine number.

Proof. We have C_{n} = s_{n}(α) and F_{n} = d_{n}(α). If U_{n}(α) = {π_{1} ⋯ π_{n−1}n : π ∈ D_{n−1}(α)} then S_{n}(α) is the disjoint union S_{n}(α) = D_{n}(α) ∪ T_{n}(α) ∪ U_{n}(α). Since C_{n} = 2F_{n} + F_{n−1}, the result follows. □

References

[Deu] E. Deutsch, Dyck Path Enumeration, Discrete Math. 204 (1999), 167-202.

[Fin] T. Fine, Extrapolation when Very Little is Known, Information and Control 16 (1970), 331-359.

[Kra] C. Krattenthaler, Permutations with Restricted Patterns and Dyck Paths, Advances in Applied Math. 27 (2001), 510-530.

[Knu] D. Knuth, \underline{The Art of Computer Programming}, vol. 3, Addison-Wesley, Reading, MA, 1973.

[Ric] D. Richards, Ballot Sequences and Restricted Permutations, Ars Combinatoria, 25 (1988), 83-86.

[Rob] A. Robertson, Permutations Restricted by Two Distinct Patterns of Length Three, Advance in Applied Math. 27, 548-561.

[Rog] D. G. Rogers, Similarity Relations on Finite Ordered Sets, Journal of Combinatorial Theory (A) 23 (1977), 88-98.

[Sha] L. W. Shapiro, A Catalan Triangle, Discrete Math. 14 (1976), 83-90.

[Slo] Sloane, N. J. A., The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/

∼njas/sequences, A009766.

[SS] R. Simion and F. Schmidt, Restricted Permutations, European Journal of Combinatorics 6 (1985), 383-406.

[SS2] F. Schmidt and R. Simion, Card Shuffling and a Transformation in S_{n}, Aeq. Math 44 (1992), 11-34.

[Str] V. Strehl, A Note on Similarity Relations, Discrete Math. 19 (1977), 99-101.

[Wes] J. West, Permutations with Forbidden Subsequences and Stack Sortable Permutations, Ph.D. Thesis, MIT, 1990.