# Permutations and Pairs of Dyck Paths

Authors: Marilena Barnabei; Flavio Bonetti; Matteo Silimbani
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

We define a mapv between the symmetric group Sn and the set of pairs of Dyck paths of semilength n. We show that the map v is injective when restricted to the set of 1234-avoiding permutations and characterize the image of this map.


---

## Body

## 1. Introduction

We say that a permutationσ∈Sn contains a pattern τ∈Sk if σ contains a subsequence that is order-isomorphic to τ. Otherwise, we say that σ avoids τ. Given a pattern τ, denote by Sn(τ) the set of permutations in Sn avoiding τ.The sets of permutations that avoid a single patternτ∈S3 have been completely determined in last decades. More precisely, it has been shown [1] that, for every τ∈S3, the cardinality of the set Sn(τ) equals the nth Catalan number, which is also the number of Dyck paths of semilength n (see [2] for an exhaustive survey). Many bijections between Sn(τ), τ∈S3, and the set of Dyck paths of semilength n have been described (see [3] for a fully detailed overview).The case of patterns of length4 appears much more complicated, due both to the fact that the patterns τ∈S4 are not equidistributed on Sn, and the difficulty of describing bijections between Sn(τ), τ∈S4, and some set of combinatorial objects.In this paper we study the caseτ=1234. An explicit formula for the cardinality of Sn(1234) has been computed by I. Gessel (see [2, 4]).We present a bijection betweenSn(1234) and a set of pairs of Dyck paths of semilength n. More specifically, we define a map ν from Sn to the set of pairs of Dyck paths, prove that every element in the image of ν corresponds to a single element in Sn(1234), and characterize the set of all pairs that belong to the image of the map ν.


## 2. Dyck Paths

A Dyck path of semilengthn is a lattice path starting at (0,0), ending at (2n,0), and never going below the x-axis, consisting of up steps U=(1,1) and down steps D=(1,-1). A return of a Dyck path is a down step ending on the x-axis. A Dyck path is irreducible if it has only one return. An irreducible component of a Dyck path P is a maximal irreducible Dyck subpath of P.A Dyck pathP is specified by the lengths a1,…,ak of its ascents (viz., maximal sequences of consecutive up steps) and by the lengths d1,…,dk of its descents (maximal sequences of consecutive down steps), read from left to right. Set Ai=∑j=1iaj and Bi=∑j=1idj. If n is the semilength of P, we have of course Ak=Bk=n, hence the Dyck path P is uniquely determined by the two sequences A=A1,…,Ak-1 and B=B1,…,Bk-1. The pair (A,B) is called the ascent-descent code of the Dyck path P.Obviously, a pair(A,B), where A=A1,…,Ak-1 and B=B1,…,Bk-1, is the ascent-descent code of some Dyck path of semilength n if and only if (i)
0<k≤n;(ii)
1≤A1<A2<⋯<Ak-1≤n-1;(iii)
1≤B1<B2<⋯<Bk-1≤n-1;(iv)
Ai≥Bi for every 1≤i≤k-1.It is easy to check that the returns of a Dyck path are in one-to-one correspondence with the indices 1≤i≤k such that Ai=Bi. Hence, a Dyck path is irreducible whenever we have Ai>Bi for every 1≤i≤k-1.For example, the ascent-descent code of the Dyck pathP in Figure 1 is (A,B), where A=3,6 and B=2,3. Note that A1>B1 and A2>B2. In fact, P is irreducible.Figure 1We describe an involutionL due to Kreweras (a description of this bijection, originally defined in [5], can be found in [6]) and discussed by Lalanne (see [7, 8]) on the set of Dyck paths. Given a Dyck path P, the path L(P) can be constructed as follows: (i)
ifP is the empty path ϵ, then L(P)=ϵ;(ii)
ifP is nonempty:
(a)
flip the Dyck pathP around the x-axis, obtaining a path E;(b)
draw northwest (resp. northeast) lines starting from the midpoint of each double descent (resp. ascent);(c)
mark the intersection between theith northwest and ith northeast line, for every i;(d)
L(P) is the unique Dyck path that has valleys at the marked points (see Figure 2).We define a further involution L′ on the set of Dyck paths, which is a variation of the involution L, as follows: (i)
ifP is the empty path ϵ, then L(P)=ϵ;
(a)
consider a Dyck pathP and flip it with respect to a vertical line;(b)
decompose the obtained path into its irreducible componentsUPiD;(c)
replace every componentUPiD with UL(Pi)D in order to get L′(P) (see Figure 3).We point out that the map L′ appears in a slightly modified version in the paper [6].Figure 2
The mapL.Figure 3
The mapL'.We now give a description of the mapL′ in terms of ascent-descent code. Obviously, it is sufficient to consider the case of an irreducible Dyck path P.Let(A,B) be the ascent-descent code of an irreducible path P of semilength n, with A=A1,…,Ah and B=B1,…,Bh. Straightforward arguments show that the ascent-descent code (A′,B′) of L′(P) can be described as follows: (i)
setA-i=Ai-1 and set A^=[n-2]∖{A-1,…,A-h}={A^1,…,A^n-2-h}, where the A^i’s are written in decreasing order. Then, Ai′=n-A^i;(ii)
consider the set[n-2]∖{B1,…,Bh}={B^1,…,B^n-2-h}, where the B^i’s are written in decreasing order. Then, Bi′=n-1-B^i.Finally, we introduce an order relation ≤ on the set of Dyck paths of the same semilength. This order relation will be defined in three steps: (i)
consider two irreducible Dyck pathsP and Q of semilength n. Let (A,B) be the ascent-descent code of P, with A=A1,…,Ak and B=B1,…,Bk. We say that Q covers P in the relation ≤ if the ascent code of Q is obtained by removing an integer Ai from A and the descent code of Q is obtained by removing an integer Bj from B, with j≥i.Roughly speaking,Q covers P if it can be obtained from P by “closing” the rectangles corresponding to an arbitrary collection of consecutive valleys of P (see Figure 4);(ii)
the desired order relation≤ on the set of irreducible Dyck paths is the transitive closure of the above covering relation;(iii)
the relation≤ is extended to the set of all Dyck path of a given semilength as follows: if P and Q are two arbitrary Dyck paths and P=P1P2⋯Pr and Q=Q1Q2⋯Qs are their respective decompositions into irreducible parts, then P≤Q whenever r=s and Pi≤Qi for every i.We point out that the described order relation is a subset of the inclusion order relation defined in [9]. In the following sections, we will show that the defined relation is more suited for our studies.Figure 4
The dotted Dyck path covers the solid one.


## 3. LTR Minima and RTL Maxima of a Permutation

Some of the well-known bijections betweenSn(τ), τ∈S3, and the set of Dyck paths of semilength n (see [10–12]), are based on the two notions of left-to-right minimum and right-to-left maximum of a permutation σ=x1x2⋯xn:(i)
the valuexi is a left-to-right minimum (LTR minimum for short) at position i if xi<xj for every j<i;(ii)
the valuexi is a right-to-left maximum (RTL maximum) at position i if xi>xj for every j>i.For example, the permutation(1)σ=53482167
has the LTR minima 5, 3, 2, and 1 (at positions 1, 2, 5, and 6) and RTL maxima 7 and 8 (at positions 8 and 4).We denote byvmin(σ) and pmin(σ) the sets of values and positions of the LTR minima of σ, respectively. Analogously, vmax(σ) and pmax(σ) denote the sets of values and positions of the RTL maxima of σ.Recall that the reverse-complement of a permutationσ∈Sn is the permutation defined by
(2)σrc(i)=n+1-σ(n+1-i).
For example, consider the permutation
(3)σ=247318956.
Then
(4)σrc=451297368.
Note that the sets Sn(123) and Sn(1234) are closed under reverse-complement, namely, σ∈Sn(123) (resp., σ∈Sn(1234)) if and only if σrc∈Sn(123) (resp. σrc∈Sn(1234)).The first assertion in the next theorem goes back to the seminal paper [12], while the second one is an immediate consequence of the straightforward fact that x is a LTR minimum of a permutation σ at position i if and only if  n+1-x is RTL maximum of σrc at position n+1-i.Theorem 1.
A permutationσ∈Sn(123) is completely determined by the two sets vmin(σ) and pmin(σ) of values and positions of its left-to-right minima. A permutation in Sn(123) is completely determined, as well, by the two sets vmax(σ) and pmax(σ) of values and positions of its right-to-left maxima.Also1234-avoiding permutations can be characterized in terms of LTR minima and RTL maxima.This characterization can be found in [2] and is based on an equivalence relation on Sn defined as follows: σ≡σ′⇔σ and σ′ share the values and the positions of LTR minima and RTL maxima.For example,(5)1234≡1324.
Straightforward arguments lead to the following result stated in [2].Theorem 2.
Every equivalence class of the relation≡ contains exactly one 1234-avoiding permutation. In this permutation, the values that are neither LTR minima nor RTL maxima appear in decreasing order.


## 4. The Mapsλ and μ

We define two mapsλ and μ between Sn and the set 𝒟n of Dyck paths of semilength n. Given a permutation σ∈Sn, the path λ(σ) is contructed as follows:(i)
decomposeσ as σ=m1w1m2w2⋯mkwk, where m1,m2,…,mk are the left-to-right minima in σ and w1,w2,…,wk are (possibly empty) words;(ii)
setm0=n+1;(iii)
read the permutation from left to right and translate any LTR minimummi (i>0) into mi-1-mi up steps and any subword wi into li+1 down steps, where li denotes the number of elements in wi.The statement of Theorem 1 implies that the map λ is a bijection when restricted to Sn(123).Note that the ascent-descent code(A,B) of the path λ(σ) is obtained as follows: (i)
A=n+1-m1,n+1-m2,…,n+1-mk-1;(ii)
B=p2-1,p3-1,…,pk-1, where pi is the position of mi.We define a further map μ:Sn→𝒟n:(i)
decomposeσ as σ=uhMhuh-1Mh-1⋯u1M1, where M1,M2,…,Mh are the right-to-left maxima in σ and u1,u2,…,uk are (possibly empty) words;(ii)
setM0=0;(iii)
associate withMi (i>0) the steps Umi-mi-1D;(iv)
associate with each entry inui a D step.Also in this case, the map μ is a bijection when restricted to Sn(123).The ascent-descent code(A*,B*) of the path μ(σ) is obtained as follows: (i)
A*=M1,M2,…,Mh-1;(ii)
B*=n-P2,n-P3,…,n-Ph, where Pi is the position of Mi.In Figure 5 the two paths λ(σ) and μ(σ) corresponding to σ=6231754 are shown.Figure 5
The Dyck paths corresponding toσ=6231754.We can now define a mapν:Sn→𝒟n×𝒟n, setting
(6)ν(σ)=(λ(σ),μ(σ)).
The statement of Theorem 2 implies that the map ν is injective when restricted to Sn(1234).Note that the mapν behaves properly with respect to the reverse-complement and the inversion operators.Proposition 3.
Letσ be a permutation in Sn. One has: (i)
ν(σ)=(L,R)⇔ν(σrc)=(R,L), hence, the permutationσisrc-invariant if and only ifL=R.(ii)
ν(σ)=(L,R)⇔ν(σ-1)=(rev(L),rev(R)), whererev(P)is the path obtained by flippingPwith respect to a vertical line. Hence, the permutationσis an involution if and only if bothL and Rare symmetric with respect to a vertical line.For example, considerσ=6231754. The two paths associated with σ are shown in Figure 5. The permutation σrc=4317562 is associated with the two paths in Figure 6, while the permutation σ-1=4237615 corresponds to the two paths in Figure 7.Figure 6
The Dyck paths corresponding toσrc=4317562.Figure 7
The Dyck paths corresponding toσ-1=4237615.Moreover, the mapν has the following further property that will be crucial in the proof of our main result.Recall that a permutationσ∈Sn is said to be right-connected if it does not have a suffix σ′ of length k<n, that is a permutation of the symbols 1,2,…,k.For example, the permutation(7)τ=61275348
is right-connected, while
(8)σ=86457213
is not right-connected.According to this definition, we can split every permutation into right-connected components:(9)σ=86457213.
Note that, if a permutation σ is not right-connected, σ is the juxtaposition of a permutation σ′′ of the set {t+1,…,n} and the permutation σ′ of the set {1,…,t}.Proposition 4.
Letσ be a non right-connected permutation in Sn, with σ=σ1σ2, where σ1 is a permutation of the set {t+1,…,n} and σ2 is a permutation of set of the set {1,…,t}. Then
(10)λ(σ)=P1P2,μ(σ)=Q1Q2,
with Pi=λ(σi) and Qi=μ(σi), i=1,2.The order relation on Dyck paths defined in Section2 can be exploited to define two order relations on the set Sn as follows: (i)
σ≤λτ if and only if λ(σ)≤λ(τ);(ii)
σ≤μτ if and only if μ(σ)≤μ(τ).These order relations can be intrinsically described as follows.Proposition 5.
Letσ,τ∈Sn. One has σ≤λτ whenever: (i)
vmin(τ)⊆vmin(σ);(ii)
pmin(τ)⊆pmin(σ);(iii)
setting:vmin(σ)={m1,…,mh}(written in decreasing order),vmin(σ)∖vmin(τ)={mi1,mi2,…,mir}(in decreasing order),pmin(σ)∖pmin(τ)={pj1,pj2,…,pjr}(in increasing order),thenik<jkfor everyk.Similarly,σ≤μτwhenever:(i)
vmax(τ)⊆vmax(σ);(ii)
pmax(τ)⊆pmax(σ);(iii)
setting:vmax(σ)={M1,…,Mt}(written in increasing order),vmax(σ)∖vmax(τ)={Mi1,Mi2,…,Miq}(in increasing order),pmax(σ)∖pmax(τ)={Pj1,Pj2,…,Pjq}(in decreasing order),thenik<jkfor everyk.For example, consider the permutation(11)σ=687325914.
We have vmin(σ)={6,3,2,1}, pmin(σ)={1,4,5,8}, vmax(σ)={4,9}, and pmax(σ)={9,7}. The permutation
(12)τ=349268715
is such that vmin(τ)={3,2,1} and pmin(τ)={1,4,8}, hence, σ≤λτ. Moreover, the permutation
(13)ρ=271346589
is such that vmax(ρ)={9} and pmax(ρ)={9}, hence, σ≤μρ.


## 5. Main Results

We say that a pair of Dyck paths(P,Q) is admissible if there exists a permutation α such that P=λ(α) and Q=μ(α). Needless to say, the set of admissible pairs is in bijection with the set of 1234-avoiding permutations.In the case when the two pathsP and Q are irreducible, if the pair (P,Q) is admissible, then the peaks of the two paths have different x and y coordinates. We observe that this is not a sufficient condition. For example, consider the pair P=UUUDDUUDDD and Q=UUUUDUDDDD. The unique permutation σ=32154 having LTR-minima and RTL-maxima at the positions prescribed by P and Q has an extra LTR-minimum at position 2. Hence, (P,Q) is not admissible.We want to show that the operatorL′ on Dyck paths allows us to characterize the set of admissible pairs. We begin with a preliminary result concerning the pairs of Dyck paths corresponding to 123-avoiding permutations:Theorem 6.
For everyσ∈Sn(123), one has:
(14)μ(σ)=L′(λ(σ)).Proof.
Proposition4, together with the definition of the map L′, allows us to restrict our attention to the right-connected case.
Recall (see [12]) that a permutation σ avoids 123 if and only if the set vmin(σ)∪vmax(σ)=[n]. It is simple to check that, if σ is right-connected, the sets of LTR minima and RTL maxima are disjoint.
Consider now a permutationσ with LTR minima m1,…,mk-1,mk=1 and RTL maxima M1,…,Mh-1,Mh=n. Denote by (A,B) the ascent-descent code of the path P=λ(σ) and by (A*,B*) the ascent-descent code of the path μ(σ).
As noted before, the ascent codeA′ of L′(P) is obtained by computing the integers A-i=Ai-1 and then considering the set A^=[n-2]∖{A-1,…,A-k-1}, which can be written as
(15)A^={n-(n-1),n-(n-2),…,n-2}∖{n-m1,…,n-mk-1}.
Since {m1,…,mk-1}∪{M1,…,Mh-1}={2,3,…,n-1}, we have
(16)A^={n-M1,…,n-Mh-1}.
Hence, A′=A*.
Similarly, the descent codeB′ of L′(P) is obtained by considering the set
(17)B^=[n-2]∖{B1,…,Bk-1}=[n-2]∖{p2-1,…,pk-1}.
Since {p1,…,pk-1}∪{P1,…,Ph-1}={2,3,…,n-1}, we have
(18)B^={P2-1,…,Ph-1-1}.
Hence, B′=B*.For example, the123-avoiding permutation σ=859762431 corresponds to the pair of Dyck paths (P,L′(P)) in Figure 3.We are now in position to state our main result.Theorem 7.
A pair(P,Q) is admissible if and only if P≥L′(Q) and Q≥L′(P).Proof.
Consider a permutationσ∈Sn(1234) and let σ′ be the unique permutation in Sn(123) with the same LTR minima as σ, at the same positions. Obviously, σ′≤μσ, since in σ′ every element that is not a LTR minimum is a RTL maximum (see Proposition 5). Recalling that μ(σ′)=L′(λ(σ))=L′(P), we get the first inequality. The other inequality follows from the fact that the pair (P,Q) is admissible whenever the pair (Q,P) is admissible.
Consider now a pair of Dyck paths(P,Q) such that P≥L′(Q) and Q≥L′(P). Proposition 4 allows us to restrict to the case P,Q irreducible. Denote by σ and τ the permutations in Sn(123) corresponding via ν to the pairs (P,L′(P)) and (L′(Q),Q), respectively. Since P≥L′(Q) and Q≥L′(P), we have τ≤λσ and σ≤μτ.
We define a permutationα∈Sn as follows: (i)
α(x)=σ(x) if x∈pmin(σ);(ii)
α(x)=τ(x) if x∈pmax(τ);(iii)
ifx∉pmin(σ)∪pmax(τ), we have x∈pmax(σ)∖pmax(τ)=pmin(τ)∖pmin(σ)={pj1,…,pjr}, written in increasing order. Set
(19)α(pjk)=mik,
where mi1,mi2,…,mir are the elements in vmin(τ)∖vmin(σ)=vmax(σ)∖vmax(τ), written in decreasing order.The permutation α is obtained as the concatenation of three decreasing sequences. Hence, α avoids 1234. We have to prove that vmin(α)=vmin(σ) and vmax(α)=vmax(τ).
It is immediate thatvmin(σ)⊆vmin(α). In order to prove that vmin(σ)=vmin(α) it remains to show that the values mi1,mi2,…,mir are not LTR minima of α.
In fact, for everyk, consider α(pjk)=mik=τ(pik). Consider the sets A={p1,p2,…,pik}, B={m1,m2,…,mik}, and their subsets A′={pi1,pi2,…,pik} and B′={mi1,mi2,…,mik}. The k elements in B′ do not belong to vmin(σ) (and hence, the ik-k elements in B∖B′ are the largest elements in vmin(σ)). Proposition 5 ensures that each of them occupies in α a position that is strictly greater than the position occupied in τ. This implies that pjk<pik and that at most k-1 elements in B′ occupy in τ a position that belongs to A. Hence, in α, at least ik-k+1 positions in A are occupied by entries belonging to vmin(σ). This implies that there is in α a position preceding pjk occupied by a value less than mik. Hence, mik is not a LTR minimum of α.
Analogous arguments can be used to prove thatvmax(α)=vmax(τ). Hence, ν(α)=(P,Q), as desired.For example, consider the pair of Dyck paths in Figure8.Figure 8It can be checked thatP≥L′(Q) and Q≥L′(P). The permutations σ=ν-1((P,L′(P))) and τ=ν-1((L′(Q),Q)) are as follows:
(20)σ=498271653,τ=759432816.
We have vmin(σ)={4,2,1}, pmin(σ)={1,4,6}, vmin(τ)={7,5,4,3,2,1}, pmin(τ)={1,2,4,5,6,8}, vmax(σ)={3,5,6,7,8,9}, pmax(σ)={9,8,7,5,3,2}, vmax(τ)={6,8,9}, and pmax(τ)={9,7,3}.The permutationα=ν-1((P,Q)) is
(21)α=479251836.
As expected, vmin(α)=vmin(σ), pmin(α)=pmin(σ), vmax(α)=vmax(τ), and pmax(α)=pmax(τ).



---

*Source: 107454-2013-01-13.xml*