Dyck路,Motzkin路和Schroder路上峰的计数

Dyck路,Motzkin路和Schroder路上峰的计数IntroductionIn combinatorial mathematics, the most interesting objects

Dyck,MotzkinSchroder 路路和路上峰的计数 Introduction Incombinatorialmathematics,themostinterestingobjects areoftenthosethathaveavisualrepresentationaswellas algebraicorcombinatorialproperties.Onesuchobjectisthepeak ofalatticepath,whichisapointonthepathwherethepathfirst reachesamaximumandthenbeginstodescend. Thereareseveraltypesoflatticepaths,includingDyckpaths, Motzkinpaths,andSchroderpaths,eachwiththeirownunique properties.Inthispaper,wewillexplorethecountingofpeakson thesethreetypesofpaths. DyckPaths ADyckpathisalatticepathoflength2n,consistingofn stepsupandnstepsdown,wherethepathnevergoesbelowthe horizontalaxis.DyckpathsarenamedafterWalthervonDyck, whointroducedtheminhisresearchongrouptheory. ApeakonaDyckpathisapointwherethepathreachesits maximumheight,andthenbeginstodescend.Thenumberof peaksonaDyckpathoflength2nisgivenbytheCatalannumber Cn.TheCatalannumbershavemanyinterestingpropertiesand ariseinvariousareasofmathematics,includingcombinatorics, algebra,geometry,andcomputerscience. TheCatalannumberscanbedefinedusingvarious combinatorialinterpretations,includingasthenumberofwaysto: -arrangenpairsofparenthesessothattheyareproperly nested -formaconvexpolygonofn+2sidesbyconnectingnpoints onacircle -partitionaconvexpolygonofn+2sidesintotrianglesusing non-crossingdiagonals MotzkinPaths AMotzkinpathisalatticepathconsistingofstepsup,down, andhorizontal,withnohorizontalstepafteradownstep.Motzkin