Séminaire Lotharingien de Combinatoire 50 (2004), Article B50g

RESTRICTED PERMUTATIONS FROM CATALAN TO FINE AND BACK

Aaron Robertson^{1}

Department of Mathematics, Colgate University, Hamilton, NY 13346, U.S.A.

                           aaron@math.colgate.edu

Abstract

We give some history and recent results in the area of pattern restricted permutations. We also present a new bijection between certain pattern restricted permutations.

Introduction

It was a great pleasure to have been given the opportunity to speak at the landmark 50^{th} meeting of the Séminaire Lotharingien de Combinatoire, held in March 2003, at Domaine Saint Jacques, near Ottrott, France. The meeting was a wonderful celebration, replete with wonderful company, wonderful food, and, of course, wonderful mathematics.

This article is an expanded version of the talk that I presented at the meeting. We give some history and recent results in the area of pattern restricted permutations, as well as present a pertinent new bijection.

1. Preliminaries

We first get the definitions and notation out of the way.

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 order-equivalent to α. By order-equivalent we mean that the usual order on the integers is the same for both sequences. For example, 475 is order-equivalent to 132 since both have smallest element first, largest element second, and middle element last. If π does not contain a pattern β, we say that π is β-avoiding. We write S_{n}(β) for the set of permutations of S_{n} that are β-avoiding.

We next extend this notation. Let S = ⋃_{n} S_{n}. Let T ⊆ S and let R be a multisubset of S. Then S_{n}(T) is the set of permutations of S_{n} that avoid all patterns in T while S_{n}(T; R) is the set of permutations of S_{n}(T) that contain each pattern (including multiplicities) in R exactly once. If |T | = 1 or |R| = 1 then we drop the set notation.

So, for example, S_{n}(132, {123, 123}) is the set of 132-avoiding permutations in S_{n} that contain exactly two 123 patterns. As a concrete example, 124635 ∈ S_{6}(321; 213).

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

2000 Mathematics Subject Classification: 05A15, 68R15

One last bit of notation: we let s_{n}(R) = |S_{n}(R)| and s_{n}(R; T) = |S_{n}(R; T)|.

2. Some History

In 1838, Catalan [3] defined what we now call the Catalan numbers:

\frac{1}{n + 1}\binom{2n}{n} = C_{n}.

In this paper he addressed the question

De combien de manières peut-on effectuer le produit de n facteurs différents?

and used essentially an argument that shows that s_{n}(132) = C_{n} by proving that C_{n} = ∑_{i=1}^{n} C_{i−1}C_{n−i}. This argument that shows s_{n}(132) = C_{n} goes as follows. Let π = π_{1}π_{2} … π_{n} and let π_{i} = n. Then π_{1} … π_{i−1} must consist of the elements n−i+1, n−i+2, …, n−1 and π_{i+1} … π_{n} must consist of the elements 1, 2, …, n − i, for otherwise π_{j} n π_{k} would be a 132 pattern for some j, k, j < i < k. Next, π_{1} … π_{i−1} and π_{i+1} … π_{n} must each be 132-avoiding permutations themselves. Hence, we have

s_{n}(132) = ∑_{i=1}^{n} s_{i−1}(132)s_{n−i}(132),

which gives (using initial conditions) s_{n}(132) = C_{n}.

Of course, Catalan did not consider s_{n}(132). It was not until 1915 that s_{n}(α) was determined for the first time for some α ∈ S_{3}. MacMahon [see 14] proved that s_{n}(123) = C_{n}. This result also gives us s_{n}(321) = C_{n} by reading permutations from right-to-left instead of left-to-right. This re-reading is called the reversal bijection, one of the three standard bijections.

2.1 Three Standard Bijections

There are three standard bijections that allow us to look at a smaller number of patterns when considering pattern-avoiding permutations. We define the following bijections.

The reversal bijection: r : S_{n} → S_{n}, π_{1}π_{2} … π_{n} ↦ π_{n} … π_{2}π_{1}.

The complement bijection: c : S_{n} → S_{n}, π_{1}π_{2} … π_{n} ↦ (n+1−π_{1})(n+1−π_{2}) … (n+1−π_{n}).

The inverse bijection i : S_{n} → S_{n}, π ↦ π^{−1} (group theoretic).

Using these bijections we see that π ∈ S_{n}(α) if and only if x(π) ∈ S_{n}(x(α)) where x is one of r, c, i.

2.2 More Recent History

It was not until 1973 that the first non-monotonic pattern restricted permutations were considered. Knuth [12] showed that s_{n}(231) = C_{n}. Now, since r(231) = 132, c(231) = 213, and i(231) = 312, Knuth’s and MacMahon’s results show that s_{n}(α) = C_{n} for any α ∈ S_{3}.

This result leads us to the following definition.

Definition. We say that two patterns α and β are in the same Wilf class or are Wilf equivalent if and only if s_{n}(α) = s_{n}(β) for all n.

Hence, there is one Wilf class for patterns of length 3. However, historically it was not shown that s_{n}(123) = s_{n}(132) directly, rather that they are both equal to C_{n}. This leads us into our next section.

3. Some Bijections

Using the three standard bijections we have s_{n}(123) = s_{n}(321) and s_{n}(132) = s_{n}(213) = s_{n}(231) = s_{n}(312). The fact that s_{n}(123) = s_{n}(132) as well is surprising. Hence, we will look at some bijections from S_{n}(\overline{123}) to S_{n}(\overline{132}), where \overline{123} means any element from \{123, 321\} and \overline{132} means any element from \{132, 213, 231, 312\} since these are equivalent by the standard bijections.

The first bijection (1975) is due to Rotem [26]. He used ballot sequences and binary trees as an intermediate step from S_{n}(321) to S_{n}(231). The first direct bijection was given by Simion and Schmidt [27] in 1985. In more recent years, West [30] has used generating trees while Stanley [29] and Krattenthaler [13] have used Dyck paths.

3.1 A New Bijection

We give a new direct bijection γ : S_{n}(321) → S_{n}(132). In order to present γ we give a definition.

Definition. Let k ≥ 2. Let α = α_{1} … α_{k} and β = β_{1} … β_{k} be two distinct occurrences of 1k(k − 1) … 2 in π. We say α is smaller than β if there exists i, 1 ≤ i ≤ k, such that π^{−1}(α_{j}) = π^{−1}(β_{j}) for all j < i and π^{−1}(α_{i}) < π^{−1}(β_{i}).

We can now describe the bijection γ : S_{n}(321) → S_{n}(132). Let π_{1}π_{2} … π_{n} = π ∈ S_{n}(321) and let xzy = π_{p_{1}}π_{p_{2}}π_{p_{3}} be the smallest 132 occurrence in π. If no such occurrence exists, γ(π) = π. Otherwise, let M be the operation that creates the permutation Mπ where Mπ_{i} = π_{i} if i ∉ {p_{1}, p_{2}, p_{3}} and Mπ_{p_{1}} = z, Mπ_{p_{2}} = y, and Mπ_{p_{3}} = x. Now let xzy be the smallest 132 occurrence in Mπ and apply M again. Repeat until the resulting permutation is 132-avoiding.

Example. Let π = 35612487 ∈ S_{8}(321), a permutation that has eight 132 occurrences, the smallest one being 354. We apply M to get Mπ = 54612387. Notice that the 354 is changed to 543 in the same positions and all other elements are left untouched. Now, in 54612387, 587 is the smallest occurrence. Apply M again to get M^{2}π = 84612375. Continuing, we get M^{3}π = 86512374 and M^{4}π = 86572341. Since 86572341 ∈ S_{8}(132), γ(35612487) = 86572341.

Of course, we must prove that this is a bijection. We start by showing that γ is well-defined. Our approach is to show that, with respect to the indices of elements, the smallest 132 occurrence in Mτ is larger than the smallest 132 occurrence in τ. Hence, M^{j}τ must be 132-avoiding for some finite j.

Write τ = τ_{1}τ_{2} … τ_{n} and let τ_{i}τ_{j}τ_{k} be the smallest 132 occurrence. Clearly, since τ has no 132 occurrence τ_{x}τ_{y}τ_{z} with x < i, Mτ could only possibly have such an occurrence if {i, j, k} ∩ {y, z} ≠ ∅. Since τ_{i}τ_{j}τ_{k} is the smallest 132 occurrence in τ, τ_{x} > τ_{k} and thus i, k ∉ {y, z}. Hence, we must have j ∈ {y, z}. From the minimality of τ_{i}τ_{j}τ_{k}, clearly j ≠ z. Thus, τ_{x}τ_{j}τ_{z} with i < z < j is our only possibility. But, τ_{z} > τ_{x} > τ_{k} implies that τ_{i}τ_{z}τ_{k} is a smaller 132 occurrence in τ than τ_{i}τ_{j}τ_{k}, a contradiction.

Next, assume, for a contradiction, that τ_{j}τ_{x}τ_{y} in Mτ is a smaller 132 occurrence (with respect to the indices) than τ_{i}τ_{j}τ_{k} is in τ. This implies that τ_{i}τ_{x}τ_{k} is a smaller 132 occurrence in τ than τ_{i}τ_{j}τ_{k}, contradicting the minimality of τ_{i}τ_{j}τ_{k}.

We now show that γ is a bijection; it is enough to give γ^{−1}. To do so, we make the following definition.

Definition. Let k ≥ 2. Let α = α_{1} … α_{k} and β = β_{1} … β_{k} be two distinct occurrences of k(k − 1) … 1 in π. We say α is larger that β if there exists i, 1 ≤ i ≤ k, such that π^{−1}(α_{j}) = π^{−1}(β_{j}) for all j > i and π^{−1}(α_{i}) > π^{−1}(β_{i}).

We can now describe γ^{−1} : S_{n}(132) → S_{n}(321). Let π_{1}π_{2} … π_{n} = π ∈ S_{n}(132) and let zyx = π_{p_{1}}π_{p_{2}}π_{p_{3}} be the largest 321 occurrence in π. If no such occurrence exists, γ^{−1}(π) = π. Otherwise, let N be the operation that creates the permutation N π where N π_{i} = π_{i} if i ∉ {p_{1}, p_{2}, p_{3}} and N π_{p_{1}} = x, N π_{p_{2}} = z, and N π_{p_{3}} = y. Now let zyx be the largest 321 occurrence in N π and apply N again. Repeat until the resulting permutation is 321-avoiding.

It is easy to check that γ^{−1}γ(π) = π for any π ∈ S_{n}(321).

We can extend γ to a bijection Γ_{k} : S_{n}(k(k−1) … 1) → S_{n}(1k(k−1) ⋯ 2) for any k ≥ 2. Let π_{1}π_{2} … π_{n} = π ∈ S_{n}(k(k − 1) … 1) and let α = π_{p_{1}}π_{p_{2}} … π_{p_{k}} be the smallest 1k(k − 1) … 2 occurrence in π. If no such occurrence exists, Γ_{k}(π) = π. Otherwise, let P be the operation that creates the permutation Pπ where Pπ_{i} = π_{i} if i ∉ {p_{1}, p_{2}, …, p_{k}} and Pπ_{p_{i}} = π_{p_{i+1 (mod k)}} for i = 1, 2, …, k.

Now let α be the smallest 1k(k − 1) … 2 occurrence in Pπ and apply P again. Repeat until the resulting permutation avoids the pattern 1k(k − 1) … 2.

To prove that Γ_{k} is well-defined we show that, with respect to the indices of elements, the smallest 1k … 2 occurrence in Pπ is larger than the smallest 1k … 2 occurrence in π. Hence, P^{j}τ has no 1k … 2 occurrence for some finite j.

Let τ be our permutation and let γ_{1} … γ_{k} be the smallest 1k … 2 occurrence in τ. Assume, for a contradiction, that Pτ has a 1k … 2 occurrence σ = σ_{1} … σ_{k} with σ_{1}^{−1} < γ_{1}^{−1}. Since τ has no such occurrence, we must have

{σ_{1}, …, σ_{k}} ∩ {γ_{1}, …, γ_{k}} ≠ ∅.

Let γ_{j} be the minimal element in the above intersection such that there exists ℓ ≥ 1, ℓ maximal, where we have (in Pτ)

σ = σ_{1} … σ_{i−1}γ_{j}σ_{i+1} … σ_{i+ℓ}σ_{i+ℓ+1} … σ_{k}  (1)

with

{σ_{i+1}, …, σ_{i+ℓ}} ∩ {γ_{1}, …, γ_{k}} = ∅  (2)

(so that {σ_{i+ℓ+1}, …, σ_{k}} ⊆ {γ_{1}, …, γ_{k}} where {σ_{i+ℓ+1}, …, σ_{k}} is possibly empty). We may further require that there do not exist γ_{m+1}, …, γ_{m+ℓ} such that

σ_{1} … σ_{i−1}γ_{j}γ_{m+1} … γ_{m+ℓ}σ_{i+ℓ+1} … σ_{k}  (3)

is also a 1k … 2 occurrence.

Since this is quite a bit to require of γ_{j}, we must prove its existence. Assume, for a contradiction, that no such γ_{j} exists. Then, for all γ_{i}, 1 ≤ i ≤ k, we have no such ℓ satisfying (1) and (2), or there exist γ_{m+1}, …, γ_{m+ℓ} such that (3) is also a 1k … 2 occurrence. In either case, there exists a 1k … 2 occurrence of the form σ_{1} … σ_{x}γ_{y} … γ_{z} in Pτ with {σ_{1}, …, σ_{x}} ∩ {γ_{1}, …, γ_{k}} = ∅ and hence, σ_{1} … σ_{x}γ_{y} … γ_{z} is also in τ, a contradiction since such an occurrence is smaller than γ_{1} … γ_{k}.

We rewrite (1) as

σ_{1} … σ_{i−1}γ_{j}σ_{i+1} … σ_{i+ℓ}γ_{j+m+1} … σ_{k}.  (4)

From (4) we must have, by assumption (3), |{γ_{j+1}, …, γ_{j+m}}| < |{σ_{i+1}, …, σ_{i+ℓ}}|. But then

γ_{1} … γ_{j−1}σ_{i+1} … σ_{i+ℓ}γ_{j+m+1} … γ_{k}

contains a smaller 1k … 2 occurrence in τ than γ_{1} … γ_{k}, a contradiction. Thus, Pτ contains no 1k … 2 occurrence σ_{1} … σ_{k} with σ_{1}^{−1} < γ_{2}^{−1} (order in Pτ).

To finish proving that Γ_{k} is well-defined, assume, for a contradiction, that γ_{2}β_{1} … β_{k−1} in Pτ is a smaller 1k … 2 occurrence (with respect to the indices) than γ_{1} … γ_{k} is in τ. Then we must have β_{1}^{−1} < γ_{3}^{−1} (order in Pτ). However, this implies that γ_{1}β_{1}γ_{3} … γ_{k} is a smaller 1k … 2 occurrence in τ than γ_{1} … γ_{k}, a contradiction. This concludes the proof that Γ_{k} is well-defined.

To show that Γ_{k} is a bijection, note that Γ_{k}^{−1} is found by using the operation Q where Qπ_{i} = π_{i} if i ∉ {p_{1}, p_{2}, …, p_{k}} and Qπ_{p_{i}} = π_{p_{i−1 (mod k)}} for i = 1, 2, …, k.

Using Γ_{k}, along with the standard bijections, we immediately have the following theorem.

Theorem. Let k ≥ 2. The following patterns are Wilf equivalent.

\begin{matrix}A. k(k − 1) ⋯ 1 & B. 1k(k − 1) ⋯ 2 \\ C. 12 ⋯ k & D. 23 ⋯ k1 \\ E. k12 ⋯ (k − 1) & F. (k − 1)(k − 2) ⋯ 1k \end{matrix}

Remark. Γ_{4} proves the Wilf equivalence of 1234 and 4123, a result of Stankova [28].

4. Enumeration Results

In this section we give some enumeration results along with their relevant references. The first table gives the number of permutations that avoid a single pattern.

Avoid 1

Class W  s_{n}(T), T ∈ W  References
\overline{(123)} C_{n} = \frac{1}{n+1} \binom{2n}{n}  [14], [12]
\overline{(1234)} 2 ∑_{k=0}^{n} \binom{2k}{k}\binom{n}{k}^{2} \frac{3k^{2}−(2k+1)(n−1)}{(k+1)^{2}(k+2)(n−k+1)}  [10]
\overline{(1342)} \frac{(−1)^{n−1}(7n^{2}−3n−2)}{2} + 3 ∑_{k=2}^{n}(−1)^{n−k}2^{k}\binom{2k−4}{k−2} \frac{(n−k+2)(n−k+1)}{k(k+1)} [1]
\overline{(1324)} ?  open

\overline{(123)} = S_{3}; \overline{(1234)} = \{1234, 1243, 2134, 2143, 3412, 3421, 4312, 4321\}; \overline{(1342)} = \{1342, 1423, 2341, 2413, 2431, 3124, 3142, 3241, 4132, 4213\}; \overline{(1324)} = \{1324, 4231\}.

We continue with a table giving the number of permutations that contain a given pattern exactly once.

Contain 1

Class W s_{n}(T), T ∈ W Reference
\overline{(∅; 123)} \frac{3}{n} \binom{2n}{n−3} for n ≥ 3 [20]
\overline{(∅; 132)} \binom{2n−3}{n−3} for n ≥ 3 [2]

\overline{(∅; 123)} = \{(∅; 123), (∅; 321)\}; \overline{(∅; 132)} = \{(∅; 132), (∅; 213), (∅; 231), (∅; 312)\}.

The penultimate table gives the number of permutations that avoid a given pattern and contain a different given pattern exactly once. The last table gives the number of permutations that contain each of two given (not necessarily distinct) patterns exactly once.

Avoid 1, Contain 1

Class W  s_{n}(T), T ∈ W  Reference

\overline{(123; 321)} 0 for n ≥ 6  —–

\overline{(123; 132)} (n − 2)2^{n−3} for n ≥ 3 [20]

\overline{(123; 231)} 2n − 5 for n ≥ 3  [17]

\overline{(132; 213)} n2^{n−5} for n ≥ 4  [16]

\overline{(132; 231)} 2^{n−3} for n ≥ 3  [16]

\overline{(123; 321)} = \{(123; 321), (321; 123)\}; \overline{(123; 132)} = \{(123; 132), (123; 213), (132; 123), (213; 123), (231; 321), (312; 321), (321; 231), (321; 312)\}; \overline{(123; 231)} = \{(123; 231), (123; 312), (132; 321), (213; 321), (231; 123), (312; 123), (321; 132), (321; 213)\}; \overline{(132; 213)} = \{(132; 213), (213; 132), (231; 312), (312; 231)\}; \overline{(132; 231)} = \{(132; 231), (132; 312), (213; 231), (213; 312), (231; 132), (231; 213), (312; 132), (312; 213)\}.

Contain 2

Class W  s_{n}(T), T ∈ W  Reference

\overline{(∅; \{123, 321\})} 0 for n ≥ 6  —–

\overline{(∅; \{123, 231\})} 2n − 5 for n ≥ 5  [23]

\overline{(∅; \{123, 132\})} \binom{n−3}{2}2^{n−4} for n ≥ 5  [22]

\overline{(∅; \{132, 213\})} (n^{2} + 21n − 28)2^{n−9} for n ≥ 7 [23]

\overline{(∅; \{132, 231\})} 2^{n−3} for n ≥ 4  [23]

\overline{(∅; \{123, 123\})} \frac{59n^{2}+117n+100}{2n(2n−1)(n+5)} \binom{2n}{n−4} for n ≥ 4 [9]

\overline{(∅; \{132, 132\})} \frac{(n−2)^{2}(n+21)−4}{2n(n−1)} \binom{2n−6}{n−4} for n ≥ 4 [15]

\overline{(∅; \{123,321\})} = \{(∅; \{123, 321\}), (∅; \{321, 123\})\}; \overline{(∅; \{123, 231\})} = \{(∅; \{123, 231\}), (∅; \{123, 312\}), (∅; \{132, 321\}), (∅; \{213, 321\})\}; \overline{(∅; \{123, 132\})} = \{(∅; \{123, 132\}), (∅; \{123, 213\}), (∅; \{231, 321\}), (∅; \{312, 321\})\}; \overline{(∅; \{132, 213\})} = \{(∅; \{132, 213\}), (∅; \{231, 312\})\}; \overline{(∅; \{132, 231\})} = \{(∅; \{132, 231\}), (∅; \{132, 312\}), (∅; \{213, 231\}), (∅; \{213, 312\})\}; \overline{(∅; \{123, 123\})} = \{(∅; \{123, 123\}), (∅; \{321, 321\})\}; \overline{(∅; \{132, 132\})} = \{(∅; \{132, 132\}), (∅; \{213, 213\}), (∅; \{231, 231\}), (∅; \{312, 312\})\}.

5. An Interesting Generating Function

An interesting generating function can be obtained when we consider {s_{n}(132; {(123)^{r}})}_{n}. To this end, let

f(x, y; k) = ∑_{n,r} s_{n}(132, {(123 … k)^{r}})x^{n}y^{r}.

In [25], the authors show that

f(x, y; 3) = \frac{1}{1 − \frac{x}{1 − \frac{x}{1 − \frac{xy}{1 − \frac{xy^{3}}{1 − \frac{xy^{6}}{...}}}}}}

in which the n^{th} numerator is xy^{\binom{n−1}{2}}. This result was the apparent impetus for several papers, of which we note a few.

Let F_{r}(x; k) = [y^{r}]f(x, y; k), i.e., the coefficient of y^{r} in f(x, y; k). Let U_{n}(x) denote the Chebyshev polynomials of the second kind, defined by

U_{n}(cos(x)) = \frac{sin((n + 1)x)}{sin(x)}.

Mansour and Vainshtein [18] show that for any k ≥ 1 and 1 ≤ r ≤ k(k + 3)/2,

F_{r}(x; k) = \frac{x^{\frac{r−1}{2}} U_{k−1}^{r−1} (\frac{1}{2\sqrt{x}})}{U_{k}^{r+1} (\frac{1}{2\sqrt{x}})} ∑_{j=0}^{⌊(r−1)/k⌋} \binom{r − kj + j − 1}{j} (\frac{U_{k} (\frac{1}{2\sqrt{x}})}{x^{\frac{k−2}{2k}} U_{k−1} (\frac{1}{2\sqrt{x}})})^{kj} .

(The case F_{0}(x; k) had already been determined in terms of Chebyshev polynomials by Chow and West [4].)

This result was followed closely by a result of Jani and Rieper [11], who give a bijection between ordered trees and S_{n}(132; {(123 … k)^{r}}).

We then come to a quote found in [13]:

Whenever you encounter generating functions which can be expressed in terms of continued fractions or Chebyshev polynomials, then expect that Dyck or Motzkin paths are at the heart of your problem, and will help to solve it.

- Krattenthaler In this paper, Krattenthaler reproves and extends all the above results as well as proves new ones with continued fractions, Chebyshev polynomials of the second kind, and Dyck and Motzkin paths.

6. Refined Restricted Permutations

Combinatorics without algebra ... is like sex without love.

- Anthony Joseph

We now move on to some very recent results on restricted permutations. In [24], the study of restricted permutations refined by the number of fixed points was initiated (to the best of my knowledge) in an attempt to combine the “purely combinatorial” with the algebraic properties of permutations.

We first look at restricted permutations classified by cycle structure.

Cycle structure S_{6}(123) S_{6}(132) S_{6}(213) S_{6}(321) S_{6}(231) S_{6}(312)
1^{6}  0  1  1  1  1  1
1^{4}2^{1}  0  5  5  5  9  9
1^{3}3^{1}  0  8  8  8  12  12
1^{2}2^{2}  10  9  9  9  18  18
1^{2}4^{1}  8  12  12  12  17  17
1^{1}2^{1}3^{1}  24  20  20  20  24  24
1^{1}5^{1}  24  20  20  20  20  20
2^{3}  10  5  5  5  4  4
2^{1}4^{1}  26  20  20  18  12  12
3^{2}  6  8  8  10  3  3
6^{1}  24  24  24  24  12  12
Sum  132  132  132  132  132  132

In this table, we see that S_{6}(132) and S_{6}(213) have the same cycle structure breakdown, and that the same holds true for S_{6}(231) and S_{6}(312). This is fairly easy to explain.

Theorem (Robertson, Saracino, Zeilberger [24]) Let γ ∈ S_{n} be given by γ_{i} = n + 1 − i for 1 ≤ i ≤ n. For π ∈ S_{n}, let π^{⋆} = γπγ^{−1}. The number of occurrences of the pattern 213 (resp.

312) in π equals the number of occurrences of the pattern 132 (resp. 231) in π^{⋆}.

This is just the reversal bijection followed by the complement bijection. However, written in the above form as a conjugation, we see that the cycle structure is preserved.

Digging a little deeper into the cycle structure breakdown, we notice that S_{6}(321) has a breakdown very close to that of S_{6}(132). In fact, the only place where a difference occurs in the table is boxed in. And, if we look at the number of fixed points, we have the same breakdown according to the number of fixed points.

Let S_{n}^{k}(S; T) be the elements of S_{n}(S; T) with exactly k fixed points and let s_{n}^{k}(T) = |S_{n}^{k}(T)|.

Robertson, Saracino, and Zeilberger [24] prove that for all n and all k, 0 ≤ k ≤ n,

• s_{n}^{k}(132) = s_{n}^{k}(231) = s_{n}^{k}(321)

• s_{n}^{k}(231) = s_{n}^{k}(312)

• s_{n}^{k}(123)

are the three classes, where we have

\begin{matrix}_{n}⧹^{k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 0 & 1 \\ 1 & 0 & 1 \\ 2 & 1 & 0 & 1 \\ 3 & 2 & 2 & 0 & 1 \\ 4 & 6 & 4 & 3 & 0 & 1 \\ 5 & 18 & 13 & 6 & 4 & 0 & 1 \\ 6 & 57 & 40 & 21 & 8 & 5 & 0 & 1 \\ 7 & 186 & 130 & 66 & 30 & 10 & 6 & 0 & 1 \\ 8 & 622 & 432 & 220 & 96 & 40 & 12 & 7 & 0 & 1 \end{matrix} \begin{matrix}_{n}⧹^{k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 0 & 1 \\ 1 & 0 & 1 \\ 2 & 1 & 0 & 1 \\ 3 & 1 & 3 & 0 & 1 \\ 4 & 4 & 4 & 5 & 0 & 1 \\ 5 & 10 & 16 & 8 & 7 & 0 & 1 \\ 6 & 31 & 44 & 35 & 12 & 9 & 0 & 1 \\ 7 & 94 & 146 & 102 & 59 & 16 & 11 & 0 & 1 \\ 8 & 303 & 464 & 362 & 180 & 87 & 20 & 13 & 0 & 1 \end{matrix} \begin{matrix}_{n}⧹^{k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 0 & 1 \\ 1 & 0 & 1 \\ 2 & 1 & 0 & 1 \\ 3 & 2 & 3 & 0 & 0 \\ 4 & 7 & 4 & 3 & 0 & 0 \\ 5 & 20 & 20 & 2 & 0 & 0 & 0 \\ 6 & 66 & 48 & 18 & 0 & 0 & 0 & 0 \\ 7 & 218 & 183 & 28 & 0 & 0 & 0 & 0 & 0 \\ 8 & 725 & 552 & 153 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}

s_{n}^{k}(132) = s_{n}^{k}(213) = s_{n}^{k}(321)  s_{n}^{k}(231) = s_{n}^{k}(312)  s_{n}^{k}(123)

It is quite amazing that s_{n}^{k}(132) = s_{n}^{k}(321). Robertson, Saracino, and Zeilberger [24] give a fairly technical proof. This was followed by a proof due to Elizalde [7], a student of Stanley, who refines this result further by showing that we have “number of excedances” in addition to the number of fixed points. Pak and Elizalde [21] follow this up by giving a nice bijective proof.

An interesting sequence appears when we consider 132-avoiding derangements. We see that

{s_{n}^{0}(132)}_{n≥0} = 1, 0, 1, 2, 6, 18, 57, 186, 622, ….

This is Fine’s sequence, initially given in [8], which stems from similarity relations. (For a good survey of Fine’s sequence, see [6].) Fine’s sequence {F_{n}}_{n≥0} is characterized by

2F_{n} + F_{n−1} = C_{n},  (5)

which may be thought of as the defining equation for the sequence.

We now take a very brief sidestep to look at similarity relations.

Definition. 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. R is said to have k isolated points if k is the number of i ∈ {1, 2, …, n} such that there does not exist 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.

In [24], the authors show that, s_{n}^{k}(321) = |SR_{n}(k)|, a somewhat unexpected connection between two at-first-sight unrelated structures.

Stepping back to refined restricted permutations, in [24] we find that, for α ∈ {132, 213, 321}, 0 ≤ k ≤ n:

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

In particular we obtain a formula for the Fine numbers:

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

The worst thing you can do to a problem is solve it completely.

- Dan Kleitman

As such, there are no nontrivial enumerations of s_{n}^{k}(α) for α ∈ {123, 231, 312} in [24].

Another unanswered question, begging for a solution, follows. For β ∈ {132, 213, 321} we have from (5)

2s_{n}^{0}(β) + s_{n−1}^{0}(β) = s_{n}(δ)

for any δ ∈ S_{3}. Can this be explained bijectively by letting δ = β?

The next set of results on refined restricted permutations comes from [19]: following the steps of Simion and Schmidt, Mansour and Robertson [19] provide enumerative results for S_{n}^{k}(S) for all S ⊆ S_{3}, |S| ≥ 2.

6.1 Refined Restricted Involutions

From the cycle structure breakdown table we notice that if we restrict our attention to involutions it appears that we may have some more unexpected structure.

Define i_{n}^{k}(S; T) to be the number of elements of S_{n}^{k}(S; T) that are involutions.

Deutsch, Robertson, and Saracino [5] prove that

• i_{n}^{k}(132) = i_{n}^{k}(231) = i_{n}^{k}(321)

• i_{n}^{k}(231) = i_{n}^{k}(312)

• i_{n}^{k}(123)

are the three classes. The proofs use the RSK correspondence as well as provide new bijections with Dyck paths. One particularly nice formula follows. For α ∈ {132, 213, 321}, 0 ≤ k ≤ n,

i_{n}^{k}(α) = \begin{cases}\frac{k+1}{n+1} \binom{n+1}{\frac{n−k}{2}} & for n + k even \\ 0 & for n + k odd. \end{cases}

Catalan strikes again!

i_{2n}^{0}(132) = C_{n} = i_{2n−1}^{1}(132).

Hence, the number of 132-avoiding permutations on n letters is the Catalan number; the number of 132-avoiding derangements on n letters is the Fine number; and the number of 132-avoiding derangement involutions on 2n letters is the Catalan number. Having gone from Catalan to Fine and back, we stop.

References

[1] M. Bóna, Exact Enumeration of 1342-avoiding Permutations; A Close Link with Labeled Trees and Planar Maps, J. Comb. Theory, Series A 175 (1997), 55-67.

[2] M. Bóna, Permutations with One or Two 132-sequences, Discrete Math. 181 (1998), 267-274.

[3] E. Catalan, Note sur une Équation aux Differences Finies, J. Math. Pures et Appliqués 3 (1838), 508-516.

[4] T. Chow and J. West, Forbidden Subsequences and Chebyshev Polynomials, Discrete Math. 204 (1999), 119-128.

[5] E. Deutsch, A. Robertson, and D. Saracino, Refined Restricted Involutions, arχiv: math.CO/0212267.

[6] E. Deutsch and L. Shapiro, A Survey of the Fine Numbers, Discrete Math. 241 (2001), 241-265.

[7] S. Elizalde, Fixed Points and Excedances in Restricted Permutations, arχiv: math.CO/0212221.

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

[9] M. Fulmek, Enumeration of Permutations Containing a Prescribed Number of Occurrences of a Pattern of Length Three, Adv. Appl. Math. 30 (2003), 607-632.

[10] I. Gessel, Symmetric Functions and P-recursiveness, J. Comb. Theory, Series A 53 (1990), 257-285.

[11] M. Jani and R. Rieper, Continued Fractions and Catalan Problems, Electron. J. Comb. 7 (2000), R45.

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

[13] C. Krattenthaler, Restricted Permutations, Continued Fractions, and Chebyshev Polynomials, Adv. Appl. Math. 27 (2001), 510-530.

[14] P. MacMahon, \underline{Combinatory Analysis}, Chelsea Publishing Co., New York, 1960.

[15] T. Mansour and A. Vainshtein, Counting Occurrences of 132 in a Permutation, Adv. Appl. Math. 28 (2002), 185-195.

[16] T. Mansour and A. Vainshtein, Restricted 132-avoiding Permutations, Adv. Appl. Math. 26 (2001), 258-269.

[17] T. Mansour and A. Vainshtein, Restricted Permutations and Chebyshev Polynomials, Sém. Lothar. Combin. 47 (2001/02), Article B47c.

[18] T. Mansour and A. Vainshtein, Restricted Permutations, Continued Fractions, and Chebyshev Polynomials, Electron. J. Comb. 7 (2000), R17.

[19] T. Mansour and A. Robertson, Refined Restricted Permutations Avoiding Subsets of Patterns of Length

Three, arχiv: math.CO/0204005.

[20] J. Noonan, The Number of Permutations Containing Exactly One Increasing Subsequence of Length Three, Discrete Math. 152 (1996), 307-313.

[21] I. Pak and S. Elizalde, Bijections for Refined Restricted Permutations, arχiv: math.CO/0212328.

[22] A. Robertson, Permutations Containing and Avoiding 123 and 132 Patterns, Discrete Math. and Theoretical Comp. Sci. 4 (1999), 151-154.

[23] A. Robertson, Permutations Restricted by Two Distinct Patterns of Length Three, Adv. Appl. Math. 27 (2001), 548-561.

[24] A. Robertson, D. Saracino, and D. Zeilberger, Refined Restricted Permutations, arχiv: math.CO/0203033.

[25] A. Robertson, H. Wilf, and D. Zeilberger, Permutation Patterns and Continued Fractions, Electron. J. Comb. 6 (1999), R38.

[26] D. Rotem, On a Correspondence Between Binary Trees and a Certain Type of Permutation, Information Processing Letters 4 (1975), 58-61.

[27] R. Simion and F. Schmidt, Restricted Permutations, Europ. J. Comb. 6 (1985), 383-406.

[28] Z. Stankova, Classification of Forbidden Subsequences of Length 4, Europ. J. Comb. 17 (1996), 501-517.

[29] R. Stanley, \underline{Enumerative Combinatorics}, vol. 2, Cambridge University Press, 1999.

[30] J. West, Generating Trees and the Catalan and Schröder Numbers, Discrete Math. 146 (1995), 247-262.