Restricted Dumont permutations, Dyck paths and noncrossing p

Abstract. We complete the enumeration of Dumont permutations of the second kind avoiding a pattern of length 4 which is itself a Dumont permutation of the second kind. We also consider some combinatorial statistics on Dumont permutations avoiding certain p

RESTRICTEDDUMONTPERMUTATIONS,DYCKPATHS,AND

NONCROSSINGPARTITIONS

ALEXANDERBURSTEIN,SERGIELIZALDE,ANDTOUFIKMANSOUR

arXiv:math/0610234v1 [math.CO] 6 Oct 2006Abstract.WecompletetheenumerationofDumontpermutationsofthesecondkindavoidingapatternoflength4whichisitselfaDumontpermutationofthesecondkind.WealsoconsidersomecombinatorialstatisticsonDumontpermutationsavoidingcertainpatternsoflength3and4andgiveanaturalbijectionbetween3142-avoidingDumontpermutationsofthesecondkindandnoncrossingpartitionsthatusescycledecomposition,aswellasbijectionsbetween132-,231-and321-avoidingDumontpermutationsandDyckpaths.Finally,weenumerateDumontpermutationsofthe rstkindsimultaneouslyavoidingcertainpairsof4-letterpatternsandanotherpatternofarbitrarylength.1.PreliminariesThemaingoalofthispaperistogiveanaloguesofenumerativeresultsoncertainclassesofpermutationscharacterizedbypattern-avoidanceinthesymmetricgroupSn.InthesetofDumontpermutations(seebelow)weidentifyclassesofrestrictedDumontpermutationswithenumerativepropertiesanalogoustoresultsonpermutations.Moreprecisely,westudythenumberofDumontpermutationsoflength2navoidingeithera3-letterpatternora4-letterpattern.WealsogivedirectbijectionsbetweenequinumeroussetsofrestrictedDumontpermutationsoflength2nandotherobjectssuchasrestrictedpermutationsoflengthn,Dyckpathsofsemilengthn,ornoncrossingpartitionsof[n]={1,2...,n}.1.1.Patterns.Letσ∈Snandτ∈Skbetwopermutations.Wesaythatτoccursinσ,orσ∈Sncontainsτ,ifσhasasubsequence(σ(i1),...,σ(ik)),1≤i1<···<ik≤n,thatisorder-isomorphictoτ(inotherwords,foranyj1andj2,σ(ij1)≤σ(ij2)ifandonlyifτ(j1)≤τ(j2)).Suchasubsequenceiscalledanoccurrence(oraninstance)ofτinσ.Inthiscontext,thepermutationτiscalledapattern.Ifτdoesnotoccurinσ,wesaythatσavoidsτ,orisτ-avoiding.WedenotebySn(τ)thesetofpermutationsinSnavoidingapatternτ.IfTisasetofpatterns,thenSn(T)=∩τ∈TSn(τ),i.e.Sn(T)isthesetofpermutations

inSnavoidingallpatternsinT.

The rstresultsintheextensivebodyofresearchonpermutationsavoidinga3-letterpatternareduetoKnuth[9],buttheintensivestudyofpatternsinpermutationsbeganwithSimionandSchmidt[16]whoconsideredpermutationsandinvolutionsavoidingeachsetTof3-letterpatterns.OneofthemostfrequentlyconsideredproblemsistheenumerationofSn(τ)andSn(T)forvariouspatternsτandsetsofpatternsT.Theinventoryofcardinalitiesof|Sn(T)|forT S3isgivenin[16],andasimilarinventoryfor|Sn(τ1,τ2)|,whereτ1∈S3andτ2∈S4isgivenin[23].Someresultson|Sn(τ1,τ2)|forτ1,τ2∈S4areobtainedin

[22].Theexactformulafor|Sn(1234)|andthegeneratingfunctionfor|Sn(12...k)|

are

Abstract. We complete the enumeration of Dumont permutations of the second kind avoiding a pattern of length 4 which is itself a Dumont permutation of the second kind. We also consider some combinatorial statistics on Dumont permutations avoiding certain p

foundin[7].B´ona[2]hasfoundtheexactvalueof|Sn(1342)|=|Sn(1423)|,andStankova

[18,19]showedthat|Sn(3142)|=|Sn(1342)|.Forasurveyofresultsonpatternavoidance,see[1,8].

Anotherproblemis ndingequinumerouslyavoided(setsof)patterns,i.e.setsT1andT2suchthat|Sn(T1)|=|Sn(T2)|foranyn≥0.Such(setsof)patternsarecalledWilf-equivalentandsaidtobelongtothesameWilfclass.ThereareeightsymmetryoperationsonSnthatmapeverypatternontoaWilf-equivalentpattern,including:

reversalr:r(τ)(j)=τ(n+

complementrupside c=down.c r:c:rc (τc)((τj)()j=)n=+1 n1+ j),1τ (i.e.jτ),r(ni.e.(τ)+1cis( τ)τjisread),τi.e.readright-to-left.r upsidec(τ)isdown.τreadright-to-left

inversei:i(τ)=τ 1.

Thesetofpatterns r,c,i (τ)={τ,r(τ),c(τ),r(c(τ)),τ 1,r(τ 1),c(τ 1),r(c(τ 1))}iscalledthesymmetryclassofτ.

Sometimeswewillrepresentapermutationπ∈Snbyplacingdotsonann×nboard.Foreachi=1,...,n,wewillplaceadotwithabscissaiandordinateπ(i)(theoriginoftheboardisatthebottom-leftcorner).

1.2.Dumontpermutations.InthispaperweanswersomeoftheaboveproblemsinthecaseofDumontpermutations.ADumontpermutationofthe rstkindisapermutationπ∈S2nwhereeachevenentryisfollowedbyadescentandeachoddentryisfollowedbyanascentorendsthestring.Inotherwords,foreveryi=1,2,...,2n,

π(i)iseven= i<2nandπ(i)>π(i+1),

π(i)isodd= π(i)<π(i+1)ori=2n.

ADumontpermutationofthesecondkindisapermutationπ∈S2nwhereallentriesatevenpositionsarede cienciesandallentriesatoddpositionsare xedpointsorexcedances.Inotherwords,foreveryi=1,2,...,n,

π(2i)<2i,

π(2i 1)≥2i 1.

WedenotethesetofDumontpermutationsofthe rst(resp.second)kindoflength2nbyD12n(resp.D22n).Forexample,D1212{2143,3142,4132}.Wealson.de neDumontD1-Wilf-equivalence2=D2={21},DandD4={2143,3421,4213},D2-Wilf-equivalencesimilarly4=totheWilf-equivalenceonS[4]showedthat

|D12n|=|D22n|=G2n+2=2(1 22n+2)B2n+2,

whereGnisthenthGenocchinumber,amultipleoftheBernoullinumberBn.ListsofDumontpermutationsD12nandD22nforn≤4aswellassomebasicinformationandreferencesforGenocchinumbersandDumontpermutationsmaybeobtainedin[15]and[17,A001469].TheexponentialgeneratingfunctionsfortheunsignedandsignedGenocchinumbersareasfollows:

∞Gx2n

2n

n=12, ∞( 1)nGx2nx2nn=1ex+1 x= xtanh

Abstract. We complete the enumeration of Dumont permutations of the second kind avoiding a pattern of length 4 which is itself a Dumont permutation of the second kind. We also consider some combinatorial statistics on Dumont permutations avoiding certain p

SomecardinalitiesofsetsofrestrictedDumontpermutationsoflength2nparallelthoseofrestricted

permutations

oflengthn.Forexample,thefollowingresultswereobtainedin

[3,11]:

|D12n(τ)|=Cnforτ∈{132,231,312},whereCn=1

2n ,thenthCatalannumber,fo …… 此处隐藏：32791字，全部文档内容请下载后查看。喜欢就下载吧 ……