Generating trees and the Catalan and Schroder numbers.pdf

《Generating trees and the Catalan and Schroder numbers.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、GENERATINGTREESANDTHECATALANANDSCHRODERNUMBERSJULIANWESTAbstract.Apermutation2Savoidsthesubpatternihasnosubse-nquencehavingallthesamepairwisecomparisonsas,andwewrite2S().nWepresentanewbijectiveproofofthewell-knownresultthatjS(123)j=njS(132)j=c,then-thCatalannumber.Ageneralizationtofo

2、rbiddenpat-nnternsoflength4givesanasymptoticformulaforthevexillarypermutations.WesettleaconjectureofShapiroandGetuthatjS(31422413)j=s,thenn;1Schrodernumber,andcharacterizethedeque-sortablepermutationsofKnuth,alsocountedbys.n;11.IntroductiontoforbiddensubsequencesnWeregardapermutation2Sasa

3、sequenceofnelements,=f(i)g.ni=1Wesaythatcontainsthe3-letterpattern231ithereisatriple1i

4、<(i).The(1)(2)(k)12kksubsequencef(i)gissaidtohavetype.(j)j=1Twosequences,oflengthnareevidentlyofthesametypeitheyhavethesamepairwisecomparisonsthroughout,namelyif(i)<(j)$(i)<(j).WedenotebyS()thesetofallpermutationsinSwhichavoid.IfR=nnTf:::g,weabbreviateS(R)=S(:::)=

5、S().Fundamental12qnn1qnjquestionsaretodeterminejS(R)jviewedasafunctionofn,andifjS(R)j=nn00jS(R)jtodiscoveranexplicitbijectionbetweenS(R)andS(R).nnnThemoststudiedcasehasbeentoforbidasinglepatternoflength3.Becauseofobvioussymmetryargumentsdescribedbelow,thereareonlytwodistinctcasestoenumerat

6、e,jS(123)jandjS(132)j.Ithappensthatthesetwofunctionsarenn2n1equal,jS(123)j=jS(132)j=c=.nnnn+1nHistorically,thesetwoenumerativeresultswereobtainedindependently[13],[10].TherstsatisfactorybijectionbetweenthetwocaseswaspresentedbyRodicaSimionandFrankSchmidt[20],andasecondwasgivenbyDanaRicha

7、rds[15].12JULIANWESTInsectiontwo,wepresentanewbijectiveproofthatjS(123)j=jS(132)j.nnThisproofhastheadvantagethattheenumerativeresultalsofollowsnatu-rally.Insectionthree,wegeneralizetheresultofsectiontwotoshowthatjS(1234)j=jS(1243)j=jS(2143)j.Permutations