Catalan and Schröder permutations sortable by two restricted stacks

Contents lists available atScienceDirect

Information

Processing

Letters

www.elsevier.com/locate/ipl

Catalan

and

Schröder

permutations

sortable

by

two

restricted

stacks

Jean-Luc Baril

a

,

Giulio Cerbai

b

,

1

,

Carine Khalil

a

,

Vincent Vajnovszki

a

,

∗

a_{LIB,UniversitédeBourgogneFranche-Comté,B.P.47870,21078DijonCedex,France} b_{DipartimentodiMatematicaeInformatica“U.Dini”,UniversityofFirenze,Firenze,Italy}

a

r

t

i

c

l

e

i

n

f

o

a

b

s

t

r

a

c

t

Articlehistory:

Received14September2020

Receivedinrevisedform15February2021 Accepted2May2021

Availableonline19May2021 CommunicatedbyAmitChakrabarti

Keywords:

Stacksorting/twostacksinseries Patternavoidingpermutations/machines CatalanandtheSchrödernumbers Combinatorialproblems

Pattern avoiding machines were introduced recently by Claesson, Cerbai and Ferrari as a particular case of the two-stacks in series sorting device. They consist of two restrictedstacks inseries,ruledby aright-greedy procedure andthe stacksavoidsome specified patterns.Someoftheobtainedresultshave beenfurthergeneralizedto Cayley permutations by Cerbai, specialized to particular patterns by Defant and Zheng, or consideredinthecontextoffunctionsoverthesymmetricgroupbyBerlow.Inthiswork we study pattern avoiding machines where the first stack avoidsa pairof patterns of length3and investigatethosepairs forwhichsortablepermutationsarecountedbythe (binomialtransformofthe)CatalannumbersandtheSchrödernumbers.

©2021PublishedbyElsevierB.V.

1. Introduction

Pattern avoiding machines were recently introduced in [7] inattempttogainabetterunderstandingofsortable permutationsusingstacksinseries.Theyconsistoftwo re-strictedstacksinseries,equippedwitharight-greedy pro-cedure,wherethefirststackavoidsafixedpattern,reading the elements from top to bottom; and the second stack avoids thepattern21 (whichis anecessarycondition for themachinetosortpermutations).Theauthorsof [7] pro-vide a characterization of theavoided patterns forwhich sortable permutationsdonotformaclass,andthey show that those patterns are enumerated by the Catalan num-bers.Forspecificpatterns,suchas123 andthedecreasing patternofanylength,ageometricaldescriptionofsortable

*

Correspondingauthor.

E-mailaddresses:barjl@u-bourgogne.fr(J.-L. Baril),

giulio.cerbai@unifi.it(G. Cerbai),carine.khalil@u-bourgogne.fr(C. Khalil), vvajnov@u-bourgogne.fr(V. Vajnovszki).

1 _{G.C. is member of the INdAM Research group GNCS; he is} par-tiallysupportedbyINdAM-GNCS2020project“Combinatoriadelle per-mutazioni,delleparolee deigrafi:algoritmie applicazioni”.

permutationsis also obtained. The pattern132 has been solvedlaterin [8].Someoftheseresultshavebeenfurther generalizedto Cayley permutations in [9]. More recently, Berlow [5] exploresasinglestackversionofpattern avoid-ingmachines,wherethestackavoidsasetofpatternsand the sorting process is regarded as a function. Analogous machines,butbasedonthenotionofconsecutivepatterns, havebeenintroducedanddiscussedin [10].

In this work we study a variant of pattern-avoiding machines where the first stack avoids

(

σ

,

τ

)

, a pair of patterns oflength three.Following [7], we call it

(

σ

,

τ

)

-machine. More specifically, we restrict ourselves to those pairs of patterns for which sortable permutations are counted by either the Catalan numbers or two of their close relatives: the binomial transform of Catalan num-bers and the Schröder numbers. For the pair

(

132

,

231

)

we show that sortable permutations are those avoiding 1324 and2314,a setwhoseenumerationis givenbythe large Schröder numbers. Under certain conditions on the avoided patterns, the output of the first stack is bijec-tively related to its input (see [5,9]): it follows that for threepairsofpatterns,namely

(

123

,

213

)

,

(

132

,

312

)

and

(

231

,

321

)

,sortablepermutationsarecountedbythe

Cata-https://doi.org/10.1016/j.ipl.2021.106138 0020-0190/©2021PublishedbyElsevierB.V.

lannumbers.Thisresultwasconjecturedin [3] andsettled independently in [4,5]. Forthe pair

(

123

,

132

)

, we prove thatsortablepermutationsarethoseavoidingthepatterns 2314, 3214,4213 and the generalizedpattern

[24¯

13. We prove that sortable permutations are enumerated by the Catalan numbers by showing that the distribution of the firstelement isgivenbythe well-knownCatalantriangle. Finally, we show that for the pair

(

123

,

312

)

the corre-sponding countingsequence isthe binomial transformof Catalannumbers.

This paper is the extended version of the conference presentation[4] andsome ofthepresented results previ-ouslyappearin [3].

2. Notationsandsomepreliminaryresults

We start by recalling some classical definitions about pattern avoidance on permutations (see [12] for a more detailedintroduction). Denote by

Sn

the set of permuta-tions oflengthn andlet

S

= ∪n

_≥0

Sn.

Giventwo

permu-tations

σ

oflengthk and

π

=

π

1

· · ·

π

n,wesaythat

π

con-tains thepattern

σ

if

π

containsasubsequence

π

i1

· · ·

π

ik, withi1

<

i2

<

· · · <

ik,whichisorderisomorphicto

σ

.In thiscase,wesaythat

π

i1

· · ·

π

ikisanoccurrence ofthe pat-tern

σ

in

π

.Otherwise,wesaythat

π

avoids

σ

.

We say that

π

contains an occurrence ofthe (gener-alized) pattern

[

σ

if

π

contains an occurrenceof

σ

that involvesthefirstelement

π

1 of

π

.Forinstance,an

occur-renceof

[

12 in

π

correspondstoapairofelements

π

1

π

i,

with i

>

1 and

π

i

>

π

1. A barredpattern

σ

˜

is a pattern

wheresomeentriesarebarred.Let

σ

betheclassical pat-tern obtainedby removing all the bars from

σ

˜

.Let

τ

be the pattern whichis order isomorphic to the non-barred entries of

σ

˜

(i.e. obtained from

σ

˜

by removing all the barred entries and suitably rescaling the remaining ele-ments).Apermutation

π

avoids

σ

˜

ifeachoccurrenceof

τ

in

π

canbeextendedtoan occurrenceof

σ

.Forinstance, apermutation

π

avoidsthepattern

[

24¯13 ifforany subse-quence

π

1

π

i

π

j,with1

<

i

<

j and

π

1

<

π

j

<

π

i,thereis an indext,i

<

t

<

j,suchthat

π

1

π

i

π

t

π

j isanoccurrence of2413.

Given a set of (generalized) patterns T , denote by

Av

n

(

T

)

the setofpermutationsin

Sn

avoiding each pat-terninT .Similarly,let

Av

(

T

)

= ∪n

≥0

Av

n

(

T

)

.IfT

= {

σ

}

is asingleton,wewrite

Av

n

(

σ

)

and

Av

(

σ

)

.Inhiscelebrated book [13], Knuth gave the following characterization of stacksortablepermutations,whichisoftenconsideredthe starting point of stack sorting and permutation patterns disciplines.

Proposition1([13]).Apermutation

π

issortableusinga clas-sicalstack(thatis,a21-avoidingstack)ifandonlyif

π

avoids thepattern231.

Let T be a set of patterns. A T -stack is a stack that isnot allowed tocontain anoccurrenceofanypatternin T ,readingits elements fromtop tobottom. Givena per-mutation

π

,denotebyoutT

₍

_π

₎

_{thepermutationobtained} after passing

π

through the T -avoiding stack by apply-ing a greedy procedure, i.e. by always pushing the next element of the input, unless it creates an occurrence of

a forbidden pattern inside the stack. Denote by Sortn

(

T

)

theset oflength n permutationsthat are sortable by the T -machine, that is, by passing

π

through the T -avoiding stack and then through the 21-avoiding stack. Permuta-tions inSortn

(

T

)

arecalled T -sortable, andSort

(

T

)

is the setof T -sortablepermutationsofanylength.As a conse-quenceofProposition1,Sort

(

T

)

consistspreciselyofthose permutations

π

for which outT

(

π

)

avoids 231. To ease notations,if T is either a singleton T

= {

σ

}

or a pair of patterns T

= {

σ

,

τ

}

,wewill omitthecurlybracketsfrom theabovenotations.Forinstance,wewillwriteSort

(

σ

,

τ

)

insteadofSort

(

{

σ

,

τ

})

.

The authors of [7] showed that if

π

is a 12-sortable permutation of length n, then out12

(

π

)

=

n

(

n

−

1

)

· · ·

1. Moreover,by Proposition1 andapplyingthecomplement operation on the processed permutation, we have that Sort

(

12

)

= Av(

213

)

. In order to refer to thisresult later, we state itbelowina slightlymoregeneral form.A par-tial permutation of n is an injection

π

: {

1

,

2

,

. . . ,

k

}

→

{

1

,

2

,

. . . ,

n

}

,forsome 0

≤

k

≤

n,andtheintegerk issaid tobe the length of

π

. Welet a 12-stackact on apartial permutation

π

ofn in the naturalway by identifying

π

withthelistofitsimages.

Proposition2.If

π

isapartialpermutationofn whichis 12-sortable,thenout12

₍

_π

₎

_{isthedecreasingrearrangementofthe} symbolsof

π

.Moreover,

π

is12-sortableifandonlyifitavoids 213.

An entry

π

i ofa permutation

π

isa left-to-right min-imum if

π

i

<

π

j, for each j

<

i. The left-to-rightminima decomposition (briefly ltr-mindecomposition) of

π

is

π

=

m1B1m2B2

· · ·

mtBt,wherem1

>

m2

>

· · · >

mt arethe ltr-minimaof

π

andtheblock Bicontains theelements of

π

betweenmi andmi+1,for i

=

1

,

. . . ,

t

−

1. The last block Bt contains the elements that followmt in

π

.Note that mt

=

1. The notion of left-to-rightmaximum of a permu-tation

π

isdefinedsimilarly. Theltr-maxdecomposition of

π

is

π

=

M1B1M2B2

· · ·

MtBt,where M1

<

M2

<

· · · <

Mt are theltr-maximaof

π

.In thiscase Mt

=

n, wheren is thelengthof

π

.

Finally,thesequence

(

cn

)

n≥0,pervasiveinthispaper,is

thesequenceofCatalannumberscn

=

_n+1₁



2n n



(A000108 in [15]). 3. Pair

(

132

,

231

)

Thissectionisdevotedtotheanalysisofthe

(

123

,

231

)

-machine.

Theorem1.Considerthe

(

132

,

σ

)

-machine,where

σ

=

σ

1

· · ·

σ

k−1

σ

k

∈ Sk

,withk

≥

3 and

σ

k−1

>

σ

k.Givenapermutation

π

oflengthn,letm1B1

· · ·

mtBt

=

π

beitsltr-min decomposi-tion.Then:

1. Everytimealtr-minimummiispushedintothe

(

132

,

σ

)

-stack,the

(

132

,

σ

)

-stackcontainstheelementsmi−1

,

. . . ,

m2

,

m1,readingfromtoptobottom.Moreover,wehave

whereB

˜

iisarearrangementofBi.

2. If

π

is

(

132

,

σ

)

-sortable,thenB

˜

iisdecreasingforeachi. Moreover,foreachi

≤

t

−

1,wehaveBi

>

Bi+1(i.e.x

>

y foreachx

∈

Bi

,

y

∈

Bi+1).

Proof. 1. Let usconsider theevolution of the

(

132

,

σ

)

-stackon input

π

.Notethat, sincek

≥

3,the element m1 remains atthebottom ofthe

(

132

,

σ

)

-stack until

theendofthe process.Now,if B1 is notempty then

foreach x

∈

B1,the elements m2xm1 form an

occur-rence of132.Therefore theblock B1 is extracted

be-forem2 entersthe

(

132

,

σ

)

-stack.After m2 ispushed,

the

(

132

,

σ

)

-stackcontainsm2m1,readingfromtopto

bottom. Sincem2

<

m1,but

σ

k−1

>

σ

k by hypothesis, m2 cannot play the role of either

σ

k−1 in an

occur-rence of

σ

orof 3 in anoccurrenceof 132.Thusm2

remains atthebottomofthe

(

132

,

σ

)

-stack untilthe endofthesortingprocedure.Thethesisfollowsby it-eratingthesameargumentoneachblockBi,fori

≥

2. 2. Suppose that

π

is

(

132

,

σ

)

-sortable. Assume, for a contradiction, that B

˜

i is not decreasing, for some i. Then therearetwoconsecutiveelements x

<

y inB

˜

i. Therefore,bywhatprovedabove,out132,σ

₍

_π

₎

_contains an occurrence xymt of 231, which is impossibledue toProposition1.Finally,supposethatx

<

y,forx

∈

Bi and y

∈

Bi+1. Then xymt is an occurrenceof 231 in out132,σ

₍

_π

₎

_{,acontradiction.}

_

Theorem 1 and Proposition 2 guarantee that if

π

=

m1B1

· · ·

mtBt isthe ltr-mindecompositionofa

(

132

,

231

)

-sortable permutation

π

, then (with the notation above)

˜

Bi

=

out12

(

Bi

)

,foreachi.However,thisistrueevenwhen thesortabilityrequirementisrelaxed.

Lemma1.Let

π

=

m1B1

· · ·

mtBtbetheltr-mindecomposition ofapermutation

π

.Writeout132,231

₍

_π

₎

_{= ˜}

_B

1

· · · ˜

Btmt

· · ·

m1 asinTheorem1.ThenB

˜

i

=

out12

(

Bi

)

,foreachi.

Proof. Considertheinstantimmediatelyaftermiispushed

intothe

(

132

,

231

)

-stackandthenon-empty block Bi has tobeprocessed,forsomei.ByTheorem1,atthispointthe

(

132

,

231

)

-stack contains mi

,

mi−1

,

. . . ,

m1, reading from

top tobottom.Wewanttoshowthat thebehaviorofthe

(

132

,

231

)

-stackon Bi isequivalent tothebehavior ofan empty12-stackoninput Bi.Weprovethatthe

(

132

,

231

)

-stack performs the pop operation of some x

∈

Bi if and only ifthe 12-stackdoes thesame. Ifeitherthe next el-ement ofthe input ismi+1 orx is the last elementof

π

to be processed, then both the

(

132

,

231

)

-stack and the 12-stack perform a pop operation, as desired. Otherwise, supposethenextelementoftheinputis y,forsome y in thesameblock Bi,andthe

(

132

,

231

)

-stackpops the ele-mentx

∈

Bi.Thismeansthatthe

(

132

,

231

)

-stackcontains two elements z

,

w,withz above w,such that yzw isan occurrence of either 132 or231. Note that, since z

>

w, z isnot a ltr-minimum. Therefore yz is an occurrenceof 12 andthe12-stackperformsapopoperation,asdesired. Conversely,supposethatthe12-stackpopstheelementx, with y

∈

Bi the next element of the input. This implies that the 12-stack contains an element z such that z

>

y.

Thereforeyzmiisanoccurrenceof231 andthe

(

132

,

231

)

-stackperformsapopoperation,asdesired.



Corollary1.Let

π

=

m1B1

· · ·

mtBtbetheltr-min decomposi-tionofapermutation

π

.Thenthefollowingareequivalent.

1. Biavoids213 andBi

>

Bi+1,foreachi. 2.

π

is

(

132

,

231

)

-sortable.

3.

π

∈ Av(

1324

,

2314

)

.

Proof. Combiningthe firstpoint in Theorem 1and

Lem-ma1wehave:

out132,231

(

π

)

=

out12

(

B1

)

· · ·

out12

(

Bt

)

mt

· · ·

m1

.

We will use this decomposition of out132,231

₍

_π

₎

throughouttherestoftheproof.

[1

⇒

2] Suppose, for a contradiction, that out132,231

₍

_π

₎

contains anoccurrencebca of231.Notethat,since c

>

a, while mt

<

· · · <

m1, c is not a ltr-minimum of

π

(and

thusneitherisb).Now,ifb andc areinthesameblockBj, thenout12

₍

_B

j

)

isnotdecreasing.Thus,byProposition2,Bj contains213,whichisacontradiction.Otherwise,ifb

∈

Bj andc

∈

Bk,with j

<

k,then wehavea contradictionwith thehypothesis Bi

>

Bi+1 foreachi.

[2

⇒

3] Suppose, for a contradiction, that

π

∈ Av(

/

1324

,

2314

)

.First, suppose that

π

contains an occurrenceacbd of1324.Observethatb

,

c

,

d arenotltr-minimaof

π

.Now, ifb andd areinthesameblock Bj of

π

,forsome j,then Bj containsanoccurrencecbd of213.Thereforeout12

(

Bj

)

containsanoccurrenceof231 duetoProposition2,which contradictsthehypothesis.Otherwise,ifb

∈

Bjandd

∈

Bk, forsome j

<

k, thenout132,231

₍

_π

₎

_{contains anoccurrence} bdmk of231,againa contradiction. Thepattern2314 can beaddressedanalogously,soweleaveittothereader. [3

⇒

1] Let

π

∈ Av(

1324

,

2314

)

.If Bi contains an occur-rencebac of213,then

π

containsan occurrencemibac of 1324,whichisimpossible.Otherwise,if

π

containstwo el-ementsx

∈

Bj, y

∈

Bk,withx

<

y and j

<

k,thenmjxmky isanoccurrenceof2314,contradictingthehypothesis.



Theenumerationof

Av

(

1324

,

2314

)

(or asymmetryof thesepatterns) can be found for instance in [2,16]. Note thatin [1],theauthorsprovideaconstructivebijection be-tweenthesepermutationsandSchröderpaths.

Corollary2.Permutations oflengthn in Sort

(

132

,

231

)

are enumeratedbythelargeSchrödernumbers(sequence

A006318

in [15]).

4. The

(

σ

,

σ

ˆ

)

-machine

Forapermutation

σ

oflengthtwoormore,denoteby

ˆ

σ

thepermutation obtained from

σ

by interchanging its firsttwoentries.Letusregard a

(

σ

,

τ

)

-stackasan opera-tor outσ,τ

_{: S}

_{→ S}

_{.By convenientlymodifying the proof} of Corollary 4.5 in [9] (stated in the context of Cayley permutations), we have that outσ,τ is a length preserv-ing bijection on

S

if andonly if

τ

= ˆ

σ

. More generally, Berlow [5] showed that foraset T ofpatterns, outT _isa

lengthpreservingbijectionon

S

ifandonlyifT isclosed under the

ˆ

operator. In order for the paper to be self-contained,weshallgivethefollowingresult,whichis eas-ier to prove (although weaker): outσ,_{σ is}ˆ _{a bijection for}

any pattern

σ

. An immediateconsequence will be Theo-rem2below.

LetN∗bethesetoffinitelengthintegersequences.The actionofthe

(

σ

,

τ

)

-stackoninput

π

canbenaturally rep-resentedasasequenceoftriples

(

r

;

s

;

t

)

∈ (

N∗

)

3,wherer isthecurrentcontentoftheoutput,s is thecurrent con-tent of the

(

σ

,

τ

)

-stack (read fromtop to bottom) andt is the current content of the input. The triple

(

r

;

s

;

t

)

is saidtobea stateofpassing of

π

throughthe

(

σ

,

τ

)

-stack. Clearly,r isaprefixofoutσ,τ

₍

_π

₎

_{,t isasuffixof}

_π

_,the ini-tialstateis

(λ

;

λ

;

π

)

andthefinaloneis

(

outσ,τ

(

π

)

;

λ

;

λ)

, where

λ

istheemptysequence.Moreoveranon-finalstate

(

p1p2

· · ·

pa;s1s2

· · ·

sb;t1t2

· · ·

tc

)

isfollowedby eitherthe state

(

p1p2

· · ·

pas1

;

s2

· · ·

sb

;

t1t2

· · ·

tc

),

ifapopoperationisperformednext,or

(

p1p2

· · ·

pa

;

t1s1s2

· · ·

sb

;

t2

· · ·

tc

),

ifapushoperationisperformednext.

For p

=

p1

· · ·

pn

∈ N

n, we denote by pr the reverse of p, that is pr

=

pn

· · ·

p1. We wish to show that the

behavior of the

(

σ

,

σ

ˆ

)

-stack on

π

is strictly related to its behavior on



outσ,σˆ

(

π

)



r

.More precisely, ifo1

· · ·

o2n

is the sequence ofpush/pop operationsperformed when

π

is passed through a

(

σ

,

σ

ˆ

)

-stack, then o _2n

· · ·

o ₁ is

the sequence of push/pop operations performed when



outσ,σˆ

₍

_π

₎



r_{ispassedthroughthe}

₍

_σ

_,

_σ

_ˆ

₎

_{-stack,whereo}

i isa push(resp.pop) operation ifoi isapop (resp.push) operation. This can be equivalently expressed by saying that thestate

(

p

;

s

;

t

)

isfollowedby

(

u

;

v

;

w

)

ifandonly ifthestate

(

wr

;

v

;

ur

)

isfollowedby

(

tr

;

s

;

pr

)

.

Lemma2.Considertheactionofthe

(

σ

,

σ

ˆ

)

-stack.Letp

,

s

,

t

∈

N

∗andx

∈ N

.

1. Ifthestate

(

p

,

xs

,

t

)

isfollowedbythestate

(

px

,

s

,

t

)

(and thusapopoperationisperformed)thenthestate

(

tr

,

s

,

xpr

)

isfollowedbythestate

(

tr

_,

_xs

_,

_pr

₎

_{(andthusapush} opera-tionisperformed).

2. If the state

(

p

,

s

,

xt

)

is followed by the state

(

p

,

xs

,

t

)

(andthusapushoperationis performed),thenthestate

(

tr

_,

_xs

_,

_pr

₎

_{isfollowedbythestate}

₍

_tr_x

_,

_s

_,

_pr

₎

_(andthusa popoperationisperformed).

Proof. 1. Since xs is the content ofthe

(

σ

,

σ

ˆ

)

-stack in the state

(

p

,

xs

,

t

)

, we have that xs avoids

σ

and

σ

ˆ

. Thusapushoperationisperformedifs isthecontent of the

(

σ

,

σ

ˆ

)

-stack and x isthe next element of the input.

2. If p isempty,thestatementholds.Otherwise,let p

=

p1

· · ·

pa and s

=

s1

· · ·

sb.Observe that pa is the last elementthathasbeenextractedfromthe

(

σ

,

σ

ˆ

)

-stack

before x enters. Therefore, when pa is extracted, pa playstheroleofeither

σ

2inanoccurrenceof

σ

orof

ˆ

σ

2 in an occurrenceof

σ

ˆ

. More precisely,one of the

followingfourcaseshold.Weshowthedetailsforthe first caseonly, the othersbeing similar. Let z be the lengthof

σ

.

•

spasi3

· · ·

siz is an occurrenceof

σ

,forsome



≥

1 and



<

i3

<

· · · <

iz. Then passi3

· · ·

siz is an oc-currenceof

σ

ˆ

andthereforeapopoperationis per-formed when pa is the next element of the input andxs isthecontentofthe

(

σ

,

σ

ˆ

)

-stack,asdesired.

•

spasi3

· · ·

siz is an occurrenceof

σ

ˆ

,forsome



≥

1

and



<

i3

<

· · · <

iz.

•

xpasi3

· · ·

siz is an occurrence of

σ

, for some i3

<

· · · <

iz.

•

xpasi3

· · ·

siz is an occurrence of

σ

ˆ

, for some i3

<

· · · <

iz.



Astraightforward consequence ofthe previous lemma is that the map



outσ,σˆ



r

_{: S}

_{→ S}

_{is its own inverse,} and thus a bijection. More specifically, for any permuta-tion

π

,wehave



outσ,σˆ



−1

(

π

)

=



outσ,σˆ

(

π

r

₎



r_.Since

_π

is

(

σ

,

σ

ˆ

)

-sortableifandonlyifoutσ,σˆ

₍

_π

₎

_{avoids231 (and} thereversemapisbijective),wehavethatSort

(

σ

,

σ

ˆ

)

isin bijectionwith

Av

(

231

)

.Thenexttheoremfollows.

Theorem2.Foranypattern

σ

,outnσ,σˆ isabijection on

Sn

. Moreover,wehave

|

Sortn

(

123

,

213

)

| = |

Sortn

(

132

,

312

)

|

= |

Sortn

(

231

,

321

)

| =

cn

,

thenthCatalannumber.

5. Pair

(

123

,

132

)

We characterize Sort

(

123

,

132

)

in terms of pattern avoidance.Thenweshow that

(

123

,

132

)

-sortable permu-tationsareenumeratedbytheCatalannumbersby exhibit-ingalinkwiththeverywellstudiedCatalantriangle.

Theorem3.Apermutation

π

is

(

123

,

132

)

-sortableifandonly if

π

avoids2314,3214,4213 and

[

24¯13.

Proof. Supposethat

π

is

(

123

,

132

)

-sortable.Fora contra-diction, suppose that

π

contains

τ

∈ {

2314

,

3214

,

4213

}

. Pick an occurrence

π

i

π

j

π

k

π

 of

τ

, with i

<

j

<

k

< 

,

where



ischosenminimal,andk, j,andi arechosen max-imal,inthisorder.

If

τ

=

2314,due to our choice ofi

,

j

,

k

,



,we have

π

i

<

π

u

<

π

j, for k

<

u

< 

. Now, when

π

k is pushed in the

(

123

,

132

)

-stack, at least one of

π

i and

π

j has already beenextracted:otherwisethe

(

123

,

132

)

-stackwould con-tainanoccurrenceof132,whichisforbidden.Foreachu, k

+

1

≤

u

≤ 

,wehave

π

k

<

π

u andwhen

π

u ispushedin the

(

123

,

132

)

-stack,

π

kisstillinthe

(

123

,

132

)

-stack. In-deed,

π

u

π

x

π

y cannotbean occurrenceof123 norof132 with

π

x above

π

y,bothinthetailofthe

(

123

,

132

)

-stack

beginningby

π

k.If

π

i(resp.

π

j)isextractedbefore

π

k en-tersinthe

(

123

,

132

)

-stack,then

π

i

π

k+1

π

k (resp.

π

j

π



π

k) createsapattern231 inout123,132

₍

_π

₎

_{,acontradiction.}

If

τ

=

3214, dueto our choice of i

,

j

,

k

,



, we have

π

i

>

π

u

>

π

j, for k

<

u

< 

; and

π

u

<

π

u+1, for k

≤

u

< 

.

As above, when

π

k is pushed in the

(

123

,

132

)

-stack, at least one of

π

i and

π

j has already been extracted: oth-erwise the

(

123

,

132

)

-stack would contain an occurrence of 123. Since

π

k+1

>

π

k, the next step pushes

π

k+1 in

the

(

123

,

132

)

-stack. (i)Assumethat

π

i and

π

j bothhad left the

(

123

,

132

)

-stack. Then

π

k is just below

π

k+1 in

the

(

123

,

132

)

-stack,and

π

k

<

π

j

<

π

k+1.Thisimpliesthat

π

j

π

k+1

π

k isanoccurrenceof231 in out123,132

(

π

)

,a con-tradiction. (ii) Assume that

π

i is still in the

(

123

,

132

)

-stackand

π

jhadleftthisstack.Again,

π

j

π

k+1

π

kisan oc-currence of231 inout123,132

₍

_π

₎

_{,a contradiction.(iii)}

As-sumethat

π

jisstillinthe

(

123

,

132

)

-stackand

π

ihadleft thisstack.Since

π

u

<

π

u+1fork

≤

u

≤ 

−

1,thenextsteps

oftheprocesspushsuccessivelyallentries

π

k+1

,

. . . ,

π

in

the

(

123

,

132

)

-stack.Asabove,

π

i

π



π

k isanoccurrenceof 231 inout123,132

(

π

)

,againacontradiction.

Thecase

τ

=

4213 canbetreatedsimilarly.

Finally, suppose that

π

contains

[

24¯13. Equivalently, thereare twoindicesi

<

j suchthat

π

1

π

i

π

j isan occur-renceof132 and

π

k

>

π

1foreachi

<

k

<

j.Observethat,

by choosing j minimalandi maximal(in thisorder), we canassume j

=

i

+

1.Now,if

π

i isstillinthe

(

123

,

132

)

-stack when

π

i+1 enters, then out123,132

(

π

)

contains an

occurrence

π

i+1

π

i

π

1 of 231,which is impossibledue to

thesortability of

π

.Therefore

π

i isextractedbefore

π

i+1

enters. Thismeansthat thereare twoelements

π

u

,

π

v in the

(

123

,

132

)

-stack, withu

<

v (and thus

π

v above

π

u), suchthat

π

i+1

π

v

π

u isanoccurrenceofeither123 or132. Chooseu

,

v minimalamongstthoseindices,2 _sothat

_π

u is still inthe

(

123

,

132

)

-stackwhen

π

i+1 enters.Notice that

π

i+1

<

π

u (andthusu

=

1).Moreover,itmustbe

π

u

<

π

i, otherwise

π

i

π

u

π

1 wouldbe an occurrenceof 231 in the

(

123

,

132

)

-stack,whichisforbidden.Butthen

π

i+1

π

u

π

1is

anoccurrenceof231 inout123,132

₍

_π

₎

_{,acontradiction.}

Conversely, suppose that

π

is not

(

123

,

132

)

-sortable. Weshallprovethat

π

containsatleastoneofthepatterns 3214, 2314, 4213 or

[

24¯13. By hypothesis out123,132

₍

_π

₎

contains anoccurrencebca of231.Letb

=

π

j andc

=

π

k, forsomeindices j

,

k.Wedistinguishtwo cases,according whether j

<

k or j

>

k.

•

Supposethat j

<

k and thus

π

j isextractedfromthe

(

123

,

132

)

-stackbefore

π

k enters.Thenthereare two elements

π

u

,

π

v in the

(

123

,

132

)

-stack, with u

<

v (and thus

π

v above

π

u), such that

π

z

π

v

π

u is an oc-currence of either 123 or 132, where

π

z is the next element of the input. Notice that

π

j

≥

min

{

π

u

,

π

v}, since otherwise

π

j

π

v

π

u would be an occurrence of either 123 or 132 in the

(

123

,

132

)

-stack, which is impossible. Thus

π

k

>

π

j

>

π

z. If

π

z

π

v

π

u is an oc-currence of 123, then

π

u

π

v

π

z

π

k isan occurrenceof

2 _{In other words, pick the deepest such elements πu,πv in the}

(123,132)-stack.

either4213,if

π

u

>

π

k,or3214,if

π

u

<

π

k.Finally,if

π

z

π

v

π

u isanoccurrenceof132,then

π

u

π

j

π

z

π

kisan occurrenceof2314.

•

Suppose instead that j

>

k and thus

π

k is still in the

(

123

,

132

)

-stack when

π

j enters. Observe that k

=

1, since

π

1 is the last element of out123,132

(

π

)

.

Therefore, when

π

j enters the

(

123

,

132

)

-stack, the

(

123

,

132

)

-stackcontains theelements

π

j

π

k

π

1,

read-ingfromtoptobottom.Noticethat

π

j

>

π

1,otherwise

π

j

π

k

π

1 wouldrealizean occurrenceoftheforbidden

132 insidethe

(

123

,

132

)

-stack.Moreover,foreach en-try

π

t, with k

<

t

<

j, we have

π

t

>

π

1. Otherwise

π

t

π

k

π

1 wouldbeanoccurrenceof132 and

π

k would beextractedbefore

π

j,whichisimpossibleduetoour assumptions.Thus

π

1

π

k

π

j isanoccurrenceof

[

24¯13. Thiscompletestheproof.



Proposition3.ThedistributionofthefirstelementinSort

(

123

,

132

)

is given by the Catalan triangle (sequence

A009766

in [15]).

Proof. Let An

(

k

)

be the set of

(

123

,

132

)

-sortable per-mutations of length n and starting with k. Let A1

n

(

k

)

be thesubset of An

(

k

)

consistingofthosepermutations

π

=

π

1

π

2

. . .

π

n where any occurrence

π

1

π

i

π

 of

[

231 with

π



=

π

1

−

1 canbeextendedintoanoccurrence

π

1

π

i

π

j

π



of

[

3412.Set A2

n

(

k

)

=

An

(

k

)

\

An1

(

k

)

andletk

≥

2.We shall providebijections

α

:

A1

n

(

k

)

→

An

(

k

−

1

)

and

β

:

An2

(

k

)

→

An−1

(

k

)

.

Define

α

:

A_n1

(

k

)

→

An

(

k

−

1

)

by

α

(

π

)

=

π

, where

π

is obtainedfrom

π

by swapping thetwo entries

π

1 and

π

1

−

1 in

π

.Since

π

∈

A1n

(

k

)

, itis easyto check that

π

avoids

[

2413.

¯

In addition, swapping

π

1 and

π

1

−

1 does

notaffecttheavoidanceofthethreepatterns3214,2314, 4213,whichimplies(see Theorem 3) that

α

(

π

)

∈

An

(

k

−

1

)

.

Nextdefine

β

:

A2

n

(

k

)

→

An−1

(

k

)

by

β(

π

)

=

π

,where

π

isobtainedfrom

π

by deletingtheentry

π



immedi-atelybeforek

−

1 andby decreasingby oneall entriesof

π

greaterthan

π

.Noticethat

β(

π

)

∈

An−1

(

k

)

.Letusnow

sketchtheproofthat

β

isbijective,leavingsometechnical detailstothereader.Weshallexplicitlydefinetheinverse map of

β

. Given

π

∈

An−1

(

k

)

,choose aninteger



as

fol-lows:

• 

is the minimal entryl

=

π

u

>

π

1, with 1

<

u

<

i,

such that there isan index v with

π

v

<

π

i andu

<

v

<

i,ifsuchentryexists.

•

Otherwise,set



=

n.

Thepreimage

π

isobtainedbyinserting



immediately be-fore

π

i

=

k

−

1 andthen increasingbyone alltheentries

π

j of

π

with

π

j

≥ 

.

Finally,settingak_n

= |

An

(

k

)

|

,we have that akn

=

akn−1

+

ak

n−1,for2

≤

k

≤

n.Since An

(

1

)

= {

123

· · ·

n

}

and An

(

n

)

is

the setof length n permutationsavoiding 213 and start-ing withn, theinitial conditionsare givenbya1_n

=

1 and ann

=

cn−1,wherecn isthenthCatalannumber.Therefore, ak

n generatesthewell-knownCatalantriangle(see Table1 and [6,11,14]).



Table 1

TheCatalantriangleak

n= |An(k)|,with1≤n≤8 and1≤k≤6. k\n 1 2 3 4 5 6 7 8 1 1 1 1 1 1 1 1 1 2 1 2 3 4 5 6 7 3 2 5 9 14 20 27 4 5 14 28 48 75 5 14 42 90 165 6 42 132 297 . . . . . . . . .  1 2 5 14 42 132 429 1430

Corollary 3.Permutations oflengthn in Sort

(

123

,

132

)

are enumeratedbytheCatalannumbers.

Proof. With the previous notations we have

|

Sortn

(

123

,

132

)

|

=

n

_k=1a_nk

=

cn, thenthCatalan number(see again [6,11,14]).



6. Pair

(

123

,

312

)

Westartbygivingaltr-maxcounterpartofTheorem1.

Theorem4.Considerthe

(

312

,

σ

)

-machine,where

σ

=

σ

1

· · ·

σ

k−1

σ

k

∈ Sk

,withk

≥

3 and

σ

k−1

<

σ

k.Givenapermutation

π

oflengthn,let

π

=

M1B1

· · ·

MtBt beitsltr-max decompo-sition.Then:

1. Everytimealtr-maximumMiispushedintothe

(

312

,

σ

)

-stack,the

(

312

,

σ

)

-stackcontainstheelementsMi

,

Mi−1

,

. . . ,

M2

,

M1,reading from top to bottom.Moreover, we have

out312,σ

(

π

)

= ˜

B1

· · · ˜

BtMt

· · ·

M1

,

whereB

˜

iisarearrangementofBi.

2. If

π

is

(

312

,

σ

)

-sortable,thenM1

,

M2

,

. . . ,

Mt

=

n

−

t

+

1

,

n

−

t

+

2

,

. . . ,

n.

Proof. 1. Theproof isidenticaltothat ofthefirstpartof

Theorem1.

2.If

π

is

(

312

,

σ

)

-sortable,thenout312,σ

(

π

)

avoids231 by Proposition 1. Suppose, fora contradiction, that there is an element j

∈ {

n

−

t

+

1

,

. . . ,

n

}

which is not a ltr-maximum.Note that j

=

π

1

=

M1 and j

=

n

=

Mt. Then,

out312,σ

₍

_π

₎

_{containsanoccurrence jnM}

1 of231,whichis

acontradiction.



Instantiating

σ

by123 intheprevioustheoremwehave thenextresult.

Theorem5.Let

π

bea

(

123

,

312

)

-sortablepermutationand let

π

=

M1B1

· · ·

MtBtbeitsltr-maxdecomposition.Then:

1. Biavoids213 foreachi. 2. B

˜

i

=

out12

(

Bi

)

,foreachi.

Proof. Let i

≥

2. Notice that, as a consequence of

The-orem 4, immediately after Mi has been pushed in the

(

123

,

312

)

-stack, this stack contains the elements Mi

· · ·

M2M1,reading fromtop to bottom. Moreover, these

ele-ments remainatthe bottomof the

(

123

,

312

)

-stackuntil theendofthesortingprocedure,sincetheyarethelast el-ementsofout123,312

₍

_π

₎

_{.Thisfactwillbeusedfortherest}

oftheproof.

1.Suppose,foracontradiction, that Bi contains an oc-currence of 213, for some i, andlet bac be such an oc-currence with a ‘minimal’, in the sense that there is no a

<

a whereba c isanoccurrenceof213 in Bi.Therefore, sinceabMiisanoccurrenceof123,b isextractedfromthe

(

123

,

312

)

-stackbeforea enters.Inaddition,whenc enters intothe

(

123

,

312

)

-stack,a isstillinthisstack.Indeed,no entryin Bi betweena and c together witha producesa forbidden pattern in the

(

123

,

312

)

-stack. It follows that out123,312

(

π

)

contains bca whichisanoccurrenceof231, yieldingacontradictionwiththesortabilityof

π

.

2.Letusconsidertheactionofthe

(

123

,

312

)

-stackon the block Bi. We wish to show that the behavior of the

(

123

,

312

)

-stack when processing Bi is equivalent to the behaviorofanempty12-stackoninputBi.Inotherwords, weprovethattherestrictionofthe

(

123

,

312

)

-stackis trig-gered ifandonly ifthe next element of theinput forms an occurrence of 12 together with some other element in the

(

123

,

312

)

-stack. Immediately after Mi has been pushed (i.e. before the first element of Bi is processed), the

(

123

,

312

)

-stack contains the elements Mi

· · ·

M2M1,

reading fromtop to bottom. Observe that Bi avoids 213 bywhatprovedabove,thereforethe

(

123

,

312

)

-stack can-notbetriggeredbyanoccurrenceof312 whenprocessing Bi. Suppose that the next element of the input x forms an occurrence xy of 12 with some y

∈

Bi. Then xyMi is an occurrence of 123 in the

(

123

,

312

)

-stack, and so thisstackbehavesasa12-stack.Conversely, supposethat the

(

123

,

312

)

-stackis triggered by an occurrenceof xyz of 123, where x is the next element of the input. Since Mi

>

Mi−1

>

· · · >

M1, necessarily y

∈

Bi. Thus xy is an occurrenceof12 thattriggersthe12-stack,aswanted.



Asaconsequenceofwhatprovedsofarinthissection, forany

(

123

,

312

)

-sortablepermutation

π

=

M1B1

· · ·

MtBt of length n, we have Bi

∈ Av(

213

)

and M1

,

. . . ,

Mt

=

n

−

t

+

1

,

. . . ,

n. Moreover, by Proposition 2, each B

˜

i in out123,312

₍

_π

₎

_{= ˜}

_B

1

· · · ˜

BtMt

· · ·

M1 isdecreasing.Therefore,

for any three elements x

,

y

,

z, with x

∈

Bi, y

∈

Bj and z

∈

Bk, with i

<

j

≤

k, xyz is not an occurrence of 231. Otherwise xyz would still be an occurrence of 231 in out123,312

₍

_π

₎

_{,contradicting the factthat}

_π

_is

₍

₁₂₃

_,

₃₁₂

₎

-sortable. From nowon, we saythat xyz is an occurrence of2

−

3

−

1 if z

<

x

<

y, withx

∈

Bi, y

∈

Bj andz

∈

Bk, withi

<

j

<

k.Similarly,when j

=

k,wesaythatxyz isan occurrenceof2

−

31.

Theorem6.Let

π

=

M1B1

· · ·

MtBtbetheltr-max decompo-sitionofapermutation

π

oflengthn.Writeout123,312

₍

_π

₎

₌

˜

B1

· · · ˜

BtMt

· · ·

M1 as in Theorem4. Then

π

is

(

123

,

312

)

-sortableifandonlyifthefollowingconditionsaresatisfied:

1. Mj

=

n

−

t

+

j,foreachj

=

1

,

. . . ,

t.

2. Biavoids213 foreachi (andthusB

˜

iisdecreasingforeach i).

3. out123,312

(

π

)

avoids2

−

3

−

1. 4. out123,312

₍

_π

₎

_avoids2

₋

_31.

Proof. If

π

is

(

123

,

312

)

-sortable,then

π

satisfiesall the above conditionsasaconsequenceofwhatproved before inthissection.Conversely,itiseasytocheckthatif

π

sat-isfiestheaboveconditions,thenout123,312

₍

_π

₎

_avoids231.

Thus

π

is

(

123

,

312

)

-sortable.



ReformulatingthethirdconditionofTheorem6we ob-tainthefollowinglemma,whoseeasyproofisomitted.

Lemma3.Let

π

=

M1B1

· · ·

MtBt betheltr-max decomposi-tion of the

(

123

,

312

)

-sortable permutation

π

. Write out123,312

₍

_π

₎

_{= ˜}

_B

1

· · · ˜

BtMt

· · ·

M1 as in Theorem 4. Then

out123,312

₍

_π

₎

_{avoids 2}

₋

_{31 ifand onlyif foreach x}

_∈

_B

i, y

∈

Bj,withi

<

j,wehave:

•

ify

>

x,thenBj

>

x.

•

Ify

<

x,thenBj

<

x.

In other words, Lemma 3 says that each block Bj of a

(

123

,

312

)

-sortable permutation

π

isboundedbetween two previous elements of

π

. The following result is ob-tainedbyrestatingthislemmaandTheorem6intermsof patternavoidance.

Theorem7.Apermutation

π

is

(

123

,

312

)

-sortableifandonly if

π

avoids thethree generalizedpatterns

[

132,

[

42531 and

[

42153.

Next we prove that

(

123

,

312

)

-sortable permutations areenumeratedbythebinomialtransformofCatalan num-bers. Weshallexploittheabove characterizationinterms of patternsin orderto provide a bijectionwith acertain setofpartialpermutations,whoseenumerationis straight-forward.

Recall from Section 2 that a partial permutation of n is an injection

π

: {

1

,

2

,

. . . ,

k

}

→ {

1

,

2

,

. . . ,

n

}

, for some 0

≤

k

≤

n.The partial permutation of lengthzero will be denoted by

λ

. Denote by

A

n the set of all partial per-mutations of n. For instance, we have

A

3

= {λ,

1

,

2

,

3

,

12

,

21

,

13

,

31

,

23

,

32

,

123

,

132, 213

,

231

,

312

,

321

}

. There is a naturalbijection betweenthe setof permutationsin

Sn

avoiding the pattern

[

132 and

A

n−1. Indeed, from a

length n permutation

π

avoiding

[

132, we associate the unique partial permutation

α

(

π

)

∈

A

n−1 defined as

fol-lows:

α

(

π

)

πi

=

i

−

1

,

for

π

i

<

π

1

.

In other words,

α

(

π

)

isobtained byrecording the in-dices(minusone)oftheelements

π

i

<

π

1,fromthe

small-esttothelargestone.Forinstance,if

π

=

52461783,then

α

(

π

)

=

4172.Notice that

α

(

π

)

= λ

ifandonlyif

π

1

=

1.

Let us now define two pattern containments on

A

n. Let a

=

a1a2

· · ·

am bea partialpermutation ofn, withm

≤

n, andleti

<

j

<

k.Thenaiajak isanoccurrenceofthe pat-tern31

|

2 ifitisanoccurrenceof312 suchthatatleastone

value ofthe interval

[

aj

,

ak] does not appearin a. More-over, we say that aiajak is an occurrence of the pattern 213 ifitisanoccurrenceof213 suchthatai

=

ak

−

1.3 By interpreting Theorem 7 in terms of partial permutations, weobtaineasily:

Theorem8.Apermutation

π

is

(

123

,

312

)

-sortableifandonly if

α

(

π

)

avoids31

|

2 and213.

Let

A

n

(

31

|

2

,

213

)

bethesetofpartialpermutationsof n avoidingthetwopatterns31

|

2 and213,and

A

n

(

213

)

be theset ofpartialpermutationsofn avoidingtheclassical pattern213.

Theorem 9.For any n

≥

1, there is a bijection

φ

between

A

n

(

31

|

2

,

213

)

and

A

n

(

213

)

.

Proof. Letusdefinerecursivelythemap

φ

from

A

n

(

31

|

2

,

213

)

to

A

n

(

213

)

. If

π

= λ

, then we set

φ (

π

)

= λ

. Oth-erwise,

π

has a unique decomposition of the form

π

=

Amin

(

π

)

B where A and B are disjoint partial permuta-tionsofn.Wedistinguishthreecases:

(i) IfatleastoneofA orB isempty,thenweset

φ (

π

)

=

φ (

A

)

min

(

π

)φ (

B

)

;

(ii) Ifboth A andB arenotemptyandmin

(

A

)

>

max

(

B

)

, then we set

φ (

π

)

= φ(

A

)

min

(

π

)φ (

B

)

. It is worth notingthatthehypothesisthat

π

avoids31

|

2 implies thatanyvaluex

∈ [

min

(

π

),

max

(

B

)

]

occursin B.

(iii) Suppose that both A and B are not empty and

min

(

A

)

<

max

(

B

)

. Since

π

avoids 213, there exists x

∈ [

min

(

A

),

max

(

B

)

]

such that x does not occur in

π

. We choose the smallest x with this property, so thatanyvalueoftheinterval

[

min

(

A

),

x

]

occursin A. Moreover, since

π

avoids31

|

2,itmustbe max

(

A

)

=

x

−

1.AnillustrationofthiscaseisdepictedinFig.1. Letr bethemaximumvalue of B thatislowerthan min

(

A

)

andconsider the string B obtained from B by decreasingby x

−

r

−

1 allentriesgreater than x. Similarly,let A beobtainedfrom A by increasingby max

(

B

)

−

x

+

1 allits entries. Obviously, A and B belong to

A

n

(

31

|

2

,

213

)

, whereas

π

=

A min

(

π

)

B contains31

|

2.Thenweset

φ (

π

)

= φ(

A

)

min

(

π

)φ (

B

)

(see againFig. 1foran illustrationofthismapping). Itisworthnotingthatthevaluer

+

1 doesnotoccur in both A and B , which implies that there exists y

∈ [

min

(

π

),

r

+

1

]

such that y does not occur in

φ (

B

)

.

Next we prove that

φ

is an injective map. We pro-ceedby induction on the length of partial permutations. Let

π

be a partial permutation. Due to the remarks at the end of (ii) and (iii), the image of

π

under

φ

satis-fying(ii) is apartial permutation

π

such that anyvalue x

∈ [

min

(

π

),

max

(φ (

B

))

]

occursin

φ (

B

)

,whichisnottrue for a permutation

π

satisfying (iii). Then, for two non-empty partial permutations

π

and

σ

in

A

n

(

31

|

2

,

213

)

,

3 _{Thisisanalogoustothenotionofbivincularpatternonclassical} per-mutations.