Séminaire Lotharingien de Combinatoire 63 (2010), Article B63a

THE DESCENT STATISTIC ON 123-AVOIDING PERMUTATIONS

MARILENA BARNABEI, FLAVIO BONETTI, AND MATTEO SILIMBANI

Abstract. We exploit Krattenthaler’s bijection between 123-avoi-ding permutations and Dyck paths to determine the Eulerian distribution over the set S_{n}(123) of 123-avoiding permutations in S_{n}. In particular, we show that the descents of a permutation correspond to valleys and triple ascents of the associated Dyck path. We get the Eulerian numbers of S_{n}(123) by studying the joint distribution of these two statistics on Dyck paths.

1. Introduction

A permutation σ ∈ S_{n} avoids a pattern τ ∈ S_{k} if σ does not contain a subsequence that is order-isomorphic to τ. The subset of S_{n} of all permutations avoiding a pattern τ is denoted by S_{n}(τ). Pattern avoiding permutations have been intensively studied in recent years from many points of view (see e.g. [7], [4], [1], and references therein).

In the case τ ∈ S_{3}, it has been shown that the cardinality of S_{n}(τ) equals the n-th Catalan number, for every pattern τ (see e.g. [3] and [7]), and hence the set S_{n}(τ) is in bijection with the set of Dyck paths of semilength n. Indeed, the six patterns in S_{3} are related as follows:

• 321 = 123^{rev},

• 231 = 132^{rev},
• 312 = 132^{c},
• 213 = (132^{c})^{rev},

where rev and c denote the usual reverse and complement operations. Hence, in order to determine the distribution of the descent statistic over S_{n}(τ), for every τ ∈ S_{3}, it is sufficient to examine the distribution of descents over two sets, say S_{n}(132) and S_{n}(123).

In both cases, the two bijections due to Krattenthaler [4] (see also [2]) allow to translate the descent statistic into some appropriate statistics on Dyck paths.

2000 Mathematics Subject Classification. 05A05 05A15 05A19.

Key words and phrases. Restricted permutations, Dyck paths, Eulerian numbers.

2 MARILENA BARNABEI, FLAVIO BONETTI, AND MATTEO SILIMBANI

In the case τ = 132, the descents of a permutation are in one-to-one correspondence with the valleys of the associated Dyck path (see [8] and [9]).

In this paper we investigate the case τ = 123. In particular, we exploit Krattenthaler’s map to translate the descents of a permutation σ ∈ S_{n}(123) into peculiar subconfigurations of the associated Dyck path, namely, valleys and triple ascents.

For that reason, we study the joint distribution of valleys and triple ascents over the set P_{n} of Dyck paths of semilength n, and we give an explicit expression for its trivariate generating function

A(x, y, z) = ∑_{n≥0} ∑_{𝒟∈P_{n}} x^{n}y^{v(𝒟)} z^{ta(𝒟)} = ∑_{n,p,q≥0} a_{n,p,q}x^{n}y^{p}z^{q},

where v(𝒟) denotes the number of valleys in 𝒟 and ta(𝒟) denotes the number of triple ascents in 𝒟. This series specializes to some well known generating functions, such as the generating function of Catalan numbers, Motzkin numbers, Narayana numbers, and sequence A092107 in [8] (see also [5]).

2. Dyck paths

A Dyck path of semilength n is a lattice path in the integer lattice ℕ × ℕ starting from the origin, consisting of n up-steps U = (1, 1) and n down steps D = (1, −1), never passing below the x-axis.

A return of a Dyck path is a down step ending on the x-axis, not counting the last step of the Dyck path. An irreducible Dyck path is a Dyck path with no return.

We note that a Dyck path 𝒟 can be decomposed according to its last return (last return decomposition) into the juxtaposition of a (possibly empty) Dyck path 𝒟′ of shorter length and an irreducible Dyck path 𝒟′′.

For example, the Dyck path 𝒟 = U^{5}D^{2}UD^{4}UDU^{3}DUD^{3} decomposes into 𝒟′ ⨁ 𝒟′′, where 𝒟′ = U^{5}D^{2}UD^{4}UD and 𝒟′′ = U^{3}DUD^{3}, as shown in Figure 1.

3. Krattenthaler’s bijection

In [4], Krattenthaler describes a bijection between the set S_{n}(123) and the set P_{n} of Dyck paths of semilength n.

Let σ = σ(1) … σ(n) be a 123-avoiding permutation. Recall that a right-to-left maximum of σ is an element σ(i) which is larger than σ(j) for all j with j > i (note that the last entry σ(n) is a right-to-left Figure 1. The last return decomposition of the Dyck path 𝒟 = U^{5}D^{2}UD^{4}UDU^{3}DUD^{3}.

maximum). Let x_{s}, …, x_{1} be the right-to-left maxima in σ. Then, we can write

(1)  σ = w_{s} x_{s} … w_{1} x_{1},

where w_{i} are (possibly empty) words. Moreover, since σ avoids 123, the word w_{s} w_{s−1} … w_{1} must be decreasing.

In order to construct the Dyck path κ(σ) corresponding to σ, read the decomposition (1) from right to left. Any right-to-left maximum x_{i} is translated into x_{i} − x_{i−1} up steps (with the convention x_{0} = 0) and any subword w_{i} is translated into l_{i} + 1 down steps, where l_{i} denotes the number of elements in w_{i}. Then, reflect the constructed path in a vertical line.

For example, the permutation σ = 6 4 7 3 2 5 1 in S_{7}(123) corresponds to the path in Figure 2.

Figure 2. The Dyck path κ(σ), with σ = 6 4 7 3 2 5 1.

4. The descent statistic

We say that a permutation σ has a descent at position i if σ(i) > σ(i + 1). We denote by des(σ) the number of descents of the permutation σ.

In this section we determine the generating function

E(x, y) = ∑_{n≥0} ∑_{σ∈S_{n}(123)} x^{n}y^{des(σ)} = ∑_{n≥0} ∑_{k≥0} e_{n,k}x^{n}y^{k},

where e_{n,k} denotes the number of permutations in S_{n}(123) with k descents.

Proposition 1. Let σ be a permutation in S_{n}(123), and 𝒟 = κ(σ). The number of descents of σ is

des(σ) = v(𝒟) + ta(𝒟),

where v(𝒟) is the number of valleys (the number of occurrences of DU) in 𝒟 and ta(𝒟) is the number of triple ascents (the number of occurrences of UUU) in 𝒟.

Proof. Let σ = w_{s} x_{s} … w_{1} x_{1} be a 123-avoiding permutation. The descents of σ occur precisely in the following positions:

1. between two consecutive symbols in the same word w_{i} (we have l_{i} − 1 of such descents),

2. after every right-to-left maximum x_{i}, except for the last one. The proof is completed as soon as we observe that:

1. every word w_{i} is mapped into an ascending run of κ(σ) of length l_{i} +1. Such an ascending run contains l_{i} −1 triple ascents, these in their turn are in bijection with the descents contained in w_{i},

2. every right-to-left maximum x_{i} with i ≥ 2 corresponds to a

valley in κ(σ).

□

The preceding result implies that we can switch our attention from permutations in S_{n}(123) with k descents to Dyck paths of semilength n with k valleys and triple ascents. Hence, we study the joint distribution of valleys and triple ascents over P_{n}, namely, we analyze the generating function

A(x, y, z) = ∑_{n≥0} ∑_{𝒟∈P_{n}} x^{n}y^{v(𝒟)} z^{ta(𝒟)} = ∑_{n,p,q≥0} a_{n,p,q}x^{n}y^{p}z^{q}.

We determine the relation between the function A(x, y, z) and the generating function

B(x, y, z) = ∑_{n≥0} ∑_{𝒟∈IP_{n}} x^{n}y^{v(𝒟)} z^{ta(𝒟)} = ∑_{n,p,q≥0} b_{n,p,q}x^{n}y^{p}z^{q}

of the same joint distribution over the set IP_{n} of irreducible Dyck paths in P_{n}.

Proposition 2. For every n > 2, we have:

(2)  b_{n,p,q} = a_{n−1,p,q−1} − a_{n−2,p−1,q−1} + a_{n−2,p−1,q}.

Proof. An irreducible Dyck path of semilength n with p valleys and q triple ascents can be obtained by prepending U and appending D to a Dyck path of semilength n − 1 of one of the two following types:

1. a Dyck path with p valleys and q triple ascents, starting with UD,

2. a Dyck path with p valleys and q − 1 triple ascents, which does

not start with UD. We observe that:

1. The paths of the first kind are in bijection with Dyck paths of semilength n − 2 with p − 1 valleys and q triple ascents, enumerated by a_{n−2,p−1,q}.

Figure 3. The Dyck path U^{2}DU^{3}D^{2}U^{3}D^{5} with 2 valleys and 2 triple ascents is obtained by prepending UD to the path U^{3}D^{2}U^{3}D^{4} with 1 valley and 2 triple ascents, and then elevating.

2. In order to enumerate the paths of the second kind we have to subtract from the integer a_{n−1,p,q−1} the number of Dyck paths of semilength n−1 with p valleys and q −1 triple ascents, starting with UD. Dyck paths of this kind are in bijection with Dyck paths of semilength n − 2 with p − 1 valleys and q − 1 triple ascents, enumerated by a_{n−2,p−1,q−1}.

□

Proposition 3. For every n > 0, we have:

(3)  a_{n,p,q} = b_{n,p,q} + ∑_{i=1}^{n−1} ∑_{j,s≥0} b_{i,j,s}a_{n−i,p−j−1,q−s}.

Figure 4. The Dyck path U^{3}DU^{2}D^{2}U^{3}D^{5} with 2 valleys and 2 triple ascents is obtained by elevating the path U^{2}DU^{2}D^{2}U^{3}D^{4} with 2 valleys and 1 triple ascent.

Proof. Let 𝒟 be a Dyck path of semilength n and consider its last return decomposition 𝒟 = 𝒟′ ⨁ 𝒟′′. If 𝒟′ is empty, then 𝒟 is irreducible. Otherwise, we have

• v(𝒟) = v(𝒟′) + v(𝒟′′) + 1,

• ta(𝒟) = ta(𝒟′) + ta(𝒟′′).

□

Identities (2) and (3) yield the following relations between the two generating functions A(x, y, z) and B(x, y, z).

Proposition 4. We have

(4) B(x, y, z) = (A(x, y, z) − 1)(xz + x^{2}y − x^{2}yz) + 1 + x + x^{2} − x^{2}z

and

(5) A(x, y, z) = B(x, y, z) + y(B(x, y, z) − 1)(A(x, y, z) − 1).

Proof. Note that recurrence (2) holds for n > 2. This fact gives rise to the correction terms of x-degree less than 3 in Formula (4). □

Combining Formulae (4) and (5) we obtain the following result.

Theorem 5. We have:

A(x, y, z) = \frac{1}{2xy(xyz − z − xy)} ( − 1 + xy + 2x^{2}y

− 2x^{2}y^{2} + xz − 2xyz − 2x^{2}yz + 2x^{2}y^{2}z (6)

+\sqrt{1 − 2xy − 4x^{2}y + x^{2}y^{2} − 2xz + 2x^{2}yz + x^{2}z^{2}}) .

This last result allows us to determine the generating function E(x, y) of the Eulerian distribution over S_{n}(123). In fact, the previous arguments show that

E(x, y) = A(x, y, y).

Hence, we obtain the following explicit expression for E(x, y).

Theorem 6. We have:

E(x, y) = \frac{\begin{matrix}−1 + 2xy + 2x^{2}y − 2xy^{2} − 4x^{2}y^{2} + 2x^{2}y^{3} \\ +\sqrt{1 − 4xy − 4x^{2}y + 4x^{2}y^{2}} \end{matrix}}{2xy^{2}(xy − 1 − x)} .

The first values of the sequence e_{n,d} are shown in the following table:

n/d 0 1 2 3 4 5 6
0 1
1 1
2 1 1
3 0 4 1
4 0 2 11 1
5 0 0 15 26 1
6 0 0 5 69 57 1
7 0 0 0 56 252 120 1

Needless to say, the series A(x, y, z) specializes to some well known generating functions. In particular, A(x, 1, 1) is the generating function of Catalan numbers, A(x, 1, 0) the generating function of Motzkin numbers, yA(x, y, 1) the generating function of Narayana numbers, and A(x, 1, z) the generating function of seq. A092107 in [8].

References

[1] M. Bóna, Combinatorics of permutations, Chapman & Hall/CRC, Boca Raton, 2004.

[2] A. Claesson and S. Kitaev, Classification of bijections between 321- and 132avoiding permutations Sém. Lothar. Combin. 60 (2008), Art. B60d, 30 pp.

[3] D. E. Knuth, The art of computer programming, vol. 1: “Fundamental algorithms,” Addison–Wesley, Reading Massachusetts, 1969.

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

[5] A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math. 307 (2007), 2909–2924.

[6] R. Simion, Combinatorial statistics on noncrossing partitions, J. Combin. Theory Ser. A 66 (1994), no. 2, 270–301.

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

[8] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,

   http://www.research.att.com/~njas/sequences/.

[9] M. Zabrocki, private communication.

Department of Mathematics, University of Bologna, P.zza di Porta San Donato 5, 40126 Bologna

E-mail address: barnabei@dm.unibo.it, bonetti@dm.unibo.it,
              silimban@dm.unibo.it