Séminaire Lotharingien de Combinatoire 60 (2008), Article B60d

CLASSIFICATION OF BIJECTIONS BETWEEN 321- AND 132-AVOIDING PERMUTATIONS

ANDERS CLAESSON AND SERGEY KITAEV

Abstract. It is well-known, and was first established by Knuth in 1969, that the number of 321-avoiding permutations is equal to that of 132-avoiding permutations. In the literature one can find many subsequent bijective proofs of this fact. It turns out that some of the published bijections can easily be obtained from others. In this paper we describe all bijections we were able to find in the literature and show how they are related to each other via “trivial” bijections. We classify the bijections according to statistics preserved (from a fixed, but large, set of statistics), obtaining substantial extensions of known results. Thus, we give a comprehensive survey and a systematic analysis of these bijections.

We also give a recursive description of the algorithmic bijection given by Richards in 1988 (combined with a bijection by Knuth from 1969). This bijection is equivalent to the celebrated bijection of Simion and Schmidt (1985), as well as to the bijection given by Krattenthaler in 2001, and it respects 11 statistics — the largest number of statistics any of the bijections respects.

Contents

1. Introduction and main results

2. Permutation statistics 5 3. Bijections in the literature 6 4. A recursive description of the Knuth–Richards bijection 14 5. Proof of Theorem 2 15 6. Proof of Theorem 1 23 7. Appendix 28 8. Acknowledgments 29 References 29

1. Introduction and main results

Given two different bijections between two sets of combinatorial objects, what does it mean to say that one bijection is better than the other? Perhaps, a reasonable

Key words and phrases. bijection, permutation statistics, equidistribution, pattern avoidance, Catalan structures.

The research presented here was supported by grant no. 060005012 from the Icelandic Research Fund.

answer would be “The one that is easier to describe.” While the ease of description and how easy it is to prove properties of the bijection using the description is one aspect to consider, an even more important aspect, in our opinion, is how well the bijection reflects and translates properties of elements of the respective sets.

A natural measure for a bijection between two sets of permutations, then, is how many statistics the bijection preserves. Obviously, we don’t have an exhaustive list of permutation statistics, but we have used the following list as our “base” set:

asc, des, exc, ldr, rdr, lir, rir, zeil, comp, lmax, lmin, rmax, rmin, head, last, peak, valley, lds, lis, rank, cyc, fix, slmax .

These are defined in Section 2. To make sure we find all statistics that a given bijection “essentially” preserves, we include in our list of statistics those that are obtained from our “basic” statistics by applying to them the trivial bijections on permutations (reverse=r, complement=c, inverse=i) and their compositions. Moreover, for each statistic stat, in this extended list we consider two other statistics: n-stat(π) = n − stat(π) and m-stat(π) = n + 1 − stat(π), where n is the length of the permutation. The meaning of n-stat or m-stat is often “non-stat”; for example, n-fix counts nonfixed-points.

This way each basic statistic gives rise to 24 statistics. The base set contains 23 statistics, giving a total of 552 statistics. There are, however, many statistics in that set that are equal as functions; for instance, des = asc.r, and peak = peak.r = valley.c, where we use a dot to denote composition of functions. The classes of equal statistics are listed in the Appendix (Section 7). To prove the correctness of this partitioning is a trivial but very lengthy task. Thus we omit giving that proof. Choosing one representative from each of the classes of equal statistics results in a final set of 148 statistics; we call this set STAT.

In the theorems below, the statistics presented are linearly independent. An example of linear dependence among the statistics over permutations avoiding 132 is lmin − lmax + n-des − head = 0. The results below are also maximal in that they cannot be non-trivially extended using statistics from STAT. That is, adding one more pair of equidistributed statistics from STAT to any of the results would create a linear dependency among the statistics.

A permutation π = a_{1}a_{2} … a_{n} avoids the pattern 321 if there are no indices i < j < k such that a_{k} < a_{j} < a_{i}. It avoids 132 if there are no indices i < j < k such that a_{i} < a_{k} < a_{j}. Avoidance of other patterns is defined similarly.

Knuth [8, 9] showed that the number of permutations avoiding a pattern of length 3 is independent of the pattern. This number is the n-th Catalan number, C_{n} = \frac{1}{n+1} \binom{2n}{n}. To prove this, it suffices, due to the symmetry afforded by the trivial bijections on permutations, to consider one representative from {123, 321} and one from {132, 231, 213, 312}. That symmetry also means that, to prove this bijectively, it suffices to find a bijection from the set of permutations avoiding a pattern in one of the classes to permutations avoiding a pattern in the other. This turns out to be a non-trivial problem. Several authors have, however, succeeded in doing so [5, 6, 10, 12, 13, 15, 16, 17]; we call those bijections

Knuth, Knuth–Rotem, Simion–Schmidt, Knuth–Richards, West, Krattenthaler, Billey–Jockusch–Stanley–Reifegerste, Elizalde–Deutsch, and Mansour–Deng–Du .

They are described in Section 3. In Section 4 we define, using recursion, a “new” bijection called Φ. It turns out that Φ is related, via trivial bijections, to the bijection by Knuth and Richards.

The main results of this paper are contained in the following three theorems. The first theorem substantially extends what was previously known about statistics preserved by the bijections. In bold we mark the results known before this paper — there is a total of 7 pairs of those; the remaining 68 pairs are new.

Theorem 1. The following results are maximal in the sense that adding one more pair of equidistributed statistics from STAT to any of the results would create a linear dependency among the statistics. In bold we mark the results that were known; also, we indicate the sets between which a bijection acts.

(11) Knuth–Richards, 132-avoiding permutations → 123-avoiding permutations

valley.i valley lmin ldr.i head.i comp.r rank ldr lir.i  lir  rmax
valley valley.i lmin ldr head comp.r rank ldr.i slmax.c slmax.i.r head.i.r

(11) Simion–Schmidt, 123-avoiding permutations → 132-avoiding permutations

valley valley.i lmin ldr head comp.r rank ldr.i slmax.c slmax.i.r head.i.r
valley valley.i lmin ldr head comp.r rank ldr.i lir  lir.i  rmin

(11) Krattenthaler, 123-avoiding permutations → 132-avoiding permutations

peak.i peak  rmax zeil last.i.r comp.r rank.r.c rdr slmax.r.i slmax.r last
valley valley.i lmin ldr head comp.r rank  ldr.i lir  lir.i  rmin

(11) Mansour–Deng–Du, 321-avoiding permutations → 231-avoiding permutations

valley peak.i rmin rir last comp rank.r lir.i slmax.c.r slmax.i head.i
valley peak.i rmin rir last comp rank.r lir.i rdr  ldr.i  lmin

(9) Knuth–Rotem, 321-avoiding permutations → 132-avoiding permutations

valley.i peak exc slmax head slmax.r.c.i rir.i lir  last.i
valley.i valley des rdr  ldr.i zeil  lmax rmin m-ldr

(9) Billey–Jockusch–Stanley–Reifegerste, 321-avoiding permutations → 132-avoiding permutations

valley peak.i exc slmax.i head.i slmax.r.c rir lir.i last
valley valley.i des zeil  ldr  rdr  rmin lmax m-ldr.i

(7) West, 123-avoiding permutations → 132-avoiding permutations

valley.i exc.r slmax.i.r slmax.c ldr  ldr.i head
valley.i asc lir.i  comp rmax ldr.i head

(5) Knuth, 321-avoiding permutations → 132-avoiding permutations

exc fix lir.i lir  lis
exc fix rmin lmax n-rank

(1) Elizalde-Deutsch, 321-avoiding permutations → 132-avoiding permutations

{fix \atop fix}

The numbers in parentheses in Theorem 1 indicate the number of statistics respected. It turns out that bijections with the same number are related via “trivial” bijections. The next theorem makes this precise.

Theorem 2. The following relations among bijections between 321- and 132-avoiding permutations hold:

reverse ∘ Φ^{−1} = inverse ∘ Simion–Schmidt ∘ reverse

= inverse ∘ Krattenthaler ∘ reverse ∘ inverse = inverse ∘ reverse ∘ Mansour–Deng–Du

= Knuth–Richards^{−1} ∘ reverse

and

Billey–Jockusch–Stanley–Reifegerste = inverse ∘ Knuth–Rotem ∘ inverse .

Also, there are no other relations among the bijections and their inverses via the trivial bijections that do not follow from the ones above.

Thus if we regard all bijections as bijections from 321- to 132-avoiding permutations — applying the transformations in Theorem 2 — then we get the following condensed version of Theorem 1.

Theorem 3. For bijections from 321- to 132-avoiding permutations we have the following equidistribution results. These results are maximal in the sense that adding one more pair of equidistributed statistics from STAT to any of the results would create a linear dependency among the statistics.

(11) Φ, Knuth–Richards, Krattenthaler, Mansour–Deng–Du, Simion–Schmidt

valley peak.i rmin rir last comp rank.r lir.i slmax.c.r slmax.i head.i
valley valley.i lmin ldr head comp.r rank ldr.i lir  lir.i  rmin

(9) Knuth–Rotem, Billey–Jockusch–Stanley–Reifegerste

valley peak.i exc slmax.i head.i slmax.r.c rir lir.i last
valley valley.i des zeil  ldr  rdr  rmin lmax m-ldr.i

(7) West

peak.i exc slmax.i slmax.r.c rir  lir.i last
valley.i asc lir.i  comp  rmax ldr.i head

(5) Knuth

exc fix lir.i lir  lis
exc fix rmin lmax n-rank

(1) Elizalde-Deutsch

{fix \atop fix}

In Section 2 we define the relevant statistics; in Section 3 we describe the bijections; in Section 4 we give a new recursive description of the bijection by Knuth and Richards; in Section 5 we prove Theorem 2; and in Section 6 we prove Theorem 1.

2. Permutation statistics

The permutation π on {1, 2, …, n} that sends 1 to a_{1}, 2 to a_{2}, etc, we denote π = a_{1}a_{2} … a_{n}, and we call a_{i} the i-th letter of π. A permutation statistic is simply a function from permutations to ℕ. For example, the permutation statistic asc is defined as follows: an ascent in π is a letter that is followed by a larger letter; in other words, an a_{i} such that a_{i} < a_{i+1}. By asc(π) we denote the number of ascents in π. Similarly, a descent is a letter followed by a smaller letter, and by des(π) we denote the number of descents in π.

For words α and β over the alphabet ℕ we define that α ≺ β if for all letters a in α and all letters b in β we have a < b. For instance, 42 ≺ 569. A component of π is a nonempty segment τ of π such that π = στρ with σ ≺ τ ≺ ρ, and such that if τ = αβ and α ≺ β then α or β is empty. By comp(π) we denote the number of components of π. For instance, comp(213645) = 3, the components being 21, 3, and 645.

A left-to-right minimum of π is a letter with no smaller letter to the left of it; the number of left-to-right minima is denoted lmin(π). The statistics right-to-left minima (rmin), left-to-right maxima (lmax), and right-to-left maxima (rmax) are defined similarly.

In the following table we define the remaining statistics that are of interest to us. For reference we include the statistics already defined in the preceding few paragraphs.

asc = number of ascent; comp = number of components;

des = number of descents; exc = number of excedances: positions i such that a_{i} > i; fix = number of fixed points: positions i such that a_{i} = i;

head = first element: head(π) = a_{1}; last = last element: last(π) = a_{n}; ldr = length of the leftmost decreasing run: largest i such that a_{1} > a_{2} > ⋯ >

a_{i}; lds = length of the longest decreasing sequence in a permutation; lir = length of the leftmost increasing run: largest i such that a_{1} < a_{2} < ⋯ < a_{i};

6 ANDERS CLAESSON AND SERGEY KITAEV

lis = length of the longest increasing sequence in a permutation; lmax = number of left-to-right maxima; lmin = number of left-to-right minima; peak = number of peaks: positions i in π such that a_{i−1} < a_{i} > a_{i+1}; rank = largest k such that a_{i} > k for all i ≤ k (see [6]); rdr = lir.r = length of the rightmost decreasing run;

rmax = number of right-to-left maxima; rmin = number of right-to-left minima;

rir = ldr.r = length of the rightmost increasing run; slmax = the number of letters to the left of second left-to-right maximum in π∞:

largest i such that a_{1} ≥ a_{1}, a_{1} ≥ a_{2}, …, a_{1} ≥ a_{i};

valley = number of valleys: positions i in π such that a_{i−1} > a_{i} < a_{i+1};

zeil = rdr.i = length of the longest subword n(n − 1) … i (see [18]). Let us also describe some of the derived statistics: comp.r = number of reverse components: a reverse component is a nonempty seg-

ment τ of π such that π = στρ with σ ≻ τ ≻ ρ, and such that if τ = αβ and α ≻ β then α or β is empty;

head.i = position of the smallest letter;

last.i = position of the largest letter; lir.i = zeil.c = largest i such that 12 … i is a subword in π;

peak.i = number of letters a_{i} that are to the right of both a_{i} − 1 and a_{i} + 1; valley.i = number of letters a_{i} that are to the left of both a_{i} − 1 and a_{i} + 1.

3. Bijections in the literature

In this section we describe the bijections, and we try to stay close to the original sources when doing so. In what follows S_{n}(τ) is the set of τ-avoiding permutations of length n, and D_{n} is the set of Dyck paths of length 2n.

3.1. Knuth’s bijection, 1973. Knuth [8, pp. 242–243] gives a bijection from 312avoiding permutations to “stack words”. Formulated a bit differently, it amounts to a bijection from 132-avoiding permutations to Dyck paths. Knuth [9, pp. 60– 61] also gives a bijection from 321-avoiding permutations to Dyck paths. By letting permutations that are mapped to the same Dyck path correspond to each other, a bijection between 321- and 132-avoiding permutation is obtained — we call it Knuth’s bijection.

We start by describing the bijection from 132-avoiding permutations to Dyck paths. We shall refer to it as the standard bijection. (This bijection is the same as the one given by Krattenthaler [10], who, however, gives a non-recursive description of it; see Section 3.6.) Let π = π_{L}nπ_{R} be a 132-avoiding permutation of length n. Each letter of π_{L} is larger than any letter of π_{R}, or else a 132 pattern would be formed. Let π′_{L} be the permutation of 1, 2, …, |π_{L}| obtained from π_{L} by subtracting |π_{R}| from each of its letters. We define the standard bijection f recursively by f(π) = uf(π′_{L})df(π_{R}) and f(ϵ) = ϵ. Here, and elsewhere, ϵ denotes the empty word/permutation. Thus, under the standard bijection, the position of the largest letter in a 132-avoiding permutation determines the first return to x-axis and vice versa. For instance,

f(7564213) = udf(564213) = uduf(1)df(4213) = uduuddudf(213)
= uduudduduf(21)d = uduudduduudf(1)d
= uduudduduududd
= [figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

As mentioned, Knuth also gives a bijection from 321-avoiding permutations to Dyck paths: Given a 321-avoiding permutation, start by applying the Robinson-Schensted-Knuth correspondence to it. This classic correspondence gives a bijection between permutations π of length n and pairs (P, Q) of standard Young tableaux of the same shape λ ⊢ n. As is well known, the length of the longest decreasing subword in π corresponds to the number of rows in P (or Q). Thus, for 321-avoiding permutations, the tableaux P and Q have at most two rows.

The insertion tableau P is obtained by reading π = a_{1}a_{2} … a_{n} from left to right and, at each step, inserting a_{i} to the partial tableau obtained thus far. Assume that a_{1}, a_{2}, …, a_{i−1} have been inserted. If a_{i} is larger than all the elements in the first row of the current tableau, place a_{i} at the end of the first row. Otherwise, let m be the leftmost element in the first row that is larger than a_{i}. Place a_{i} in the square that is occupied by m, and place m at the end of the second row. The recording tableau Q has the same shape as P and is obtained by placing i, for i from 1 to n, in the position of the square that in the construction of P was created at step i (when a_{i} was inserted). For example, the pair of tableaux corresponding to the 321-avoiding permutation 3156247 we get by the following sequence of insertions:

( ϵ ϵ ) → ( 3 1 ) → ( \begin{matrix}1 & 1 \\ 3 & 2 \end{matrix} )

→ ( \begin{matrix}15 & 13 \\ 3 & 2 \end{matrix} ) → ( \begin{matrix}156 & 134 \\ 3 & 2 \end{matrix} )

→ ( \begin{matrix}126 & 134 \\ 35 & 25 \end{matrix} ) → ( \begin{matrix}124 & 134 \\ 356 & 256 \end{matrix} ) → ( \begin{matrix}1247 & 1347 \\ 356 & 256 \end{matrix} ) .

The pair of tableaux (P, Q) is then turned into a Dyck path D. The first half, A, of the Dyck path we get by recording, for i from 1 to n, an up-step if i is in the first row of P, and a down-step if it is in the second row. Let B be the word obtained from Q in the same way but interchanging the roles of u and d. Then D = AB^{r} where B^{r} is the reverse of B. Continuing with the example above we get

D = [figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

Elizalde and Pak [6] use this bijection together with a slight modification of the standard bijection to give a combinatorial proof of a generalization of the result by Robertson et al. [14] that fixed points have the same distribution on 123- and 132avoiding permutations. The modification they use is to reflect the Dyck path obtained from the standard bijection with respect to the vertical line crossing the path in the middle. Alternatively, the path can be read from the permutation diagram as described in [6]. We follow Elizalde and Pak and apply the same modification. After reflection, the path f(7564213) above is the same as the path D in the preceding example. Thus the image of the 321-avoiding permutation 3156247 under what we call Knuth’s bijection is the 132-avoiding permutation 7564213.

3.2. Knuth–Rotem’s bijection, 1975. Rotem [15] gives a bijection between 321avoiding permutations and Dyck paths, described below. Combining it with the standard bijection gives a bijection from 321- to 132-avoiding permutations — we call it Knuth–Rotem’s bijection.

Let B_{n} be the set of sequences b_{1}b_{2} … b_{n} satisfying the two conditions

(1) b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{n};

(2) 0 ≤ b_{i} ≤ i − 1, for i = 1, 2, …, n.

Let π = p_{1}p_{2} … p_{n} be a 321-avoiding permutation. From it we construct a sequence b_{1}b_{2} … b_{n} in B_{n}: Let b_{1} = 0. For i = 2, …, n, let b_{i} = b_{i−1} if p_{i} is a left-to-right maximum in π, and let b_{i} = p_{i} otherwise.

For the permutation π = 2513476 we get the sequence 0013446. We represent this sequence by a “bar-diagram”, which in turn can be viewed as a lattice path from (0, 0) to (7, 7):

76  _{•} _{•} 54  _{•} _{•} _{•} 3  _{•} _{•} 21  _{•} _{•} 0 _{•} _{•} _{•}  7  ^{•} 6  _{•} _{•} 5  _{•} 4  _{•} _{•} _{•} 3  _{•} _{•} 2  _{•} 1  _{•} _{•} 0 _{•} _{•} _{•}

Rotating that path counter clockwise by 3π/4 radians we get

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

In the previous subsection we saw that this path is f(7564213) where f is the standard bijection. Thus the image of the 321-avoiding permutation 2513476 under Knuth– Rotem’s bijection is the 132-avoiding permutation 7564213.

3.3. Simion–Schmidt’s bijection, 1985. Consider the following algorithm:

Input: A permutation σ = a_{1}a_{2} …, a_{n} in S_{n}(123).
Output: A permutation τ = c_{1}c_{2} … c_{n} in S_{n}(132).
1  c_{1} := a_{1}; x := a_{1}
2  for i = 2, …, n:
3  if a_{i} < x:
4  c_{i} := a_{i}; x := a_{i}

5  else:

6  c_{i} := min{ k | x < k ≤ n, k ≠ c_{j} for all j < i }

The map σ ↦ τ is the Simion–Schmidt bijection [16]. As an example, the 123-avoiding permutation 6743152 maps to the 132-avoiding permutation 6743125.

We remark that Fulmek [7] has given a simple diagrammatic description of what is essentially the Simion–Schmidt bijection. To be more precise, the bijection Fulmek describes is (complement ∘ Simion–Schmidt ∘ complement).

3.4. Knuth–Richards’ bijection, 1988. Richards’ bijection [13] from Dyck paths to 123-avoiding permutations is given by the following algorithm:

Input: A Dyck path P = b_{1}b_{2} … b_{2n}.
Output: A permutation π = a_{1}a_{2} … a_{n} in S_{n}(123).
1  r := n + 1; s := n + 1; j := 1
2  for i = 1, …, n:
3  if b_{j} is an up-step:
4  repeat s := s − 1; j := j + 1 until b_{j} is a down-step
5  a_{s} := i

6  else:

7  repeat r := r − 1 until a_{r} is unset
8  a_{r} := i
9  j := j + 1

The Knuth–Richards bijection, from S_{n}(132) to S_{n}(123), is defined by

Knuth–Richards = Richards ∘ f,

where f is the standard bijection from 132-avoiding permutations to Dyck paths, and Richards is the algorithm just described. As an example, applying Knuth–Richards’ bijection to 6743125 yields 5743612.

3.5. West’s bijection, 1995. West’s bijection [17] is induced by an isomorphism between generating trees. The two isomorphic trees generate 123- and 132-avoiding permutations, respectively. We give a brief description of that bijection: Given a permutation π = p_{1}p_{2} … p_{n−1} and a positive integer i ≤ n, let

π^{i} = p_{1} … p_{i−1} n p_{i} … p_{n−1};

we call this inserting n into site i. With respect to a fixed pattern τ, we call site i of π in S_{n−1}(τ) active if the insertion of n into site i creates a permutation in S_{n}(τ).

For i = 0, …, n − 1, let a_{i+1} be the number of active sites in the permutation obtained from π by removing the i largest letters. The signature of π is the word

a_{0}a_{1} … a_{n−1}.

West [17] showed that for 123-avoiding permutations, as well as for 132-avoiding permutations, the signature determines the permutation uniquely. This induces a natural bijection between the two sets. For example, the 123-avoiding permutation 536142 corresponds to the 132-avoiding permutation 534612 — both have the same signature, 343322.

3.6. Krattenthaler’s bijection, 2001. Krattenthaler’s bijection [10] uses Dyck paths as intermediate objects. Permutations that are mapped to the same Dyck path correspond to each other under this bijection.

The first part of Krattenthaler’s bijection is a bijection from 123-avoiding permutations to Dyck paths. Reading right to left, let the right-to-left maxima in π be m_{1}, m_{2}, …, m_{s}, so that

π = w_{s}m_{s} … w_{2}m_{2}w_{1}m_{1},

where w_{i} is the subword of π in between m_{i+1} and m_{i}. Since π is 123-avoiding, the letters in w_{i} are in decreasing order. Moreover, all letters of w_{i} are smaller than those of w_{i+1}.

To define the bijection, read π from right to left. Any right-to-left maximum m_{i} is translated into m_{i} − m_{i−1} up-steps (with the convention m_{0} = 0). Any subword w_{i} is translated into |w_{i}| + 1 down-steps, where |w_{i}| denotes the number of letters of w_{i}. Finally, the resulting path is reflected in a vertical line through the center of the path. Alternatively, we could have generated the Dyck path from right to left.

The second part of Krattenthaler’s bijection is a bijection from 132-avoiding permutations to Dyck paths. Read π = p_{1}p_{2} … p_{n} in S_{n}(132) from left to right and generate a Dyck path. When p_{j} is read, adjoin, to the path obtained thus far, as many up-steps as necessary to reach height h_{j} + 1, followed by a down-step to height h_{j} (measured from the x-axis); here h_{j} is the number of letters in p_{j+1} … p_{n} which are larger than p_{j}. This procedure can be shown to be equivalent to the standard bijection from 132-avoiding permutations to Dyck paths.

For instance, Krattenthaler’s bijection sends the permutation 536142 in S_{6}(123) to the permutation 452316 in S_{6}(132) — both map to the same Dyck path,

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •]

3.7. Billey–Jockusch–Stanley–Reifegerste’s bijection, 2002. The following figure illustrates the Billey–Jockusch–Stanley–Reifegerste bijection as it was presented by Reifegerste [12].

87654321 1 2 3 4 5 6 7 8

It pictures the 321-avoiding permutation π = 13256847 and the 132-avoiding permutation π′ = 78564213, two permutations that correspond to each other under that bijection.

Let π = a_{1}a_{2} … a_{n} be a 321-avoiding permutation, and let E be the set of pairs

E = { (i, a_{i}) | i is an excedance }.

For each pair (i, a_{i}) in E, we place a square, called an E-square, in position (i, n+1−a_{i}) in an n×n permutation matrix. (E uniquely determines π.) Next we shade each square (a, b) of the matrix where there are no E-squares in the region {(i, j) | i ≥ a, j ≥ b}, thus obtaining a Ferrers diagram. Finally, we get the 132-avoiding permutation π′ corresponding to π by placing dots (circles), row by row starting from the first row, in the leftmost available shaded square such that there are no two dots in any column or row. If (i, j) contains a dot, then π′(i) = j.

Reifegerste [12, Thm. 3.1] showed that the map π ↦ π′ is the composition of a bijection (between 321-avoiding permutations and Dyck paths) given by Billey, Jockusch and Stanley [2] and the standard bijection (from 132-avoiding permutations to Dyck paths). Therefore we call π ↦ π′ the Billey–Jockusch–Stanley–Reifegerste bijection.

3.8. Elizalde-Deutsch’s bijection, 2003. Here is an outline of a bijection by Elizalde and Deutsch [5]: Map 321- and 132-avoiding permutation bijectively to Dyck paths; use an automorphism Ψ on Dyck paths; and match permutations with equal paths.

We start by describing the automorphism Ψ. Let P be a Dyck path of length 2n. Each up-step of P has a corresponding down-step in the sense that the path between the up-step and the down-step forms a proper Dyck path. Match such pairs of steps. Let σ in S_{2n} be the permutation defined by σ_{i} = (i + 1)/2 if i is odd, and σ_{i} = 2n + 1 − i/2 otherwise. For i from 1 to 2n, consider the σ_{i}-th step of P. If the corresponding matching step has not yet been read, define the i-th step of Ψ(P) to be an up-step, otherwise let it be a down-step. For example,

Ψ(uuduudududddud) = uuuddduduuddud.

The bijection ψ from 321-avoiding permutations to D_{n} is defined as follows. Any permutation π in S_{n} can be represented as an n × n array with crosses in the squares (i, π(i)). Given the array of π in S_{n}(321), consider the path with down- and right-steps along the edges of the squares that goes from the upper-left corner to the lower-right corner of the array leaving all the crosses to the right and remaining always as close to the main diagonal as possible. Then the corresponding Dyck path is obtained from this path by reading an up-step every time the path moves down, and a down-step every time the path moves to the right. For example,

ψ(2314657) = uuduudududddud.

The bijection ϕ from 132-avoiding permutations to D_{n} is the standard bijection followed by a reflection of the path with respect to a vertical line through the middle of the path. For example,

ϕ(7432516) = uuduudududddud.

The Elizalde-Deutsch bijection, from S_{n}(321) to S_{n}(132), is defined by

Elizalde–Deutsch = ϕ^{−1} ∘ Ψ^{−1} ∘ ψ.

As an example, it sends 2314657 to 2314657.

3.9. Mansour–Deng–Du’s bijection, 2006. Let i be a positive integer smaller than n. Let s_{i}, for i = 1, …, n − 1, denote the adjacent transposition (i i + 1) in S_{n}. For any permutation π of length n, the canonical reduced decomposition of π is

π = σ_{1}σ_{2} … σ_{k},

where σ_{i} = s_{h_{i}}s_{h_{i}−1} … s_{t_{i}}, h_{i} ≥ t_{i}, 1 ≤ i ≤ k and 1 ≤ h_{1} < h_{2} < ⋯ < h_{k} ≤ n − 1. For example, 415263 = (s_{3}s_{2}s_{1})(s_{4}s_{3})(s_{5}).

Mansour, Deng and Du [11] use canonical reduced decompositions to construct a bijection between S_{n}(321) and S_{n}(231). They show that a permutation is 321-avoiding precisely when t_{i} ≥ t_{i−1} + 1 for 2 ≤ i ≤ k [11, Thm. 2]. They also show that a permutation is 231-avoiding precisely when t_{i} ≥ t_{i−1} or t_{i} ≥ h_{i−j} + 2 for 2 ≤ i ≤ k and 1 ≤ j ≤ i − 1 [11, Thm. 15]. Using these two theorems they build their bijection, which is composed of two bijections: one from S_{n}(321) to D_{n}, and one from S_{n}(231) to D_{n}.

For a Dyck path P, we define the (x + y)-labeling of P as follows: each cell in the region enclosed by P and the x-axis, whose corner points are (i, j), (i + 1, j − 1), (i + 2, j) and (i + 1, j + 1) is labeled by (i + j)/2. If (i − 1, j − 1) and (i, j) are starting points of two consecutive up-steps, then we call the cell with leftmost corner (i, j) an essential cell and the up-step ((i − 1, j − 1), (i, j)) its left arm. We say that two cells are connected if they share at least one point.

We define the zigzag strip of P as follows: If there is no essential cell in P, then the zigzag strip is empty. Otherwise, the zigzag strip is the longest run of connected cells (from left to right) that starts at the rightmost essential cell and is such that each cell in the run shares an edge with P (it lies on the border of P). For example, the zigzag strip of the Dyck path uuduuududddudduduuddud in Figure 1 is the shaded cell labeled by 9, while for the Dyck path uuduuududdd (obtained from that in Figure 1 by ignoring the steps 15 to 22) the zigzag strip is the run of shaded connected cells labeled by 4, 5, 5, 5 and 6.

1 2 3 4 5 6 9 3 4 5 4 5^{1}^{2}^{3}^{4}_{0} _{1} _{2} _{3} _{4} _{5} _{6} _{7} _{8} _{9} _{10} _{11} _{12} _{13} _{14} _{15} _{16} _{17} _{18} _{19} _{20} _{21} _{22}^{Figure 1}

1 2 3 4 5 6 9 2 3 4 2 3^{1}^{2}^{3}^{4}_{0} _{1} _{2} _{3} _{4} _{5} _{6} _{7} _{8} _{9} _{10} _{11} _{12} _{13} _{14} _{15} _{16} _{17} _{18} _{19} _{20} _{21} _{22}^{Figure 2}

Let P_{n,k} be a Dyck path of semi-length n containing k essential cells. We define its zigzag decomposition as follows: The zigzag decomposition of P_{n,0} is the empty set. The zigzag decomposition of P_{n,1} is the zigzag strip. If k ≥ 2, then we decompose P_{n,k} = P_{n,k−1}Q, where Q is the zigzag strip of P_{n,k} and P_{n,k−1} is the Dyck path obtained from P by deleting Q. Reading the labels of Q from left to right, ignoring repetitions, we get a sequence of numbers {i, i + 1, …, j}, and we associate Q with the sequence of adjacent transpositions σ_{k} = s_{j}s_{j−1} … s_{i}. For P_{n,i} with i ≤ k − 1 repeat the above procedure to get σ_{k−1}, …, σ_{2}, σ_{1}. The zigzag decomposition of P_{n,k} is then given by σ = σ_{1}σ_{2} … σ_{k}.

From the zigzag decomposition we get a 321-avoiding permutation π whose canonical reduced decomposition is σ. For the Dyck path P_{11,4} in Figure 1 we have

π = (s_{3}s_{2}s_{1})(s_{4}s_{3})(s_{6}s_{5}s_{4})(s_{9}) = (4, 1, 5, 7, 2, 3, 6, 8, 10, 9, 11),

which is a permutation in S_{11}(321).

We will now describe a map from Dyck paths to 231-avoiding permutations. For a Dyck path P, we define (x − y)-labeling of P as follows (this labeling seems to be considered for the first time in [1]): each cell in the region enclosed by P and the x-axis, whose corner points are (i, j), (i + 1, j − 1), (i + 2, j) and (i + 1, j + 1) is labeled by (i − j + 2)/2.

Let us say that a cell is on the x-axis if it shares a point with the x-axis. We define the trapezoidal strip of P as follows: If there is no essential cell in P, then the trapezoidal strip is empty. Otherwise, the trapezoidal strip is the longest run of connected cells on the x-axis (from left to right) that starts at the rightmost essential cell on the xaxis. For example, the trapezoidal strip of the Dyck path uuduuududddudduduuddud in Figure 2 is the shaded cell labeled by 9, while for the Dyck path uuduuududdd (obtained from that in Figure 2 by ignoring the steps 15 to 22) the zigzag strip is the downmost shaded strip with labels 1, 2, 3, 4, 5 and 6.

Let P_{n,k} be a Dyck path of semi-length n containing k essential cells. We define its trapezoidal decomposition as follows: The trapezoidal decomposition of P_{n,0} is the empty set. The trapezoidal decomposition of P_{n,1} is the trapezoidal strip. If k ≥ 2, then we decompose P_{n,k} into P_{n,k} = Q_{1}uQ_{2}d, where u is the left arm of the rightmost essential cell that touches the x-axis, d is the last down step of P_{n,k}, and Q_{1} and Q_{2} carry the labels in P_{n,k}. Reading the labels of the trapezoidal strip of P_{n,k} from left to right we get a sequence {i, i + 1, …, j}, and we set σ_{k} = s_{j}s_{j−1} … s_{i}. Repeat the above procedure for Q_{1} and Q_{2}. Suppose the trapezoidal decomposition of Q_{1} and Q_{2} are σ′ and σ′′ respectively, then the trapezoidal decomposition for P_{n,k} is σ = σ′σ′′σ_{k}.

From the trapezoidal decomposition we get a 231-avoiding permutation π whose canonical reduced decomposition is σ. For the Dyck path P_{11,4} in Figure 2 we have

π = (s_{3}s_{2})(s_{4}s_{3}s_{2})(s_{6}s_{5}s_{4}s_{3}s_{2}s_{1})(s_{9}) = (7, 1, 5, 4, 2, 3, 6, 8, 10, 9, 11),

which is a permutation in S_{11}(231).

Together, the two maps involving Dyck paths described in this subsection gives a bijection from 321-avoiding to 231-avoiding permutations.

4. A recursive description of the Knuth–Richards bijection

In this section we define a recursive map from 231- to 321-avoiding permutations. That this map is the Knuth–Richards bijection will be proved in Section 5.3.

We call a permutation π indecomposable if comp(π) = 1; otherwise we call π decomposable. Equivalently, if we define the sum ⊕ on permutations by σ ⊕ τ = στ′, where τ′ is obtained from τ by adding |σ| to each of its letters, then a permutation is indecomposable if it cannot be written as the sum of two nonempty permutations.

We shall describe, separately for 231- and 321-avoiding permutations, how to generate the indecomposable permutations, thus inducing a bijection we call Φ.

For a permutation of length n to be 231-avoiding everything to the left of n has to be smaller than anything to the right of n. Clearly, if there is at least one letter to the left of n, then the permutation is decomposable (everything to the right of n, including n, would form the last component). Thus a 231-avoiding permutation of length n is indecomposable if and only if it starts with n.

To build an indecomposable 231-avoiding permutation of length n from a 231avoiding permutation of length n − 1 we simply prepend n. Let us call this map α. For instance, α(2134) = 52134.

Given k indecomposable 231-avoiding permutations π_{1}, π_{2}, …, π_{k}, we build the corresponding permutation by summing: π_{1} ⊕ π_{2} ⊕ ⋯ ⊕ π_{k}. Given k indecomposable 321-avoiding permutations π_{1}, π_{2}, …, π_{k} we build the corresponding permutation by summing in reverse order: π_{k} ⊕ π_{k−1} ⊕ ⋯ ⊕ π_{1}.

Here is how we build an indecomposable 321-avoiding permutation π′ of length n from a 321-avoiding permutation π of length n − 1:

π =  2 4 1 3 5 7 6 9 8 2 4 10 1 3 5 7 6 9 8 π′ = 2 4 7 1 3 5 9 6 10 8

In the first row we box the left-to-right maxima to the right of 1 that are not right-to-left minima. Here, those are 7 and 9. In the second row we insert a new largest letter, 10, immediately to the left of 1 and box it. Finally, in the third row, we cyclically shift the sequence of boxed letter one step to the left, thus obtaining π′. Let us call this map β.

The induced map Φ, between 231- and 321-avoiding permutations is then formally defined by

Φ(ϵ) = ϵ; Φ(α(σ)) = β(Φ(σ)); Φ(σ ⊕ τ) = Φ(τ) ⊕ Φ(σ).

As an example, consider the permutation 5213476 in S_{6}(231). Decompose it using ⊕ and α:

5213476 = 52134 ⊕ 21 = α(2134) ⊕ α(1) = α(α(1) ⊕ 1 ⊕ 1) ⊕ α(1).

Reverse the order of summands and change each α to β:

β(1) ⊕ β(1 ⊕ 1 ⊕ β(1)) = 21 ⊕ β(1243) = 21 ⊕ 41253 = 2163475.

In conclusion, Φ(5213476) = 2163475.

5. Proof of Theorem 2

In the following five subsections we shall prove the equalities of Theorem 2 — one subsection for each equality. The last statement of Theorem 2, that there can be no other relations than the ones presented, is easily realized as follows: The set STAT is by definition closed with respect to the trivial bijections, meaning that if f is a trivial bijection and stat ∈ STAT, then stat.f ∈ STAT. Thus, two bijections related by trivial bijections will preserve the same number of statistics from STAT. Consequently, bijections preserving different number of statistics (from STAT) cannot be related by trivial bijections.

5.1. Simion–Schmidt versus Φ. We prepare for this proof by characterizing the Simion–Schmidt bijection in terms of left-to-right minima. (That characterization can be said to be implicit in [16].) We also characterize the bijection Φ in terms of right-to-left minima.

Definition 4. For a permutation π = a_{1}a_{2} … a_{n} of length n, define

𝔩𝔪𝔦𝔫(π) = { (i, a_{i}) | a_{i} is a left-to-right minima in π }

as the set of positions of left-to-right minima together with their values. Also, define S_{n}/ 𝔩𝔪𝔦𝔫 as the set of equivalence classes with respect to the equivalence induced by 𝔩𝔪𝔦𝔫: that is, π is equivalent to τ if 𝔩𝔪𝔦𝔫(π) = 𝔩𝔪𝔦𝔫(τ). Similarly, define 𝔯𝔪𝔦𝔫, 𝔩𝔪𝔞𝔵 and 𝔯𝔪𝔞𝔵.

The cardinality of 𝔩𝔪𝔦𝔫(S_{n}) = {𝔩𝔪𝔦𝔫(π) | π ∈ S_{n}} is easily seen to be C_{n}, the n-th Catalan number. The following lemma strengthens that observation:

Lemma 5. Each equivalence class in S_{n}/ 𝔩𝔪𝔦𝔫 contains exactly one permutation that avoids 123 and one that avoids 132. In other words, both S_{n}(123) and S_{n}(132) are complete sets of representatives for S_{n}/ 𝔩𝔪𝔦𝔫.

Proof. Given a set L in 𝔩𝔪𝔦𝔫(S_{n}), this is how we construct the corresponding permutation τ = c_{1}c_{2} … c_{n} in S_{n}(132): For i from 1 to n, if (i, a) is in L let c_{i} = a; otherwise, let c_{j} be the smallest letter not used that is greater than all the letters used thus far.

Given a set L in 𝔩𝔪𝔦𝔫(S_{n}), this is how we construct the corresponding permutation π = a_{1}a_{2} … a_{n} in S_{n}(123): For i from 1 to n, if (i, c) is in L let a_{i} = c; otherwise, let a_{j} be the largest letter not used thus far.

It is easy to see that filling in the letters in any other way than the two ways described will either change the sequence of left-to-right minima or result in an occurrence of 132 or 123. □

As an illustration of the preceding proof, with L = {(1, 6), (3, 3), (4, 2), (6, 1)} we get 67324158 in S_{8}(132) and 68327154 in S_{8}(123).

Using Lemma 5 we can thus define a bijection between S_{n}(123) and S_{n}(132) by letting π correspond to σ if 𝔩𝔪𝔦𝔫(π) = 𝔩𝔪𝔦𝔫(σ). However, this map is not new — it is the Simion–Schmidt bijection:

Lemma 6. For π in S_{n}(123) and σ in S_{n}(132), the following two statements are equivalent:

(1) Simion–Schmidt(π) = σ;

(2) 𝔩𝔪𝔦𝔫(π) = 𝔩𝔪𝔦𝔫(σ).

Indeed, looking at the algorithm defining the Simion–Schmidt bijection we see that the variable x keeps track of the smallest letter read thus far; lines 3 and 4 express that left-to-right minima are left unchanged; and line 6 assigns c_{j} to be the smallest letter not used that is greater than all the letters used thus far (as described above).

Here is a characterization of Φ in terms of 𝔯𝔪𝔦𝔫:

Lemma 7. For π in S_{n}(231) and σ in S_{n}(321), the following two statements are equivalent:

(1) Φ(π) = σ;

(2) (n + 1 − i, a) ∈ 𝔯𝔪𝔦𝔫(π) ⟺ (n + 1 − a, i) ∈ 𝔯𝔪𝔦𝔫(σ).

Proof. That the latter statement characterizes a bijection from S_{n}(231) to S_{n}(321) follows from Lemma 5, so all we need to show is that Φ is that bijection.

We use induction on n, the length of the permutation. The case n = 1 is obvious: the right-to-left minimum (1, 1) goes to the right-to-left minimum (1, 1). For the induction step we distinguish two cases: π is decomposable and π is indecomposable (see Section 4 for definitions).

Suppose that π is indecomposable, and hence π = α(σ) for some σ. By definition, Φ(π) = β(Φ(σ)). The claim follows from the following equivalences:

(n + 1 − i, a) ∈ 𝔯𝔪𝔦𝔫(π) ⟺ (n − i, a) ∈ 𝔯𝔪𝔦𝔫(σ)
⟺ (n − a, i) ∈ 𝔯𝔪𝔦𝔫 Φ(σ)
⟺ (n + 1 − a, i) ∈ 𝔯𝔪𝔦𝔫 Φ(π).

Here, the first equivalence is immediate from the definition of α — recall that all α does is to insert a new largest letter in front of σ. The second equivalence holds by induction. The third equivalence follows from the definition of β: the cyclic shift involves no right-to-left minima and the space for the new letter is created to the left of the letter 1; therefore, 1 is added to the indices of right-to-left minima.

Suppose π = τ ⊕ ρ is decomposable, and let k = |τ| and ℓ = |ρ|. By definition, Φ(π) = Φ(ρ) ⊕ Φ(τ). We have

(n + 1 − i, a) ∈ 𝔯𝔪𝔦𝔫(π)

⟺ (n + 1 − i, a) ∈ 𝔯𝔪𝔦𝔫(τ) or (ℓ + 1 − i, a − k) ∈ 𝔯𝔪𝔦𝔫(ρ)  def’ of ⊕
⟺ (k + 1 − (i − ℓ), a) ∈ 𝔯𝔪𝔦𝔫(τ) or (ℓ + 1 − i, a − k) ∈ 𝔯𝔪𝔦𝔫(ρ)  n = k + ℓ
⟺ (k + 1 − a, i − ℓ) ∈ 𝔯𝔪𝔦𝔫 Φ(τ) or (ℓ + 1 − (a − k), i) ∈ 𝔯𝔪𝔦𝔫 Φ(ρ) induction
⟺ (k + 1 − a, i − ℓ) ∈ 𝔯𝔪𝔦𝔫 Φ(τ) or (n + 1 − a, i) ∈ 𝔯𝔪𝔦𝔫 Φ(ρ)  n = k + ℓ
⟺ (n + 1 − a, i) ∈ 𝔯𝔪𝔦𝔫(Φ(ρ) ⊕ Φ(τ))  def’ of ⊕

from which the claim follows. □

We now turn to the proof of the first identity of Theorem 2. It is equivalent to

inverse ∘ Simion–Schmidt ∘ reverse ∘ Φ ∘ reverse = identity .

With all the preparation we have done, this is easy to prove:

(i, a) ∈ 𝔩𝔪𝔦𝔫(π) ⟺ (n + 1 − i, a) ∈ 𝔯𝔪𝔦𝔫 . reverse(π)

⟺ (n + 1 − a, i) ∈ 𝔯𝔪𝔦𝔫 .Φ. reverse(π) ⟺ (a, i) ∈ 𝔩𝔪𝔦𝔫 . reverse .Φ. reverse(π) ⟺ (a, i) ∈ 𝔩𝔪𝔦𝔫 . Simion–Schmidt . reverse .Φ. reverse(π) ⟺ (i, a) ∈ 𝔩𝔪𝔦𝔫 . inverse . Simion–Schmidt . reverse .Φ. reverse(π).

5.2. Simion–Schmidt versus Krattenthaler. In Lemma 6 we characterized the Simion–Schmidt bijection. We shall do the same for Krattenthaler’s bijection. We start by looking at the standard bijection from 132-avoiding permutations to Dyck paths (as defined in Section 3.1).

Let P be a Dyck path of length 2n; index its up- and down-steps 1 through n. For instance,

P = u_{1}u_{2}u_{3}d_{1}d_{2}u_{4}u_{5}d_{3}d_{4}u_{6}d_{5}d_{6}.

A peak in a Dyck path is an up-step directly followed by a down-step. Define

𝔭𝔢𝔞𝔨(P) = { (i, j) | u_{i}d_{j} is a peak in P }.

For instance, with P as before, we have 𝔭𝔢𝔞𝔨(P) = {(3, 1), (5, 3), (6, 5)}.

Lemma 8. Let f be the standard bijection from S_{n}(132) to D_{n}. For π in S_{n}(132) and P in D_{n}, the following two statements are equivalent:

(1) f(π) = P;

(2) (i, n + 1 − a) ∈ 𝔩𝔪𝔦𝔫(π) ⟺ (a, i) ∈ 𝔭𝔢𝔞𝔨(P).

Proof. Clearly, knowing 𝔭𝔢𝔞𝔨(P) is equivalent to knowing the path P. Thus the second statement determines a bijection (by Lemma 5). It remains to show that the first statement implies the second.

We shall use induction on the length of the permutation. Assume that π^{r} is indecomposable (with respect to ⊕). It is easy to see that π ends with its largest letter. Hence, π = τn for some τ in S_{n−1}(132). Let Q = f(τ). Then P = f(π) = uf(τ)d = uQd and

(i, n + 1 − a) ∈ 𝔩𝔪𝔦𝔫(π) ⟺ (i, n + 1 − a) = (i, n − (a − 1)) ∈ 𝔩𝔪𝔦𝔫(τ)
⟺ (a − 1, i) ∈ 𝔭𝔢𝔞𝔨(Q)
⟺ (a, i) ∈ 𝔭𝔢𝔞𝔨(P).

Assume that π^{r} is decomposable, so π^{r} = ρ^{r} ⊕ τ^{r} for some τ in S_{k}(132) and ρ in S_{ℓ}(132) with both k and ℓ positive and k + ℓ = n. Let Q = f(τ) and R = f(ρ). Then P = f(π) = f(τ)f(ρ) = QR and

(i, n + 1 − a) ∈ 𝔩𝔪𝔦𝔫(π)
⟺ (i, k + 1 − a) ∈ 𝔩𝔪𝔦𝔫(τ) or (i − k, n + 1 − a) ∈ 𝔩𝔪𝔦𝔫(ρ)
⟺ (i, k + 1 − a) ∈ 𝔩𝔪𝔦𝔫(τ) or (i − k, ℓ + 1 − (a − k)) ∈ 𝔩𝔪𝔦𝔫(ρ)
⟺ (a, i) ∈ 𝔭𝔢𝔞𝔨(Q) or (a − k, i − k) ∈ 𝔭𝔢𝔞𝔨(R)
⟺ (a, i) ∈ 𝔭𝔢𝔞𝔨(P),

which completes the proof. □

Lemma 9. Let K be Krattenthaler’s bijection from S_{n}(123) to D_{n} as described in Section 3.6. For π in S_{n}(123) and P in D_{n}, the following two statements are equivalent:

(1) K(π) = P;

(2) (i, n + 1 − a) ∈ 𝔯𝔪𝔞𝔵(π) ⟺ (a, i) ∈ 𝔭𝔢𝔞𝔨(P).

Proof. This is an easy consequence of K’s definition. □

Putting Lemma 8 and Lemma 9 together we get the desired characterization of Krattenthaler’s bijection.

Lemma 10. For π in S_{n}(123) and σ in S_{n}(132), the following two statements are equivalent:

(1) Krattenthaler(π) = σ;

(2) (n + 1 − i, a) ∈ 𝔯𝔪𝔞𝔵(π) ⟺ (n + 1 − a, i) ∈ 𝔩𝔪𝔦𝔫(σ).

Having established this characterization, the rest is easy. From the sequence of equivalences

(i, a) ∈ 𝔩𝔪𝔦𝔫(π)

⟺ (n + 1 − i, a) ∈ 𝔯𝔪𝔦𝔫 . reverse(π)

⟺ (a, n + 1 − i) ∈ 𝔩𝔪𝔞𝔵 . inverse . reverse(π)

⟺ (n + 1 − a, n + 1 − i) ∈ 𝔯𝔪𝔞𝔵 . reverse . inverse . reverse(π)

⟺ (i, a) ∈ 𝔩𝔪𝔦𝔫 . Krattenthaler . reverse . inverse . reverse(π)

⟺ (i, a) ∈ 𝔩𝔪𝔦𝔫 . Simion–Schmidt^{−1} . Krattenthaler . reverse . inverse . reverse(π)

it follows that

Simion–Schmidt^{−1} ∘ Krattenthaler ∘ reverse ∘ inverse ∘ reverse = identity

as desired.

5.3. Knuth–Richards versus Φ. Consider the Dyck path P = uudduududuuddd of semi-length n = 7. Let us index its up- and down-steps 1 through n:

P = u_{1}u_{2}d_{1}d_{2}u_{3}u_{4}d_{3}u_{5}d_{4}u_{6}u_{7}d_{5}d_{6}d_{7}.

From this path we shall construct a permutation π = a_{1}a_{2} … a_{n}. Scan P ’s down-steps from left to right: if d_{i} is preceded by an up-step u_{j}, then let a_{n+1−j} = i; otherwise, let j be the largest value for which a_{j} is unset, and let a_{j} = i. In our example, this leads to:

(1) d_{1} is preceded by the up-step u_{2}; let a_{8−2} = a_{6} = 1.

(2) d_{2} is preceded by a down-step; let j = 7 and a_{7} = 2.

(3) d_{3} is preceded by the up-step u_{4}; let a_{8−4} = a_{4} = 3.

(4) d_{4} is preceded by the up-step u_{5}; let a_{8−5} = a_{3} = 4.

(5) d_{5} is preceded by the up-step u_{7}; let a_{8−7} = a_{1} = 5.

(6) d_{6} is preceded by a down-step; let j = 5 and a_{5} = 6.

(7) d_{7} is preceded by a down-step; let j = 2 and a_{2} = 7. The resulting permutation is π = 5743612. What we have just described is the algorithm defining Richard’s bijection. Lines 3, 4 and 5 of that algorithm cover the case when d_{i} is preceded by an up-step; lines 6, 7 and 8 the case when d_{i} is preceded by a down-step.

Plainly, if d_{i} is preceded by an up-step u_{i} then u_{i}d_{j} is a peak in P. Moreover, a_{n+1−j} = i is a left-to-right minimum in the corresponding permutation. To be precise we have the following lemma.

Lemma 11. Let Richards be Richards’ bijection from S_{n}(123) to D_{n} as described in Section 3.4. For π in S_{n}(123) and P in D_{n}, the following two statements are equivalent:

(1) Richards(P) = π;

(2) (n + 1 − i, a) ∈ 𝔩𝔪𝔦𝔫(π) ⟺ (i, a) ∈ 𝔭𝔢𝔞𝔨(P).

Using Lemma 8 we get a characterization of the Knuth–Richards bijection:

Lemma 12. For π in S_{n}(132) and σ in S_{n}(123), the following two statements are equivalent:

(1) Knuth–Richards(π) = σ;

(2) (i, a) ∈ 𝔩𝔪𝔦𝔫(π) ⟺ (a, i) ∈ 𝔩𝔪𝔦𝔫(σ).

The rest is easy. We have

(i, a) ∈ 𝔩𝔪𝔦𝔫(π) ⟺ (a, i) ∈ 𝔩𝔪𝔦𝔫 . Knuth–Richards^{−1}(π)
⟺ (n + 1 − a, i) ∈ 𝔯𝔪𝔦𝔫 . reverse . Knuth–Richards^{−1}(π)
⟺ (n + 1 − i, a) ∈ 𝔯𝔪𝔦𝔫 .Φ. reverse . Knuth–Richards^{−1}(π)
⟺ (i, a) ∈ 𝔩𝔪𝔦𝔫 . reverse .Φ. reverse . Knuth–Richards^{−1}(π)

and hence reverse ∘ Φ ∘ reverse ∘ Knuth–Richards^{−1} = identity .

5.4. Simion–Schmidt versus Mansour–Deng–Du. We will show that

Mansour–Deng–Du = reverse ∘ Simion–Schmidt ∘ reverse .

Due to Lemma 6 it suffices to prove the following lemma.

Lemma 13. For π in S_{n}(132) and π′ in S_{n}(123), the following two statements are equivalent:

(1) Mansour–Deng–Du(π) = π′;

(2) 𝔯𝔪𝔦𝔫(π) = 𝔯𝔪𝔦𝔫(π′).

Proof. Assume that π and π′ are as above. According to the proofs of Corollaries [11, Cor. 4] and [11, Cor. 16], the positions of right-to-left minima in π and π′ are the same and, in particular, rmin(π) = rmin(π′). Thus we only need to prove that right-to-left minima are preserved in value under the Mansour–Deng–Du bijection. Equivalently, we need to prove that non-right-to-left-minima (n-rmin) are preserved in value.

One can see that a letter a is an n-rmin in π if and only if the reduced decomposition of π contains a run of adjacent transpositions (s_{a−1} …). In particular, a = 1 is always an n-rmin. Thus π = σ_{1} … σ_{k} and π′ = σ′_{1} … σ′_{k} for k = n−rmin(π). That is, π and π′ have the same number of runs of adjacent transpositions in the reduced decompositions and it remains to show that the first letter of σ_{j} equals the first letter of σ′_{j} whenever 1 ≤ j ≤ k.

Let P be the intermediate Dyck path and consider its (x+y)- and (x−y)-labellings of P. Note that cells touching the x-axis receive the same labels under both labellings. From this, and the way that the zigzag and trapezoidal decompositions are constructed, it immediately follows that σ_{k} and σ′_{k} begin with the same letter, namely, the label C of the rightmost cell.

We now proceed by induction on the number of essential cells. If there are no essential cells, then the statement is true. Suppose we have k > 0 essential cells. Remove the rightmost zigzag strip to get a Dyck path P′. Note that |P′| = |P | − 2 and that P′ has k − 1 essential cells. Clearly, the permutation corresponding to the (x + y)-labeling of P′ is τ = σ_{1} … σ_{k−1}. Let the permutation corresponding to the (x − y)-labeling of P′ be τ′′ = σ′′_{1} … σ′′_{k−1}. From the properties of the (x − y)-labeling, a cell labeled Q ≠ C is the rightmost cell of a trapezoidal strip in P if and only if Q is the rightmost cell of a trapezoidal strip in P′. This means that σ′_{i} and σ′′_{i} begin with the same letter for 1 ≤ i ≤ k − 1. The desired result now follows from the induction hypothesis applied to P′, τ and τ′′. □

5.5. Billey–Jockusch–Stanley–Reifegerste versus Knuth–Rotem. We will show the following equality:

(1) Billey–Jockusch–Stanley–Reifegerste = inverse ∘ Knuth–Rotem ∘ inverse .

The Billey–Jockusch–Stanley–Reifegerste bijection is defined by values and positions of excedances. Suppose that π = a_{1}a_{2} … a_{n} is a 321-avoiding permutation and that π′ is the image of π under the Billey–Jockusch–Stanley–Reifegerste bijection. The only permutation of length n without excedances is 12 … n. As is easy to see, that permutation is fixed by both sides of identity (1). So we can assume that π has at least one excedance. Let π have an excedance a at position i, denoted (i, a). Also, let (j, b) be the excedance closest to the left of (i, a). If no such excedance exists we define j = 0. Note that b < a, since otherwise an occurrence of 321 would be formed.

Consider the Ferrers diagram corresponding to π in the definition of the Billey– Jockusch–Stanley–Reifegerste bijection (shaded in the figure in Subsection 3.7 on page 10). The point (j + 1, n + 2 − a) is a corner in that diagram. It is sent to the left-to-right minimum (j + 1, n + 2 − a) in π′. Thus, we need to prove that an excedance (i, a) corresponds to a left-to-right minimum (j + 1, n + 2 − a) under the right hand side of identity (1).

Because a > i, b > j and b < a it follows that both i and j are strict non-excedances in π^{−1} with the property that there are no other strict non-excedances between i and j. (A strict non-excedance between i and j would either bring an occurrence of 321 in π or in π^{−1}, or an occurrence of an excedance between a and b in π.) Thus the sequence β, obtained when applying Knuth–Rotem’s bijection to π^{−1} will have the letter j + 1 in positions b = a_{j}, a_{j+1}, …, a_{i−1} and the letter i + 1 in position a = a_{i}. Let P be the Dyck path corresponding to β. It remains to show that f^{−1}, the inverse of the standard bijection, sends P to a permutation having the letter j + 1 in position n + 2 − a. After applying inverse we would then have the letter n + 2 − a in position j + 1, the same outcome as when applying the Billey–Jockusch–Stanley–Reifegerste bijection.

For the remainder of this proof we use induction on n, the length of the permutation π. The smallest permutation that has an excedance is π = 21. In this case, i = 1, j = 0 and a = 2. See Figure 3A. After rotating that diagram counter clockwise by 3π/4 radians we read the Dyck path udud. The inverse of the standard bijection, f^{−1}, sends udud to the permutation π′ = 21. It has the letter j + 1 = 1 in position n + 2 − a = 2 as desired.

Assume that n > 2. Let D be the diagram constructed from the sequence (in B_{n}) corresponding to π. Let P be the Dyck path we read from D. Let (r, s) be the

ij  a i = 1 j = 0  a = 2A  B

Figure 3

coordinate in D corresponding to the first return to the x-axis in P. In particular, r = s. Consider the following four cases.

Case 1: s = 0. This case is sketched in Figure 3B. Note that a > i + 1, and we can remove the first step and the last step of the path, thus shifting the path one step to the left. This corresponds to adjoining n to the right side of the permutation obtained inductively from the reduced Dyck path. Moreover, the number of steps is now 2(n − 1), i and j are unchanged, while a becomes a − 1. From the induction hypothesis it follows that j + 1 will be in position (n − 1) + 2 − (a − 1) = n + 2 − a, as desired.

Case 2: n > s > i. From the definition of the standard bijection we see that the permutation f^{−1}(P) is of the form π′ = σnτ where each letter of σ is larger than any letter of τ; the largest letter, n, is in position n − s + 1; part σ is obtained inductively from the portion of the path above the line y = s; and τ is obtained inductively from the portion of the path below the line y = s. Applying the induction to τ we see that the letter j + 1 is in position (s − 1) + 2 − a = s + 1 − a. Thus, in π′, the letter j + 1 is in position (s + 1 − a) + (n − s + 1) = n + 2 − a.

Case 3: 0 < s < i. From the path we remove the part below the line y = s, we remove the first and the last steps of the remaining path, and we shift the obtained path so that it runs from (n − s − 1, n − s − 1) to (0, 0). The resulting path we call P′. It is responsible for building the standardization σ′ of σ in the outcome permutation π′ = σnτ. (Here σ′ is obtained from σ by adding |τ| to each of its letters.) Note that i, j and a in P become i − s, j − s and a − s − 1 in P′, respectively. From the induction hypothesis applied to P′ it follows that (j − s) + 1 will be in position (n−s−1)+2−(a−s−1) = n+2−a in σ′. But (j −s)+1 in σ′ is (j −s)+1+s = j +1 in σ. Thus, in π′, the letter j + 1 will be in position n + 2 − a.

Case 4: s = i. In this case i + 1 = a and we need to prove that the letter j + 1 is in position n + 2 − a = n + 1 − i. Remove from P the first and last steps of the subpath from (n, n) to (i, i). Shift the path from (n, n − 1) to (i + 1, i) one step to the left. Let P′ denote the obtained path from (n − 1, n − 1) to (0, 0). Now we apply f^{−1} to P and get a 132-avoiding permutation of length (n − 1) of the form σ (n − 1) τ, where |τ| ≥ i. The first return in P′ to the line y = x will be either at (i, i) or above the line y = i. By the induction hypothesis, in σ(n − 1)τ, the letter j + 1 is in position (n − 1) + 2 − a = n − i. This position is located to the right of n − 1. Looking at the definition of the standard bijection we see that f^{−1}(P) is σ(n − 1)τ with the largest letter, n, inserted immediately to the left of the letter j + 1, causing it to appear in position n − i + 1 = n + 2 − a.

6. Proof of Theorem 1

In this section we prove the equidistributions presented in Theorem 1. In light of Theorem 2 it suffices to consider the following five bijections:

Simion–Schmidt, Billey–Jockusch–Stanley–Reifegerste, West, Knuth and Elizalde–Deutsch .

For brevity we shall write stat_{1} ≃ stat_{2} in this section when, for all π in the relevant domain, we have stat_{1}(π) = stat_{2}(ψ(π)), where ψ is the bijection under consideration.

6.1. Simion–Schmidt’s bijection. Let π be a 123-avoiding permutation of length n and let π′ be the image of π under the Simion–Schmidt bijection. By Lemma 6 we have 𝔩𝔪𝔦𝔫(π) = 𝔩𝔪𝔦𝔫(π′). In particular, lmin ≃ lmin. A three letter segment abc is a valley precisely when a and b are left-to-right minima but c is not. Thus valley ≃ valley. Similarly, we have ldr ≃ ldr and head ≃ head. Indeed, ldr is determined by the position of the first non-left-to-right minimum and head is the first left-to-right minimum.

• comp.r ≃ comp.r: Suppose that π = AB where B is the rightmost reverse component. Then B = mC where m is a left-to-right minimum in π. It follows that π′ = A′B′ in which A′ and B′ are the images, under Simion–Schmidt’s bijection, of A and B, respectively. Because the Simion–Schmidt bijection is an involution it also follows that B′ is the rightmost reverse component in π′. By induction on the number of reverse components we thus have comp.r ≃ comp.r.

• slmax.c ≃ lir: The statistic slmax.c is the position of the second left-to-right minimum (it is defined to be n if there is only one left-to-right minimum). Suppose π = a_{1}Aa_{2}B where a_{1} and a_{2} are the two leftmost left-to-right minima (the case π = 1 … n is trivial). Note that each letter in A is larger than a_{1} and a_{2}. We know that π′ = a_{1}A′a_{2}B′ and |A| = |A′|. To avoid the pattern 132 the segment A′ must be increasing. Thus slmax.c ≃ lir.

• slmax.i.r ≃ lir.i: The statistic slmax.i.r is one less than the minimal i such that the letter i is to the left of the letter 1. Note that such an i in π must be a left-to-right minimum. Suppose slmax.i.r(π) = i−1 and i ≤ n (the case slmax.i.r(π) = n is trivial). Then i and 1 are two consecutive left-to-right minima in π. Consequently, i and 1 are two consecutive left-to-right minima in π′. Thus the letters 2, 3, …, i − 1 must be to the right of 1 in π′. To avoid forming an occurrence of 132, those letters must also be in increasing order. Thus lir.i(π′) = i − 1.

• ldr.i ≃ ldr.i: By definition ldr.i(π) is the largest i such that i, i − 1, …, 1 is a subword in π. In particular, i + 1, if it exists, is to the right of i in π. Suppose that ldr.i(π) = i. Clearly, the letters i, i − 1, …, 1 are consecutive left-to-right minima in π and i + 1 is a non-left-to-right minimum. Thus i, i − 1, …, 1 is a subword in π′ and i + 1 is to the right of i in π′; hence ldr.i(π′) = i.

• head.i.r ≃ rmin: Plainly, head.i.r(π) = n − i + 1 where i is the position of 1 in π. Let π′ = σ1τ. The letter 1 is in the same position in π′ as it is in π and so |τ| = n − i. To avoid 132 the letters of τ must be in increasing order. The sequence of right-to-left minima in π′ is thus simply 1τ and therefore head.i.r(π) = rmin(π′).

• valley.i ≃ valley.i: By definition, valley.i(π) is the number of letters i in π such that i is to the left of both i − 1 and i + 1. Suppose i in π is one of those letters counted by valley.i(π). To avoid 123 the letter i must be a left-to-right minimum. Thus i − 1 is a left-to-right minimum too, but i + 1 is not. Since 𝔩𝔪𝔦𝔫(π) = 𝔩𝔪𝔦𝔫(π′) this observation translates to π′. That is, in π′, the letters i and i − 1 are left-to-right minima whereas i + 1 is not. Thus i + 1 is to the right of i in π′ and the letter i in π′ is counted by valley.i(π′). Because the Simion–Schmidt bijection is an involution it is easy to see that no i which is not counted by valley.i(π) contributes to valley.i(π′).

• rank ≃ rank: Suppose that rank(π) = k and π has a in position k + 1. We distinguish two cases based on whether a is a left-to-right minimum or not. If a is a non-left-to-right-minimum, then k + 1 is the left-to-right minimum closest to a in π from the left. Since 𝔩𝔪𝔦𝔫(π) = 𝔩𝔪𝔦𝔫(π′) we have rank(π′) = k. On the other hand, if a is a left-to-right minimum, then a ≤ k + 1 and π′ will have the same left-to-right minimum, a, in position k + 1. Thus rank(π′) = k in this case as well.

6.2. Billey–Jockusch–Stanley–Reifegerste’s bijection. Let π = a_{1}a_{2} … a_{n} be a 321-avoiding permutation of length n and let π′ be the image of π under the Billey– Jockusch–Stanley–Reifegerste bijection. That exc ≃ des was proved in [12].

• valley ≃ valley: A 321-avoiding permutation is a shuffle of two increasing subwords. From this one can see that if a_{i}a_{i+1}a_{i+2} is a valley in π, then a_{i} is an excedance and a_{i+1} is a non-excedance. Thus, in the permutation matrix corresponding to π, there is an E-square in the i-th row but no E-square in the (i + 1)-st row. It follows that the Ferrers diagram has a corner in the (i + 1)-st row. Thus a′_{i}a′_{i+1}a′_{i+2} is a valley in π′ = a′_{1}a′_{2} … a′_{n}. (The dot in row i + 1, corresponding to the letter a′_{i+1}, will be to the left of the dots in rows i and i + 2 corresponding to the letters a′_{i} and a′_{i+2}, respectively).

• peak.i ≃ valley.i: By definition, peak.i(π) is the number of letters a in π to the right of both a − 1 and a + 1; and valley.i(π) is the number of letters a in π to the left of both a − 1 and a + 1. If i is counted by peak.i, then i is a non-excedance while i + 1 is an excedance; otherwise an occurrence of 321 is formed. Thus we have an E-square in column n − i, but no E-square in column n − i + 1. Note also that there is a column n − i + 2 (corresponding to the letter i − 1). Thus column n − i + 1 is not the rightmost column of the matrix and it contains a corner of the Ferrers diagram. So peak.i counts the columns that contain a corner but no E-squares, excluding the rightmost column. In the construction of π′ each corner with the properties described above gives rise to a letter i in π′ to the left of i − 1 and i + 1. Indeed, such a corner has an E-square in the column immediately to its left and no E-square in the column immediately to its right; consequently, the points corresponding to i − 1 and i + 1 in π′ will be below the point corresponding to i in π′. Thus peak.i ≃ valley.i.

• slmax.i ≃ zeil: The letter between the two leftmost left-to-right maxima in a 321-avoiding permutation is an initial segment of 123 . . .. Hence slmax.i is the length of the maximal initial segment of the form 23 … i. Moreover, each of the letters counted by slmax.i is an excedance. Thus we have E-squares in positions (ℓ, n − ℓ) for ℓ = 1, 2, …, i − 1 and no E-square in position (k, n − k). Thus π′ is of the form π′ = n(n − 1)(n − 2) … (n − k + 2)A(n − k)B(n − k + 1)C, where A, B, and C are some words. Clearly, zeil(π′) = k = slmax.i(π).

• head.i ≃ ldr: The statistic head.i(π) is the position of 1 in π. Say this position is i. Then row i of the permutation matrix corresponding to π is the topmost row that does not contain an E-square. Thus, in π′, the first i letters will be in decreasing order, while in position i there will be an ascent (unless i = n). Thus ldr(π′) = i.

• slmax.r.c ≃ rdr: Let the right-to-left minima of π, read from right to left, be r_{1}, r_{2}, …, r_{k}. One can see that slmax.r.c is one more than the number of letters between r_{1} and r_{2}. (To make sure that there is at least two left-to-right minima we can assume that a 0 stays in front of π when considering this statistic.) To avoid the pattern 321 the letters between r_{1} and r_{2} must be the largest letters in π, and thus all of them are excedances. Thus, in the permutation matrix corresponding to π, there will be E-squares in positions (i, n−i) for i = n−1, n−2, …, n−(slmax.r.c(π)−1) and there will be no E-squares in the (n − slmax.r.c(π))-th row. In turn, this guarantees that the 132-avoiding permutation π′ ends with j(slmax.r.c(π) − 1)(slmax.r.c(π) − 2)… 1, where j, if it exists, is strictly larger than slmax.r.c(π). To avoid 132 this segment must be preceded by a letter smaller than j. Thus rdr(π′) = slmax.r.c(π).

• rir ≃ rmin: Let rir(π) = i. We have i = n only if π = π′ = 12 … n, and then, trivially, rir(π) = rmin(π′) = n. Assume i < n. The letters in the rightmost increasing run are non-excedances while the letter immediately to the left of that run is an excedance. Thus the bottommost E-square is in row n − i in the permutation matrix. The dots placed in rows n − i + 1, n − i + 2, …, n when creating π′ gives the sequence of right-to-left minima in π′, and thus rmin(π′) = i.

• lir.i ≃ lmax: Let lir.i(π) = i. We have i = n only if π = π′ = 12 … n, and then, trivially, lir.i(π) = lmax(π′) = n. Assume i < n. By definition, i is the largest positive integer such that 1, 2, …, i is a subword of π. Since π is the shuffle of two increasing sequences, i + 1 is the leftmost excedance in π. The E-square corresponding to i + 1 in the permutation matrix is placed in column n − i, leaving i columns to the right of it. When constructing π′ each of those i columns gets a dot, beginning at the position (1, n − i + 1) and moving in the South-East direction. Those dots give the sequence of left-to-right maxima in π′, and thus lmax(π′) = i.

• last ≃ m-ldr.i: Note that ldr.i(π) is the largest i such that i, (i − 1), …, 1 is a subword in π. The case π = π′ = 12 … n is trivial. Suppose i < n and last(π) = i. To avoid the pattern 321, the letters i + 1, i + 2, …, n must form a subword of π, and clearly each of them is an excedance. Therefore the n − i leftmost columns of the permutation matrix corresponding to π contain E-squares but the (n − i + 1)-st column does not contain an E-square. From this, and the way π′ is constructed, it immediately follows that (n − i + 1), (n − i), …, 1 is the longest subword of π′ of the sought type. Thus m-ldr.i(π′) = i.

6.3. West’s bijection. Recall that West’s bijection is induced by an isomorphism between generating trees. The two isomorphic trees generate 123- and 132-avoiding permutations, respectively. However, for the purpose of this proof we shall generate 321-avoiding permutations instead of 123-avoiding ones. This change is reflected in positions of active sites: In the 123-avoiding case the active sites are all the positions to the left of the leftmost ascent and the position in between the two letters of the leftmost ascent. In the 321-avoiding case the active sites are all the positions to the right of the rightmost descent and the position in between the two letters of the rightmost descent.

The active sites in a 132-avoiding permutation are the leftmost position and every position immediately to the right of right-to-left maxima.

All the proofs below are by induction on the length of the permutation, with easily verifiable base cases. Let π be a 321-avoiding permutation of length n. Let π′ be the image of π under the modified version of West’s bijection as described above.

• peak.i ≃ valley.i: By definition, peak.i(π) is the number of letters a in π to the right of both a − 1 and a + 1; and valley.i(π′) is the number of letters a in π′ to the left of both a − 1 and a + 1.

Case 1. Assume that π ends with n. Then π′ begins with n. Insertion of n + 1 to the right of n in π does not change peak.i. Insertion of n + 1 to the left of n in π′ does not change valley.i. Insertion of n + 1 in any other position in π and π′ increases peak.i and valley.i by 1.

Case 2. Assume that π does not end with n. To avoid the pattern 321, the letter n must be the last letter of the rightmost descent. Thus n is not the leftmost letter in π′, and to avoid the pattern 132, the letter n − 1 must be to the left of n. It follows that insertion of n+1 in an active site of π and π′, respectively, does not change peak.i and valley.i, respectively.

• exc ≃ asc: Insertion of n + 1 at the end of π does not change the number of excedances. Similarly, insertion of n + 1 at the beginning of π′, the number of ascents is not changed. In all other cases, the number of excedances in π and the number of ascents in π′ is increased by 1.

• slmax.i ≃ lir.i: We see that slmax.i(π) is one more than the length of the maximum initial segment of the form 234 … in π. Also, lir.i(π′) is the largest i such that 12 … i is a subword of π′.

Case 1. Assume that π = 234 … n1. Using induction it is easy to verify that π′ = 12 … n. Insertion of n + 1 at the end of π does not change slmax.i, and insertion of n + 1 at the beginning of π′ does not change lir.i. On the other hand, insertion of n + 1 between n and 1 in π increases slmax.i by 1, and insertion of n + 1 at the end of π′ increases lir.i by 1.

Case 2. Assume that π ≠ 234 … n1, and thus π′ ≠ 12 … n. Insertion of n + 1 will not change slmax.i in π and it will not change lir.i in π′.

• slmax.r.c ≃ comp: By definition slmax.r.c(π) = 1 if the letter n is not in position n − 1, and slmax.r.c(π) is one more than the length of the maximal segment of the form i(i + 1) … n if n is in position n − 1.

Insertion of n + 1 at the end of π′ (creating two active sites) increases the number of components by 1. The corresponding action on π (creating two active sites) is insertion of n + 1 in position n; this increases slmax.r.c by 1. Insertion of n + 1 in any other active site of π′ will create an indecomposable permutation (n + 1 will be to the left of 1). The corresponding operation on π places n + 1 in a position different from n, and thus slmax.r.c will be 1.

• rir ≃ rmax: A proof is straightforward from the location of active sites in π and π′: the (number of) active sites in π and π′ essentially give the rir- and rmax-statistics, respectively.

• lir.i ≃ ldr.i: By definition lir.i(π) is the largest i such that 12 … i is a subword of π, and ldr.i(π′) is the largest i such that i(i − 1) … 1 is a subword of π′.

It is easy to see, by induction, that π = 12 … n corresponds to π′ = n(n − 1) … 1. Insertion of n + 1 at the end of π and at the beginning of π′ will increase lir.i and ldr.i by 1, respectively. For any other insertions and any other π and π′, the statistics lir.i and ldr.i will not change.

• last ≃ head: Insertion of n + 1 in π changes the last letter only if the insertion is at the end. Similarly, insertion of n + 1 in π′ changes the leftmost letter only if the insertion is at the beginning.

6.4. Knuth’s bijection. Elizalde and Pak [6] proved that exc ≃ exc, fix ≃ fix and lis ≃ n-rank. Let π be a 321-avoiding permutation of length n and let π′ be the image of π under Knuth’s bijection.

• lir ≃ lmax: If lir(π) = i then the first row of the recording tableau begins with 1, 2, …, i, and i + 1 (if it exists) is the leftmost element in the second row. Thus the statistic lir translates to the statistic “length of the rightmost slope” (segment of down-steps) in the corresponding Dyck path. After reflection, that statistic becomes “length of the leftmost slope” (segment of up-steps). The up-steps in the leftmost slope have corresponding down-steps such that between these steps one has a proper Dyck path. In particular, the down-step corresponding to the leftmost up-step gives the first return to the x-axis, giving the position of n, the rightmost left-to-right maxima, in π′. Proceeding recursively it is easy to see that in general the up-steps in the leftmost slope read from left to right correspond to the left-to-right maxima in π′ read from right to left. This gives the desired result.

• lir.i ≃ rmin: The statistic lir.i is the length of the longest subword of the form 12 … i. So, if lir.i(π) = i, the first row of the insertion tableau begins with 1, 2, …, i, and i + 1 (if it exists) is the leftmost element in the second row. Thus the statistic lir.i translates to the statistic “length of the leftmost slope” in the corresponding Dyck path. After reflection, that statistic becomes “length of the rightmost slope”. Returns to the x-axis in the Dyck path correspond to reverse components in π′. Consider the part D′ of the Dyck path between the last return and next-to-last return to the x-axis. The first up-step of D′ corresponds to the rightmost down-step in the rightmost slope, and it corresponds to the rightmost letter, say a, in π′. The letter a is the largest letter in the rightmost reverse component of π′, and thus it is a right-to-left minimum. Proceeding recursively we see that the next to last down-step in the rightmost slope corresponds to the second right-to-left minimum from the right, and so on.

6.5. Elizalde-Deutsch’s bijection. Elizalde and Deutsch [5] proved that fix ≃ fix.

7. Appendix

The set of 552 statistics partitioned with respect to equality as function. There are 148 classes. By choosing the first element of each class we get the set STAT.

{ asc,des.c,des.r,asc.r.c }{ comp,comp.i,comp.r.c,comp.i.c.r }{ cyc,cyc.i,cyc.r.c,cyc.i.c.r }
{ des,asc.c,asc.r,des.r.c }{ exc,exc.i.c.r }{ fix,fix.i,fix.r.c,fix.i.c.r }
{ head,last.r,m-head.c,m-last.r.c }
{ lmax,lmin.c,rmax.r,rmin.i,lmin.i.c,rmax.i.r,rmin.r.c,lmax.i.c.r }
{ lmin,lmax.c,lmin.i,rmin.r,lmax.i.r,rmax.r.c,rmin.i.c,rmax.i.c.r }
{ last,head.r,m-last.c,m-head.r.c }{ ldr,lir.c,rir.r,rdr.r.c,zeil.i.c.r }
{ lds,lds.i,lis.c,lis.r,lds.r.c,lis.i.c,lis.i.r,lds.i.c.r }
{ lir,ldr.c,rdr.r,rir.r.c,zeil.i.r }
{ lis,lds.c,lds.r,lis.i,lds.i.c,lds.i.r,lis.r.c,lis.i.c.r }
{ peak,peak.r,valley.c,valley.r.c }{ slmax }
{ rmax,lmax.r,rmax.i,rmin.c,lmax.i.c,lmin.r.c,rmin.i.r,lmin.i.c.r }
{ rmin,lmax.i,lmin.r,rmax.c,lmax.r.c,lmin.i.r,rmax.i.c,rmin.i.c.r }{ rank,rank.i }
{ rdr,lir.r,rir.c,zeil.i,ldr.r.c }{ rir,ldr.r,rdr.c,lir.r.c,zeil.i.c }
{ valley,peak.c,valley.r,peak.r.c }{ zeil,rdr.i,lir.i.c,rir.i.r,ldr.i.c.r }
{ asc.i,des.i.c,des.i.r,asc.i.c.r }{ comp.c,comp.r,comp.i.c,comp.i.r }
{ cyc.c,cyc.r,cyc.i.c,cyc.i.r }{ des.i,asc.i.c,asc.i.r,des.i.c.r }
{ exc.c,exc.i.r }{ exc.i,exc.r.c }{ exc.r,exc.i.c }{ fix.c,fix.r,fix.i.c,fix.i.r }
{ head.c,last.r.c,m-head,m-last.r }{ head.i,last.i.c,m-head.i.r,m-last.i.c.r }
{ last.c,head.r.c,m-last,m-head.r }{ last.i,head.i.c,m-last.i.r,m-head.i.c.r }
{ ldr.i,lir.i.r,rir.i.c,zeil.r.c,rdr.i.c.r }{ lir.i,zeil.c,ldr.i.r,rdr.i.c,rir.i.c.r }
{ peak.i,peak.i.c,valley.i.r,valley.i.c.r }{ slmax.c }{ slmax.i }{ slmax.r }
{ rank.c,rank.i.c }{ rank.r,rank.i.r }{ rir.i,zeil.r,ldr.i.c,rdr.i.r,lir.i.c.r }
{ valley.i,peak.i.r,valley.i.c,peak.i.c.r }{ head.i.r,last.i.c.r,m-head.i,m-last.i.c }
{ last.i.r,head.i.c.r,m-last.i,m-head.i.c }{ slmax.i.c }{ slmax.i.r }{ slmax.r.c }
{ rank.r.c,rank.i.c.r }{ slmax.i.c.r }{ n-asc,n-des.c,n-des.r,n-asc.r.c }
{ n-comp,n-comp.i,n-comp.r.c,n-comp.i.c.r }{ n-cyc,n-cyc.i,n-cyc.r.c,n-cyc.i.c.r }
{ n-des,n-asc.c,n-asc.r,n-des.r.c }{ n-exc,n-exc.i.c.r }
{ n-fix,n-fix.i,n-fix.r.c,n-fix.i.c.r }{ n-head,n-last.r }
{ n-lmax,n-lmin.c,n-rmax.r,n-rmin.i,n-lmin.i.c,n-rmax.i.r,n-rmin.r.c,n-lmax.i.c.r }
{ n-lmin,n-lmax.c,n-lmin.i,n-rmin.r,n-lmax.i.r,n-rmax.r.c,n-rmin.i.c,n-rmax.i.c.r }
{ n-last,n-head.r }{ n-ldr,n-lir.c,n-rir.r,n-rdr.r.c,n-zeil.i.c.r }
{ n-lds,n-lds.i,n-lis.c,n-lis.r,n-lds.r.c,n-lis.i.c,n-lis.i.r,n-lds.i.c.r }
{ n-lir,n-ldr.c,n-rdr.r,n-rir.r.c,n-zeil.i.r }
{ n-lis,n-lds.c,n-lds.r,n-lis.i,n-lds.i.c,n-lds.i.r,n-lis.r.c,n-lis.i.c.r }
{ n-peak,n-peak.r,n-valley.c,n-valley.r.c }{ n-slmax }
{ n-rmax,n-lmax.r,n-rmax.i,n-rmin.c,n-lmax.i.c,n-lmin.r.c,n-rmin.i.r,n-lmin.i.c.r }
{ n-rmin,n-lmax.i,n-lmin.r,n-rmax.c,n-lmax.r.c,n-lmin.i.r,n-rmax.i.c,n-rmin.i.c.r }
{ n-rank,n-rank.i }{ n-rdr,n-lir.r,n-rir.c,n-zeil.i,n-ldr.r.c }
{ n-rir,n-ldr.r,n-rdr.c,n-lir.r.c,n-zeil.i.c }{ n-valley,n-peak.c,n-valley.r,n-peak.r.c }
{ n-zeil,n-rdr.i,n-lir.i.c,n-rir.i.r,n-ldr.i.c.r }
{ n-asc.i,n-des.i.c,n-des.i.r,n-asc.i.c.r }{ n-comp.c,n-comp.r,n-comp.i.c,n-comp.i.r }
{ n-cyc.c,n-cyc.r,n-cyc.i.c,n-cyc.i.r }{ n-des.i,n-asc.i.c,n-asc.i.r,n-des.i.c.r }

{ n-exc.c,n-exc.i.r }{ n-exc.i,n-exc.r.c }{ n-exc.r,n-exc.i.c }
{ n-fix.c,n-fix.r,n-fix.i.c,n-fix.i.r }{ n-head.c,n-last.r.c }{ n-head.i,n-last.i.c }
{ n-last.c,n-head.r.c }{ n-last.i,n-head.i.c }
{ n-ldr.i,n-lir.i.r,n-rir.i.c,n-zeil.r.c,n-rdr.i.c.r }
{ n-lir.i,n-zeil.c,n-ldr.i.r,n-rdr.i.c,n-rir.i.c.r }
{ n-peak.i,n-peak.i.c,n-valley.i.r,n-valley.i.c.r }{ n-slmax.c }{ n-slmax.i }{ n-slmax.r }
{ n-rank.c,n-rank.i.c }{ n-rank.r,n-rank.i.r }
{ n-rir.i,n-zeil.r,n-ldr.i.c,n-rdr.i.r,n-lir.i.c.r }
{ n-valley.i,n-peak.i.r,n-valley.i.c,n-peak.i.c.r }{ n-head.i.r,n-last.i.c.r }
{ n-last.i.r,n-head.i.c.r }{ n-slmax.i.c }{ n-slmax.i.r }{ n-slmax.r.c }
{ n-rank.r.c,n-rank.i.c.r }{ n-slmax.i.c.r }{ m-asc,m-des.c,m-des.r,m-asc.r.c }
{ m-comp,m-comp.i,m-comp.r.c,m-comp.i.c.r }{ m-cyc,m-cyc.i,m-cyc.r.c,m-cyc.i.c.r }
{ m-des,m-asc.c,m-asc.r,m-des.r.c }{ m-exc,m-exc.i.c.r }
{ m-fix,m-fix.i,m-fix.r.c,m-fix.i.c.r }
{ m-lmax,m-lmin.c,m-rmax.r,m-rmin.i,m-lmin.i.c,m-rmax.i.r,m-rmin.r.c,m-lmax.i.c.r }
{ m-lmin,m-lmax.c,m-lmin.i,m-rmin.r,m-lmax.i.r,m-rmax.r.c,m-rmin.i.c,m-rmax.i.c.r }
{ m-ldr,m-lir.c,m-rir.r,m-rdr.r.c,m-zeil.i.c.r }
{ m-lds,m-lds.i,m-lis.c,m-lis.r,m-lds.r.c,m-lis.i.c,m-lis.i.r,m-lds.i.c.r }
{ m-lir,m-ldr.c,m-rdr.r,m-rir.r.c,m-zeil.i.r }
{ m-lis,m-lds.c,m-lds.r,m-lis.i,m-lds.i.c,m-lds.i.r,m-lis.r.c,m-lis.i.c.r }
{ m-peak,m-peak.r,m-valley.c,m-valley.r.c }{ m-slmax }
{ m-rmax,m-lmax.r,m-rmax.i,m-rmin.c,m-lmax.i.c,m-lmin.r.c,m-rmin.i.r,m-lmin.i.c.r }
{ m-rmin,m-lmax.i,m-lmin.r,m-rmax.c,m-lmax.r.c,m-lmin.i.r,m-rmax.i.c,m-rmin.i.c.r }
{ m-rank,m-rank.i }{ m-rdr,m-lir.r,m-rir.c,m-zeil.i,m-ldr.r.c }
{ m-rir,m-ldr.r,m-rdr.c,m-lir.r.c,m-zeil.i.c }{ m-valley,m-peak.c,m-valley.r,m-peak.r.c }
{ m-zeil,m-rdr.i,m-lir.i.c,m-rir.i.r,m-ldr.i.c.r }
{ m-asc.i,m-des.i.c,m-des.i.r,m-asc.i.c.r }{ m-comp.c,m-comp.r,m-comp.i.c,m-comp.i.r }
{ m-cyc.c,m-cyc.r,m-cyc.i.c,m-cyc.i.r }{ m-des.i,m-asc.i.c,m-asc.i.r,m-des.i.c.r }
{ m-exc.c,m-exc.i.r }{ m-exc.i,m-exc.r.c }{ m-exc.r,m-exc.i.c }
{ m-fix.c,m-fix.r,m-fix.i.c,m-fix.i.r }
{ m-ldr.i,m-lir.i.r,m-rir.i.c,m-zeil.r.c,m-rdr.i.c.r }
{ m-lir.i,m-zeil.c,m-ldr.i.r,m-rdr.i.c,m-rir.i.c.r }
{ m-peak.i,m-peak.i.c,m-valley.i.r,m-valley.i.c.r }
{ m-slmax.c }{ m-slmax.i }{ m-slmax.r }{ m-rank.c,m-rank.i.c }{ m-rank.r,m-rank.i.r }
{ m-rir.i,m-zeil.r,m-ldr.i.c,m-rdr.i.r,m-lir.i.c.r }
{ m-valley.i,m-peak.i.r,m-valley.i.c,m-peak.i.c.r }
{ m-slmax.i.c }{ m-slmax.i.r }{ m-slmax.r.c }{ m-rank.r.c,m-rank.i.c.r }{ m-slmax.i.c.r }

8. Acknowledgments

We wish to express our gratitude towards Christian Krattenthaler for many useful suggestions regarding this paper.

References

[1] J. Bandlow and K. Killpatrick, An area-to-inv bijection between Dyck paths and 312-avoiding permutations, Elect. J. Combin. 8 (2001) #R40.

[2] S.C. Billey, W. Jockusch and R.P Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (1993), 345–374.

[3] A. Claesson, S. Kitaev and E. Steingrímsson, Stack sorting, trees, and pattern avoidance, preprint.

[4] I. P. Goulden and J. West, Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations, J. Combin. Theory Ser. A 75 (1996), 200–242.

[5] S. Elizalde and E. Deutsch, A simple and unusual bijection for Dyck paths and its consequences, Ann. Combin. 7 (2003), 281–297.

[6] S. Elizalde and I. Pak, Bijections for refined restricted permutations, J. Combin. Theory Ser. A 105 (2004), 207–219.

[7] M. Fulmek, Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three, Adv. in Appl. Math. 30 (2003), 607–632.

[8] D. E. Knuth, The art of computer programming, I: Fundamental algorithms. Addison-Wesley Publishing Co., Reading, Mass.–London–Don Mills, Ont., 1969.

[9] D. E. Knuth, The art of computer programming, III: Sorting and searching, Addison-Wesley, Reading, MA, 1973.

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

[11] T. Mansour, E. Deng and R. Du, Dyck paths and restricted permutations, Discrete Appl. Math. 154 (2006), 1593–1605.

[12] A. Reifegerste, A generalization of Simion–Schmidt’s bijection for restricted permutations, Electron. J. Combin. 9 (2) (2002), paper #R14, 9 pp. (electronic).

[13] D. Richards, Ballot sequences and restricted permutations, Ars Combin. 25 (1988), 83–86.

[14] A. Robertson, D. Saracino and D. Zeilberger, Refined restricted permutations, Ann. Combin. 6 (2003), 427–444.

[15] D. Rotem, On a correspondence between binary trees and a certain type of permutations, Information processing letters 4 (1975), 58–61.

[16] R. Simion and F. W. Schmidt, Restricted permutations, Europ. J. Combin. 6 (1985), 383–406.

[17] J. West, Permutation trees and the Catalan and Schröder numbers Discrete Math., 146 (1995), 247–262.

[18] D. Zeilberger: A proof of Julian West’s conjecture that the number of two-stack-sortable permutations of length n is 2(3n)!/((n + 1)!(2n + 1)!), Discrete Math. 102 (1992), 85–93.

The Mathematics Institute, Reykjavik University, Kringlan 1, 103 Reykjavik, Iceland