Séminaire Lotharingien de Combinatoire 77 (2018), Article B77f

AN INVOLUTION ON DYCK PATHS THAT PRESERVES THE RISE

COMPOSITION AND INTERCHANGES THE NUMBER OF RETURNS AND THE POSITION OF THE FIRST DOUBLE FALL

MARTIN RUBEY

Abstract. Motivated by a recent paper of Adin, Bagno and Roichman, we present an involution on Dyck paths that preserves the rise composition and interchanges the number of returns and the position of the first double fall.

1. Introduction

Let 𝔖_{n}(321) be the set of 321-avoiding permutations on n letters. In a recent paper of Adin, Bagno and Roichman [1] a new equidistribution result of two statistics on 𝔖_{n}(321) is used to demonstrate the Schur positivity of quasi-symmetric functions associated with certain subsets of 𝔖_{n}(321). Using a recursively defined bijection^{1} the authors establish

∑_{π∈𝔖_{n}(321)} x^{LRMAX(π)}q^{bl(π)} = ∑_{π∈𝔖_{n}(321)} x^{LRMAX(π)}q^{n−ldes(π^{−1})}, where

• LRMAX(π) is the set of positions of the left-to-right maxima of π and x^{L} = ∏_{i∈L} x_{i},

• bl(π) = |{i : ∀j ≤ i : π(j) ≤ i}| is the number of blocks of π and

• ldes(π) = max ({0} ∪ {i : π(i) > π(i + 1)}) is the position of the last descent of

π. We exhibit an involution which proves the stronger result that, fixing LRMAX, the joint distribution of π ↦ bl(π) and π ↦ n − ldes(π^{−1}) is in fact symmetric.

Let us first transform the statistics involved into statistics on Dyck paths, using a bijection due to Krattenthaler [3]^{2}. To do so, it is convenient to define a Dyck path as a path in ℕ^{2} consisting of (1, 0)- and (0, 1)-steps beginning at the origin, ending at (n, n), and never going below the diagonal y = x. We refer to (1, 0)-steps also as east steps or falls, and to (0, 1)-steps also as north steps or rises, and the number n as the semilength of the path. Krattenthaler’s bijection maps

• 𝔖_{n}(321) to the set of Dyck paths 𝔇_{n} of semilength n,

• LRMAX(π) to RISES(D), the set of x-coordinates (plus 1) of the north steps of the Dyck path,

• bl(π) to ret(D), the number of returns of the path, that is, the number of east steps that end on the main diagonal,

• ldes(π^{−1}) to ldr(D), the y-coordinate of the midpoint of the last double rise, that is, the last pair of two consecutive north steps. For the path without double rises, we set ldr(D) = 0.

Supported by the Austrian Science Fund (FWF): P 29275.

1http://www.findstat.org/Mp00124

2http://www.findstat.org/Mp00119

The purpose of this note is to provide an involution Φ^{3} that implies

∑_{π∈𝔇_{n}} x^{RISES(π)}p^{ret(D)}q^{n−ldr(D)} = ∑_{π∈𝔇_{n}} x^{RISES(π)}p^{n−ldr(D)}q^{ret(D)}.

2. An involution on Dyck paths

In the spirit of [2]^{4}, we first introduce an invertible map ϕ taking a Dyck path D that ends with two east steps and satisfies ldr(D) < n − 1 (that is, not maximal) to a Dyck path ϕ(D) that ends with two east steps and has at least two returns. The crucial properties of this map are as follows:

• RISES(ϕ(D)) = RISES(D)

• ret(ϕ(D)) = ret(D) + 1

• ldr(ϕ(D)) = ldr(D) + 1 The desired involution Φ then maps an arbitrary path D(NE)^{ℓ} (of semilength n + ℓ) to ϕ^{(n−ldr(D)−ret(D))}(D) (NE)^{ℓ}.

To define ϕ, write D as the concatenation of three paths P, Q and R where

• R is maximal such that it has no double rises, begins with a rise and the path Q before R ends with an east step, and

• Q R is a prime Dyck path, that is, its only return is the final east step. Let N_{0} Q_{0} N_{1} Q_{1} … N_{k} Q_{k} be the prime decomposition of Q, that is, all the Q_{i} are prime Dyck paths and the N_{i} are sequences of north steps. Note that N_{0} is non-empty, because Q does not return to the diagonal. We distinguish three cases, illustrated in Figure 1:

(1) If k = 0 or N_{1} ≠ ∅ define ϕ(D) = P Q_{0} N_{1} … N_{k} Q_{k} N_{0} R. In the remaining two cases let N be all but one of the north steps of the final rise in Q, and let Q′ be Q with N_{0}, Q_{0} and N erased.

(2) If N_{1} = ⋯ = N_{k} = ∅ define ϕ(D) = P N Q_{0} Q′ N_{0} R.

(3) Otherwise define ϕ(D) = P Q_{0} N Q′ N_{0} R.

We now provide an inverse for ϕ. Let D̃ be a Dyck path that ends with two east steps and has at least two returns. Write D̃ as the concatenation of paths P, Q̃, Ẽ, Ñ and R where

• R is maximal such that it has no double rises and begins with a rise, and

• Q̃ Ẽ Ñ R is a Dyck path with precisely two returns, Ñ is a maximal sequence of

north steps and Ẽ is a maximal sequence of east steps. Let Ñ_{0} Q̃_{1} Ñ_{1} … Q̃_{ℓ} Ñ_{ℓ} be the prime decomposition of Q̃. (˜1) If Q̃ ends with a double rise, we have ϕ^{(−1)}(D̃) = P Ñ Q̃ Ẽ R. (˜2) Otherwise, if Q̃ has no returns, ϕ^{(−1)}(D̃) = P Ñ Q̃_{1} Ñ_{1} … Q̃_{ℓ} Ñ_{ℓ} Ñ_{0} Ẽ R. (˜3) Otherwise, ϕ^{(−1)}(D̃) = P Ñ Q̃_{1} Q̃_{2} Ñ_{2} … Q̃_{ℓ} Ñ_{ℓ} Ñ_{1} Ẽ R. To conclude, we show that applying the constructions in Cases (1), (2) and (3) above

a path corresponding to Cases (˜1), (˜2) and (˜3), respectively. Suppose that D̃ = ϕ(D) is obtained by applying Case (1). Because Q_{k} ends with the last double rise of D followed by east steps, Q̃ ends with a double rise.

3http://www.findstat.org/Mp00132

4http://www.findstat.org/Mp00118

Cases (1) and (˜1):

0 1 2 4 5 8 10 R Q N_{0} N_{1}

↦ 0 1 2 4 5 8 10 Ñ Ẽ R Q̃

Cases (2) and (˜2):

0 1 3 5 7 11 12 R Q N_{0}

↦ 0 1 3 5 7 11 12 R Q̃ Ñ Ẽ

Cases (3) and (˜3):

0 1 2 4 5 7 8 9 R Q N_{0} N_{2}

↦ 0 1 2 4 5 7 8 9 R Q̃ Ñ Ẽ

Figure 1. Examples for Dyck paths and their images under ϕ

In Case (2), N Q_{0} Q′ is a prime Dyck path whose last sequence of north steps has length 1 so Q̃ does not end with a double rise and has no returns, whereas Q̃ Ẽ is a prime Dyck path.

Finally, in Case (3), N Q′ N_{0} has no returns and its last sequence of north steps has length 1. Thus, Q̃ does not end with a double rise, but does have a return coming from Q_{0}.

References

[1] R. M. Adin, E. Bagno and Y. Roichman, Block decomposition of permutations and Schur-positivity, J. Algebraic Combin. (to appear); arχiv:1611.06979.

[2] S. Elizalde and M. Rubey, Symmetries of statistics on lattice paths between two boundaries, Adv. Math. 287 (2016), 347–388.

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

4 MARTIN RUBEY

E-mail address: Martin.Rubey@tuwien.ac.at

Fakultät für Mathematik und Geoinformation, TU Wien, Austria