Séminaire Lotharingien de Combinatoire 60 (2009), Article B60a

ON BIJECTIONS BETWEEN 231-AVOIDING PERMUTATIONS AND DYCK PATHS

CHRISTIAN STUMP

Abstract. We construct a bijection between 231-avoiding permutations and Dyck paths that sends the sum of the major index and the inverse major index of a 231avoiding permutation to the major index of the corresponding Dyck path. Furthermore, we relate this bijection to others and exhibit a bistatistic on 231-avoiding permutations which is related to the q, t-Catalan numbers.

1. Introduction

The q, t-Catalan numbers Cat_{n}(q, t) were defined by A. Garsia and M. Haiman in [7] as symmetric rational function in q and t. They reduce for q = t = 1 to the well-known Catalan numbers Cat_{n} := \frac{1}{n+1} \binom{2n}{n}; more generally, they reduce for t = q^{−1}, up to a power of q, to the q-Catalan numbers considered by P.A. MacMahon in [12],

q^{\binom{n}{2}} Cat_{n}(q, q^{−1}) = \frac{1}{[n + 1]_{q}} [\begin{matrix}2n \\ n \end{matrix}]_{q} .

Here, [k]_{q} := \frac{1−q^{k}}{1−q} is the usual q-extension of the integer k, [k]_{q}! := [1]_{q}[2]_{q} … [k]_{q} is the q-factorial of k and [ \begin{matrix}k \\ ℓ \end{matrix}]_{q} := \frac{[k]_{q}!}{[ℓ]_{q}![k−ℓ]_{q}!} is the q-binomial coefficient. In [6], A. Garsia and J. Haglund proved that Cat_{n}(q, t) is in fact a polynomial with non-negative integer coefficients by providing a combinatorial description of Cat_{n}(q, t) in terms of the two statistics area and bounce on Dyck paths of semilength n. So far, no bijective proof is known for the fact that Cat_{n}(q, t) is symmetric in q and t.

In this article, we construct a bijection between 231-avoiding permutations and Dyck paths which sends the sum of the major index and the inverse major index on 231avoiding permutations to the major index of the corresponding Dyck path. Using this bijection, we exhibit a polynomial A_{n}(q, t) which is related to Cat_{n}(q, t) by

A_{n}(q, q^{−1}) = Cat_{n}(q, q^{−1}),

and show bijectively that A_{n}(q, t) is symmetric in q and t.

Finally, we connect the proposed bijection to a bijection between 132-avoiding permutations and Dyck paths introduced in [11] by C. Krattenthaler and to a bijection from 231-avoiding permutations and Dyck paths introduced in [1] by J. Bandlow and K. Killpatrick. Using these connections, we obtain several generating function identities as corollaries of the main theorem.

2000 Mathematics Subject Classification. Primary 05A05; Secondary 05A15.

Key words and phrases. pattern-avoiding permutations, Dyck paths, permutation statistics, q, t-Catalan numbers.

Research supported by the Austrian Science Foundation FWF, grant P17563-N13 “Macdonald polynomials and q-hypergeometric Series”.

The article is organized as follows: In Section 2, we define pattern-avoiding permutations and Dyck paths and state some of their basic properties. In Section 3, we construct the announced bijection between 231-avoiding permutations and Dyck paths. In Section 4 we describe the bistatistic (maj, \binom{n}{2} − imaj) on 231-avoiding permutations, and we prove the symmetry of the corresponding generating function. In Section 5 we show how the bijection can be described in terms of earlier bijections, and in Section 6 we describe how the bistatistic (maj, \binom{n}{2} − imaj) could be connected to the q, t-Catalan numbers Cat_{n}(q, t).

2. Basic definitions

We denote by S_{n} the symmetric group of all permutations of the set [n] := {1, …, n}. Usually, we write a permutation σ ∈ S_{n} in one-line notation as the word σ = [σ_{1}, …, σ_{n}] of length n where σ_{i} := σ(i) (often, we suppress the commas or even the brackets around). A subword of σ is a subsequence [σ_{i_{1}}, …, σ_{i_{k}}] of σ with i_{1} < ⋯ < i_{k}.

Definition 2.1. Let σ ∈ S_{n} and τ ∈ S_{k}. σ avoids the pattern τ and is called τ-avoiding if σ does not contain a subword of length k having the same relative order as τ. In particular, σ is called

• 231-avoiding if σ does not contain a subword [σ_{i}, σ_{j}, σ_{k}] with σ_{k} < σ_{i} < σ_{j},

• 312-avoiding if σ does not contain a subword [σ_{i}, σ_{j}, σ_{k}] with σ_{j} < σ_{k} < σ_{i}.

For τ ∈ S_{k}, we denote the set of all σ ∈ S_{n} which are τ-avoiding by S_{n}(τ).

Remark 2.2. In [10], D.E. Knuth proved that for any τ ∈ S_{3} the number of τ-avoiding permutations is equal to the n-th Catalan number Cat_{n}.

An integer 1 ≤ i < n is called a descent of σ if σ_{i} > σ_{i+1}, otherwise i is called an ascent. As we count n as an ascent, this differs from the usual definition. By Des(σ) (respectively Asc(σ)) we denote the set of all descents (respectively ascents) of σ, and we set des(σ) := | Des(σ)| and asc(σ) := | Asc(σ)|. As we will often use the descent set and sometimes the ascent set of the inverse of a permutation, we will denote these sets by iDes(σ) and by iAsc(σ) respectively.

We furthermore need the following two elementary involutions on S_{n}: define ρ to be the involution sending [σ_{1}, …, σ_{n}] to [σ_{n}, …, σ_{1}] and σ ↦ σ̂ to be the involution sending a permutation to its inverse. We can easily describe the descent set and the inverse descent set of the images of those involutions: sending a permutation to its inverse interchanges Des and iDes, and for ρ we have

Des(ρ(σ)) = [n − 1] \ {n − i : i ∈ Des(σ)},
iDes(ρ(σ)) = [n − 1] \ iDes(σ).

Furthermore, define the major index of a permutation σ by

maj(σ) := ∑_{i∈Des(σ)} i,

[figure]

Figure 1. The Dyck path 01 001 011 01 01 ∈ D_{6}.

and define its inverse major index to be the major index of its inverse, imaj(σ) := maj(σ̂). The inverse major index is discussed in detail by D. Foata and G.-N. Han in [3, Chapters 11, 12].

Next, we define Dyck paths and state the properties of Dyck paths we need:

Definition 2.3. A Dyck path of semilength n is a sequence of 2n letters containing n 0’s and n 1’s such that every prefix contains at least as many 0’s as 1’s. We denote the set of all Dyck paths of semilength n by D_{n}.

A natural way of thinking of a Dyck path is to identify it with the lattice path consisting of north and east steps starting at (0, 0) and ending at (n, n), where a north step is encoded by a 0 and an east step by a 1. The property that any prefix contains at least as many 0’s as 1’s is equivalent to the property that a Dyck path always stays weakly above the diagonal x = y, see Figure 1 for an example of a Dyck path of semilength 6.

It is well-known that – as for τ-avoiding permutations with τ ∈ S_{3} – the number of Dyck paths of semilength n is given by Cat_{n}, see e.g. [14].

For D ∈ D_{n}, an integer i with 1 ≤ i < 2n is called descent of D, if D_{i} = 1 and D_{i+1} = 0, and let Des(D) denote the set of all descents of D. In analogy to the definition on permutations, the major index of D is defined by

maj(D) := ∑_{i∈Des(D)} i.

A descent can also be described as a valley in the lattice path, i.e., an east step followed by a north step. The coordinates of a descent or valley of a Dyck path D are the coordinates of the lattice point right after the corresponding east step. Furthermore, we define the sets Set_{X}(D) and Set_{Y} (D) to be the set of x-coordinates and the set of y-coordinates of the descents or valleys of D. In [2, Section 3], D. Callan called Set_{X}(D) and Set_{Y} (D) the “ascent-descent code” of D.

The following observation is fundamental.

Proposition 2.4. A Dyck path D is uniquely determined by Set_{X}(D) and Set_{Y} (D) and furthermore

maj(D) = ∑_{i∈Set_{X}(D)} i + ∑_{j∈Set_{Y} (D)} j.

Example 2.5. Let D = 01 001 011 01 01 ∈ D_{6} be the Dyck path shown in Figure 1. As indicated by the blanks, the descent set of D is given by Des(D) = {2, 5, 8, 10} and its major index by 2 + 5 + 8 + 10 = 25. The valleys of D – indicated in the picture by dots – have coordinates (1, 1), (2, 3), (4, 4) and (5, 5) which gives

Set_{X}(D) = {1, 2, 4, 5}, Set_{Y} (D) = {1, 3, 4, 5}.

There exist plenty of bijections between pattern-avoiding permutations and Dyck paths. To mention one, J. Bandlow and K. Killpatrick introduced an interesting bijection which sends the inversion number inv(σ) := |{i < j : σ_{i} > σ_{j}}| of a 312-avoiding permutation σ to the area statistic of the corresponding Dyck path. We will discuss this and other bijections in more detail in Sections 5 and 6, for definitions see [1].

3. The bijection

In this section, we construct a bijection Φ between S_{n}(231) and D_{n} such that

maj(Φ(σ)) = maj(σ) + imaj(σ).

Lemma 3.1. Let σ ∈ S_{n}(231), with Des(σ) = {i_{1}, …, i_{k}}, Asc(σ) = {j_{1}, …, j_{n−k}}. Then

iDes(σ) = {σ_{i_{1}} − 1, …, σ_{i_{k}} − 1},
iAsc(σ) = ({σ_{j_{1}} − 1, …, σ_{j_{n−k}} − 1} \ {0}) ∪ {n}

Proof. Let i be a descent of σ. As σ is 231-avoiding, [σ_{i} − 1, σ_{i}] cannot be a subword of σ. In other words, σ̂(σ_{i} − 1) > σ̂(σ_{i}) = i, and therefore σ_{i} − 1 is a descent of σ̂. On the other hand, let i′ be a descent of σ̂, which is 312-avoiding. The same argument as above yields σ(σ̂_{i′+1}) > σ(σ̂_{i′+1} +1) or, equivalently, σ̂_{i′+1} is a descent of σ. This implies

iDes(σ) = {σ_{i_{1}} − 1, …, σ_{i_{k}} − 1}.

As Asc(σ) = [n] \ Des(σ), the statement about iAsc(σ) follows. □

Recall the definition of the involution ρ on S_{n} and its properties as discussed in Section 2. Together with Lemma 3.1, this implies the following corollary.

Corollary 3.2. Let σ be τ-avoiding for a given τ ∈ {132, 231, 312, 213}. Then

des(σ) = des(σ̂), asc(σ) = asc(σ̂).

Remark 3.3. For τ ∈ {123, 321}, the analogous statement of the previous corollary is false. E.g., σ = [2, 4, 1, 3] is 123-avoiding and

Des(σ) = {2}, iDes(σ) = {1, 3}.

Lemma 3.4. Let j be an ascent of a 231-avoiding permutation σ and let k > j. Then σ_{k} > σ_{j}.

Proof. This follows immediately from the fact that σ is 231-avoiding. □

For the remaining part of this section, set σ to be a 231-avoiding permutation. Our next goal is to show that σ is uniquely determined by its ascent set and the image of its ascent set. Given the sets

Asc(σ) = {j_{1}, …, j_{n−k} = n}, σ(Asc(σ)) = {ℓ_{1}, …, ℓ_{n−k}}

in increasing order (i.e., j_{1} < ⋯ < j_{n−k} and ℓ_{1} < ⋯ < ℓ_{n−k}). Then, by the previous lemma, σ(j_{1}) < ⋯ < σ(j_{n−k}), and therefore σ(j_{i}) = ℓ_{i}.

To determine σ on its descent set, we determine σ on its descent blocks, i.e., the maximal sequences of consecutive descents. On any descent block {j_{i} + 1, …, j_{i+1} − 1}, σ is decreasing and bounded from below by the image on the ascent following the sequence (recall that our definition of the ascent set implies that every descent block is followed by an ascent). In symbols, σ(j_{i} + 1) > ⋯ > σ(j_{i+1} − 1) > σ(j_{i+1}). Together with the property of being 231-avoiding, this determines σ on its descents from right to left: start with the rightmost descent, say m. Then σ(m) is given by the smallest unassigned integer larger than σ(m + 1). Repeat this process by going through all descents from right to left as shown in Example 3.6.

By Lemma 3.1 and the above discussion we conclude the following fact, which is, in a slightly different context, originally due to A. Reifegerste, see [13, Proposition 2.4] and the following discussion.

Corollary 3.5. σ is uniquely determined by Des(σ) and iDes(σ).

Example 3.6. Let σ ∈ S_{6}(231) such that

Des(σ) = {1, 2, 4, 5}, iDes(σ) = {1, 3, 4, 5}.

This implies

Asc(σ) = {3, 6}, iAsc(σ) = {2, 6}.

By Lemma 3.1, we have

σ(Des(σ)) = {2, 4, 5, 6}, σ(Asc(σ)) = {1, 3}.

As described in the previous discussion, we first determine σ on its ascent set,

σ_{3} = 1 < σ_{6} = 3.

Then, we determine σ on its descents from right to left. The rightmost descent, 5, is mapped to the smallest unassigned integer larger than σ(6) = 3, which is 4; the next descent, 4, is mapped to the smallest unassigned integer larger than σ(5) = 4, which is 5; and so on. This gives

σ_{6} = 3 < σ_{5} = 4 < σ_{4} = 5, σ_{3} = 1 < σ_{2} = 2 < σ_{1} = 6,

and in total, we get σ = [6, 2, 1, 5, 4, 3].

Our next goal is to construct a bijection between Asc(σ) and iAsc(σ) such that the image of any ascent j is less than or equal to j.

Let j be an ascent of σ. By τ(j), we denote the size of the descent block immediately left of j, or, equivalently,

τ(j) := j − 1 − j′,

with j′ being the largest ascent such that j′ < j (respectively 0 if j is the first ascent).

Lemma 3.7. Let j be an ascent of σ. Then

j ≥ σ_{j} + τ(j).

Proof. Lemma 3.4 implies σ_{k} > σ_{j} for all k such that k > j and for all k such that j > k > j − τ(j). Therefore, n − j ≤ n − σ(j) − τ(j), which is equivalent to the statement. □

Corollary 3.8. Let Asc(σ) = {j_{1}, …, j_{n−k}}. Then, for any 1 ≤ ℓ < n − k, we have

j_{ℓ} ≥ σ_{j_{ℓ+1}} − 1.

Proof. By Lemma 3.7, j_{ℓ+1} is greater than or equal to σ_{j_{ℓ+1}} + τ(j_{ℓ+1}), which, by definition, is equal to σ_{j_{ℓ+1}} + j_{ℓ+1} − 1 − j_{ℓ}. This proves the corollary. □

By Lemma 3.1 and Corollary 3.8, we can define a bijection between Asc(σ) and iAsc(σ), which has the desired property that the image of an ascent j is less than or equal to j in the following way:

j_{ℓ} ↦ σ_{j_{ℓ+1}} − 1 for 1 ≤ ℓ < n − k,
j_{n−k} ↦ n

This implies the following corollary concerning the descent sets of σ and σ̂:

Corollary 3.9. Let Des(σ) = {i_{1}, …, i_{k}} and let iDes(σ) = {i′_{1}, …, i′_{k}} such that i_{1} < ⋯ < i_{k} and i′_{1} < ⋯ < i′_{k}. Then i_{ℓ} ≤ i′_{ℓ} for 1 ≤ ℓ ≤ n.

Now we are in the position to define the proposed bijection.

Definition 3.10. Define a map Φ from S_{n}(231) to D_{n} as follows: let σ ∈ S_{n}(231) with Des(σ) = {i_{1}, …, i_{k}} and iDes(σ) = {i′_{1}, …, i′_{k}}, such that

i_{1} < ⋯ < i_{k} < i_{k+1} := n, i′_{1} < ⋯ < i′_{k} < i′_{k+1} := n.

Then Φ(σ) is defined to be the Dyck path starting with i′_{1} 0’s, followed by i_{1} 1’s, followed by i′_{2} − i′_{1} 0’s, followed by i_{2} − i_{1} 1’s, followed by i′_{3} − i′_{2} 0’s, and so on, ending with i_{k+1} − i_{k} 1’s.

Theorem 3.11. The map Φ defined in the previous definition is well-defined and bijective.

Proof. By Proposition 3.2 and Corollary 3.9, Φ is well-defined and by Proposition 3.5 it is injective and therefore bijective. □

From the definition, we immediately obtain the following corollary.

Corollary 3.12. Let σ ∈ S_{n}(231). Then

Set_{X}(Φ(σ)) = Des(σ), Set_{Y} (Φ(σ)) = iDes(σ),

and, in particular, maj(Φ(σ)) = maj(σ) + imaj(σ).

Example 3.13. Let σ be the permutation defined in Example 3.6. As the descent set of σ is {1, 2, 4, 5} and the descent set of its inverse is {1, 3, 4, 5}, the coordinates of the descents of Φ(σ) are (1, 1), (2, 3), (4, 4) and (5, 5) and therefore Φ(σ) = 01 001 011 01 01 is the Dyck path described in Example 2.5. Furthermore,

maj(σ) = 1 + 2 + 4 + 5 = 12,
imaj(σ) = 1 + 3 + 4 + 5 = 13,
maj(Φ(σ)) = 2 + 5 + 8 + 10 = 25.

In Figure 2 all 231-avoiding permutations of the set {1, 2, 3, 4} and their associated Dyck paths are shown.

[figure: [1, 2, 3, 4] ↦; [4, 1, 2, 3] ↦; [1, 4, 2, 3] ↦; [1, 2, 4, 3] ↦; [3, 1, 2, 4] ↦]

[figure: [4, 3, 1, 2] ↦; [4, 1, 3, 2] ↦; [1, 3, 2, 4] ↦; [1, 4, 3, 2] ↦; [2, 1, 3, 4] ↦]

[figure: [4, 2, 1, 3] ↦; [2, 1, 4, 3] ↦; [3, 2, 1, 4] ↦; [4, 3, 2, 1] ↦]

Figure 2. The bijection between S_{4}(231) and D_{4}.

4. A bistatistic on 231-avoiding permutations

Define the polynomial A_{n}(q, t) by

A_{n}(q, t) := ∑_{σ∈S_{n}(231)} q^{maj(σ)}t^{\binom{n}{2}−imaj(σ)}.

The first values of A_{n}(q, t) are given by

A_{1}(q, t) = 1,
A_{2}(q, t) = q + t,
A_{3}(q, t) = q^{3} + q^{2}t + qt^{2} + t^{3} + qt,
A_{4}(q, t) = q^{6} + q^{5}t + q^{4}t^{2} + 2q^{3}t^{3} + q^{2}t^{4} + qt^{5} + t^{6} + q^{4}t + q^{3}t^{2} + q^{2}t^{3} + qt^{4} + q^{3}t + qt^{3}.

Obviously, A_{n}(q, t) reduces for q = t = 1 to Cat_{n} and the bijection Φ defined in the previous section shows that A_{n}(q, t) can also be described in terms of Dyck paths. As considered by J. Fürlinger and J. Hofbauer in [5, Section 5], define two statistics maj_{0} and maj_{1} on a Dyck path D by

maj_{0}(D) := ∑_{i∈Des(D)} |{j ≤ i : D_{j} = 0}|, maj_{1}(D) := ∑_{i∈Des(D)} |{j ≤ i : D_{j} = 1}|.

Corollary 4.1. Let Φ be the bijection defined in Theorem 3.11, and let σ be a 231avoiding permutation. Then

maj_{1}(Φ(σ)) = maj(σ), maj_{0}(Φ(σ)) = imaj(σ),

and furthermore

A_{n}(q, t) = ∑_{D∈D_{n}} q^{maj_{1}(D)}t^{\binom{n}{2}−maj_{0}(D)}.

Since maj_{1}(D) + maj_{0}(D) = maj(D), we get

q^{\binom{n}{2}}A_{n}(q, q^{−1}) = ∑_{D∈D_{n}} q^{maj(D)},

which is equal to MacMahon’s q-Catalan number defined in the introduction, see [5, Section 3]. Using another identity in [5], we obtain the following generating function identity.

Theorem 4.2. A_{n}(q, t) satisfies the generating function identity

∑_{n≥0} \frac{A_{n}(q, t) z^{n}}{(1 + qz) … (1 + q^{n+1}z)(1 + tz) … (1 + t^{n+1}z)} = 1.

Proof. Setting x = 1, a = q^{−1} and b = q in [5, Theorem 5] gives the above identity. □

The following corollary follows immediately from the fact that the generating function identity proved in Theorem 4.2 is symmetric in q and t.

Corollary 4.3. The polynomial A_{n}(q, t) is symmetric in q and t,

A_{n}(q, t) = A_{n}(t, q).

Now, we want to provide a bijective proof of a refinement of this symmetry.

Theorem 4.4.

∑_{σ∈S_{n}(231)} a^{des(σ)}q^{maj(σ)}t^{imaj(σ)} = ∑_{σ∈S_{n}(312)} a^{n−1−des(σ)}q^{\binom{n}{2}−maj(σ)}t^{\binom{n}{2}−imaj(σ)}.

Proof. Let Ψ be the involution on S_{n}(231) defined by the rule that a given σ is mapped to the unique τ with Des(τ) := [n − 1] \ iDes(σ) and iDes(τ) := [n − 1] \ Des(σ) (in Section 3, we proved the existence of such a τ). This implies des(σ) = n−1−des(Ψ(σ)) and furthermore

maj(σ) = \binom{n}{2} − imaj(Ψ(σ)), imaj(σ) = \binom{n}{2} − maj(Ψ(σ)).

Since mapping a permutation to its inverse interchanges Des(σ) and iDes(σ), the statement follows. □

Remark 4.5. Equivalently, we could have defined the bijection Ψ in the proof of Theorem 4.4 in terms of Dyck paths by the rule that a given Dyck path D is mapped to the unique Dyck path D′ with

Set_{X}(D′) = [n − 1] \ Set_{Y} (D), Set_{Y} (D′) = [n − 1] \ Set_{X}(D).

5. Another description of Φ

The bijection Φ defined in Definition 3.10 is closely connected to other bijections from pattern-avoiding permutations to Dyck paths. In [11], C. Krattenthaler constructed bijections from 132- and from 123-avoiding permutations to Dyck paths which were recently related to other bijections between pattern-avoiding permutations and Dyck paths by D. Callan in [2]. In this section, we express the bijection Φ in terms of Krattenthaler’s bijection from 132-avoiding permutations to Dyck paths, which we denote by κ.

First, we recall the definition of κ from [11, Section 2] and give an example. For any Dyck path D, the height of D at position i is the number of north steps minus the number of east steps until and including position i. Now, let σ = [σ_{1}, …, σ_{n}] be a 132-avoiding permutation and let h_{i} denote the number of j’s larger than i such that σ_{j} > σ_{i}. Read σ from left to right and successively generate a Dyck path. When σ_{i} is read, then in the path we adjoin as many north steps as necessary, followed by an east step from height h_{i} + 1 to height h_{i}.

Example 5.1. Let σ = [3, 4, 5, 1, 2, 6]. Then (h_{1}, …, h_{6}) = (3, 2, 1, 2, 1, 0) which gives the heights of the east steps of the corresponding Dyck paths. Therefore, κ(σ) = 0000111 00111.

Our next goal is to express κ in terms of the descent set of σ and the descent set of σ̂.

Lemma 5.2. Let σ be any permutation. Then (i) h_{i+1} < h_{i} if and only if i ∈ Asc(σ), (ii) σ ∈ S_{n}(132) if and only if h_{i+1} ≥ h_{i} − 1 for all 1 ≤ i < n.

Proof. The first statement is obvious. as is the fact that σ ∈ S_{n}(132) implies h_{i+1} ≥ h_{i} − 1 for all 1 ≤ i < n. For the reverse statement we use that h_{i+1} ≥ h_{i} − 1 implies for an ascent i that there exists no k > i with σ_{i} < σ_{k} < σ_{i+1}. □

Proposition 5.3. Let σ be a 132-avoiding permutation. Then κ(σ) is the Dyck path D given by

Set_{X}(D) = Des(σ), Set_{Y} (D) = {i + h_{i} : i ∈ Des(σ)}.

Proof. The statement follows from the first part of the previous lemma and the definition of κ. □

Proposition 5.4. Let σ be a 132-avoiding permutation. Then

iDes(σ) = {n − i − h_{i} : i ∈ Des(σ)}.

Proof. Let i be a descent of σ. The number of σ_{j}’s right of σ_{i} that are smaller than σ_{i} is equal to n − i − h_{i}. Since σ is 132-avoiding, we know that the set of those σ_{j}’s is equal to {1, …, n − i − h_{i}}. This implies that σ̂_{n−i−h_{i}} > σ̂_{n−i−h_{i}+1}, and therefore n − i − h_{i} is a descent of σ̂.

Now let i be a descent of σ and let j > i. The previous lemma implies that i + h_{i} ≠ j + h_{j}, because otherwise {i, i + 1, …, j − 1} ⊆ Asc(σ), a contradiction to i ∈ Des(σ). The proposition follows from Corollary 3.2. □

These two propositions characterize κ in terms of the descent set of σ and the descent set of σ̂: let σ ∈ S_{n}(132). Then

Set_{X}(κ(σ)) = Des(σ), Set_{Y} (κ(σ)) = {n − j : j ∈ iDes(σ)}.

Example 5.5. Continuing the previous example, we have that Des(σ) and iDes(σ) are given by {3} and by {2}, respectively. On the other hand,

Set_{X}(κ(σ)) = {3} = Des(σ), Set_{Y} (κ(σ)) = {4} = {n − j : j ∈ iDes(σ)}.

Let D be a Dyck path with valleys {(i_{1}, j_{1}), …, (i_{k}, j_{k})}. The last map we need is the involution Ψ as described in Remark 4.5 followed by the involution on Dyck paths sending D to the Dyck path with valleys {(n − j_{k}, n − i_{k}), …, (n − j_{1}, n − i_{1})}. We denote this composition by ψ.

Now we can describe the relation of Φ and κ using the involutions ρ and ψ:

Theorem 5.6. κ = ψ ∘ Φ ∘ ρ.

Proof. Let σ be a 132-avoiding permutation. Then

Set_{X}(Φ ∘ ρ(σ)) = Des(ρ(σ)) = [n − 1] \ {n − i : i ∈ Des(σ)},
Set_{Y} (Φ ∘ ρ(σ)) = iDes(ρ(σ)) = [n − 1] \ iDes(σ).

On the other hand,

Set_{X}(ψ(D)) = {n − i : i ∈ [n − 1] \ Set_{X}(D)},
Set_{Y} (ψ(D)) = {n − i : i ∈ [n − 1] \ Set_{Y} (D)},

for a Dyck path D. So, in total, we have

Set_{X}(ψ ∘ Φ ∘ ρ(σ)) = Des(σ),
Set_{Y} (ψ ∘ Φ ∘ ρ(σ)) = {n − j : j ∈ iDes(σ)}.

Together with the above discussion, this implies the theorem. □

Example 5.7. Set σ := [6, 2, 1, 5, 4, 3]. As we have seen in Example 3.13, Φ(σ) = 01 001 011 01 01, and therefore ψ(Φ(σ)) = 0000111 00111. As shown in Example 5.1, this equals κ(ρ(σ)).

Next, we want to use the involutions Ψ, ρ, and σ ↦ σ̂ (we denote the latter by i) to prove an analogue of Theorem 4.4 for S_{n}(132) and S_{n}(213).

Theorem 5.8.

∑_{σ∈S_{n}(132)} a^{des(σ)}q^{maj(σ)}t^{imaj(σ)} = ∑_{σ∈S_{n}(213)} a^{n−1−des(σ)}q^{\binom{n}{2}−maj(σ)}t^{\binom{n}{2}−imaj(σ)}.

Proof. The bijection between S_{n}(132) and S_{n}(213) defined by ρ ∘ i ∘ Ψ ∘ ρ, where Ψ is meant as described in the proof of Theorem 4.4, sends the tristatistic (des, maj, imaj) to the tristatistic (n − 1 − des, \binom{n}{2} − maj, \binom{n}{2} − imaj):

(des, maj, imaj) ⟼^{ρ} (n − 1 − des, \binom{n}{2} − n des + maj, \binom{n}{2} − imaj)

⟼^{ψ} (des, imaj, n des − maj)

⟼^{i} (des, n des − maj, imaj)

⟼^{ρ} (n − 1 − des, \binom{n}{2} − maj, \binom{n}{2} − imaj).

□

Corollary 5.9.

∑_{σ∈S_{n}(132)} q^{maj(σ)}t^{imaj(σ)} = ∑_{σ∈S_{n}(213)} q^{\binom{n}{2}−maj(σ)}t^{\binom{n}{2}−imaj(σ)}.

Computations suggest that the statement is also true when summing over S_{n}(123) and over S_{n}(321) respectively. E.g.,

\{( maj(σ), imaj(σ)) : σ ∈ S_{4}(123)\} = \{ \begin{matrix}(5, 5), (2, 4), (4, 4), (5, 4), (4, 2), (3, 3), (4, 3), \\ (2, 2), (5, 3), (4, 5), (3, 4), (4, 4), (3, 5), (6, 6) \end{matrix} \} ,
\{( maj(σ), imaj(σ)) : σ ∈ S_{4}(321)\} = \{ \begin{matrix}(0, 0), (3, 3), (2, 2), (3, 2), (2, 3), (1, 1), (4, 4), \\ (2, 1), (3, 1), (2, 4), (1, 2), (4, 2), (2, 2), (1, 3) \end{matrix} \} .

It would be implied by the following conjecture.

Conjecture 5.10. There exists a bijection from S_{n}(321) to itself which leaves the descent set Des invariant and maps the descent set of the inverse, iDes, to {n − j : j ∈ iDes}.

In the remaining part of this section, we describe the connection between Φ and the bijection by Bandlow and Killpatrick between S_{n}(132) and D_{n} mentioned at the end of Section 2. This shows how the area statistic on Dyck paths can be represented in S_{n}(231) via Φ. We denote the bijection Bandlow and Killpatrick defined in [1] by β. Together with M. Fulmek, C. Krattenthaler already described the connection between β and κ in a comment on Bandlow and Killpatrick’s article, [4]. By the definitions of Φ, κ and β, we have

β = Ψ ∘ Φ ∘ i.

As β sends the inversion number on S_{n}(132) to the area statistic on D_{n} and i leaves the inversion number invariant, we conclude for any 231-avoiding permutation σ,

inv(σ) = area(Ψ ∘ Φ(σ)).

6. Connections to q, t-Catalan numbers

The q, t-Catalan numbers Cat_{n}(q, t) can be defined in terms of the two statistics area and bounce on Dyck paths, which were first considered by J. Fürlinger and J. Hofbauer in [5] and by J. Haglund in [8] respectively. For definitions and for further information see e.g. [9].

Definition 6.1. Define the q, t-Catalan numbers Cat_{n}(q, t) as

Cat_{n}(q, t) := ∑_{D∈D_{n}} q^{area(D)}t^{bounce(D)}.

In [7], A. Garsia and M. Haiman proved that Cat_{n}(q, t) = Cat_{n}(t, q). But it is still an open problem to find a bijective proof of this fact. Furthermore, they proved that q^{\binom{n}{2}} Cat_{n}(q, q^{−1}) is equal to MacMahon’s q-Catalan numbers, and therefore

Cat_{n}(q, q^{−1}) = A_{n}(q, q^{−1}).

Simple computations show that, for n ≥ 4, Cat_{n}(q, t) ≠ A_{n}(q, t), but the computations lead to the following guess. It was verified for n ≤ 10.

Guess 6.2. We have

Cat_{n}(q, t) = ∑_{D∈D_{n}} q^{maj_{1}(D)−k_{D}}t^{\binom{n}{2}−maj_{0}(D)−k_{D}},

for appropriate non-negative integers k_{D}.

Example 6.3. Let n = 4. Then

Cat_{4}(q, t) = q^{6} +q^{5}t+q^{4}t^{2} +q^{3}t^{3} +q^{2}t^{4} +qt^{5} +t^{6} +q^{4}t+q^{3}t^{2} +q^{2}t^{3} +qt^{4} +q^{3}t+q^{2}t^{2} +qt^{3},

and therefore

A_{4}(q, t) − Cat_{4}(q, t) = q^{3}t^{3} − q^{2}t^{2} = q^{2}t^{2}(qt − 1).

This shows that

Cat_{4}(q, t) = ∑_{D∈D_{4}} q^{maj_{1}(D)−k_{D}}t^{\binom{n}{2}−maj_{0}(D)−k_{D}},

where either k_{D} = \{ \begin{matrix}1, & D = 01 01 0011 \\ 0, & otherwise \end{matrix} , or k_{D} = \{ \begin{matrix}1, & D = 000111 01 \\ 0, & otherwise \end{matrix} .

Remark 6.4. For n = 4, the involution defined in Corollary 4.3 interchanges the paths 01 01 0011 and 000111 01. Therefore even if one could determine the k_{D}’s in Guess 6.2, the proposed involution would fail to prove the open problem of finding a bijective proof of the symmetry property of Cat_{n}(q, t).

References

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

[2] D. Callan, Bijections from Dyck paths to 321-avoiding permutations revisited, preprint, available

    at arχiv:0711.2684v1 (2007).

[3] D. Foata and G.-N. Han, The q-series in combinatorics; permutation statistics, lecture notes,

    available at http://www-irma.u-strasbg.fr/~foata/paper/index.html (2003).

[4] M. Fulmek and C. Krattenthaler, Comments on “An area-to-inv bijection between Dyck paths and 312-avoiding permutations” by J. Bandlow and K. Killpatrick, Electron. J. Combin. 8 (1) (2002), Article R40.

[5] J. Fürlinger and J. Hofbauer, q-Catalan numbers, J. Combin. Theory Ser. A 40 (1985), 248–264.

[6] A. Garsia and J. Haglund, A positivity result in the theory of Macdonald polynomials, Proc. Natl. Acad. Sci. USA 98 (2001), 4313–4316.

[7] A. Garsia and M. Haiman, A remarkable q, t-Catalan sequence and q-Lagrange inversion, J. Algebraic Combin. 5 (1996), 191–244.

[8] J. Haglund, Conjectured statistics for the q, t-Catalan numbers, Adv. Math. 175 (2003), 319–334.

[9] , The q, t-Catalan numbers and the space of diagonal harmonics, University Lecture Series, Amer. Math. Soc. 41 (2008).

[10] D.E. Knuth, The art of computer programming, vol. 1, Addison-Wesley, Reading, Mass. (1973).

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

[12] P.A. MacMahon, Combinatory analysis, vol. 2, Cambridge University Press, London (1960).

[13] A. Reifegerste, On the diagram of 132-avoiding permutations, European J. Combin. 24 (2003), 759–776.

[14] R.P. Stanley, Enumerative combinatorics, vol. 2, Cambridge University Press (1999).

Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna, Austria

  E-mail address: christian.stump@univie.ac.at
  URL: http://homepage.univie.ac.at/christian.stump/