Alina F.Y. Zhao---A Combinatorial Proof of the Enumeration of Alternating Permutations with Given Peak Set.pdf

《Alina F.Y. Zhao---A Combinatorial Proof of the Enumeration of Alternating Permutations with Given Peak Set.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ACombinatorialProofoftheEnumerationofAlternatingPermutationswithGivenPeakSetAlinaF.Y.ZhaoSchoolofMathematicalScienceNanjingNormalUniversity,Nanjing210046,P.R.Chinaalinazhao@njnu.edu.cnAbstractUsingthecorrespondencebetweenacycleup-downpermutationandapairofmatch-ing

2、s,wegiveacombinatorialproofoftheenumerationofalternatingpermutationsac-cordingtothegivenpeakset.AMSSubjectClassification:05A05,05A19Keywords:alternatingpermutation,cycleup-downpermutation,matching1IntroductionLetSndenotethesymmetricgroupofallpermutationsof[n]:={1,2

3、,...,n}.Analternatingpermutationon[n]isdefinedtobeapermutationσ=σ1σ2···σn∈Snsatisfyingσ1>σ2<σ3>σ4<···,etc.,inanalternatingway.Similarly,σisreversealternatingifσ1<σ2>σ3<σ4>···,whichisalsoreferredasanup-downpermutation.DenotebyEnthesetofalternatingpermutationson[n],a

4、ndfurtherletEn=

5、En

6、.NotethatEniscalledEulernumber,andwasshownbyAndr´e[1,2]tosatisfyXxnEn=secx+tanx.n!n≥0arXiv:1204.1141v1[math.CO]5Apr2012Thereversemapσ7→σrdefinedbyσir=σn+1−ionSnshowsthatEnisalsothenumberofup-downpermutationsinSn.Recently,ElizaldeandDeutsch[4]intr

7、oducedtheconceptofcycleup-downpermutations.Acycleissaidtobeup-downif,whenwritteninstandardcycleform,say(a1,a2,a3,...),onehasa1a3···,andapermutationσisacycleup-downpermutationifitisaproductofup-downcycles.TheyprovebothbijectivelyandanalyticallythatPropositi

8、on1([4],Lemma2.2).Thenumberofcycleup-downpermutationsof[2k]allofwhosecyclesareevenisE2k.Foroutpurpose,letusbrieflyrecallthebijectionτdevelopedin[4]toprovetheaboveproposition.Givenσ=σ1σ2···σ2k∈E2k,letσi1>σi2>···>σimbeitslefttorightminima,thecorrespondingcycleup-down

9、permutationτ(σ)withonlyevencyclesisdefinedbyτ(σ)=(σi1,...,σi2−1)(σi2,...,σi3−1)···(σim,...,σ2k).1Theelementσi(1≤i≤n)iscalledapeakifσi−1<σi>σi+1,wherewesetσ0=0andσn+1=0,andthepeaksetofσaretheelementsofpeaksinσ.Forotherdefinitionsofpeakssee[5,6].Forn=2keven,andforanys

10、equence2≤i1

11、Sk(i1,i2,...,ik)

12、.Fo