; TeX output 2001.05.11:2311 KE&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍ:9|&html: html:.MTcolor push Black color popZVg5PSfile=logo113.eps llx=0 lly=0 urx=99 ury=16 rwi=2880*
;N G cmbx12DycukzPathsWithNoPeaksAtHeightk8Gu 'XQ cmr12PraulPeartandWVen-JinWoan ;K`y
3
cmr10Departmen!tfofMathematics
Ho!wardfUniversity Weashington,fD.C.20059,USA_rEmailfaddresses:(html:color push cmyk 0 1 0 0pp@scs.ho!ward.edu color pop html:,'html:color push cmyk 0 1 0 0wwoan@howard.edu color pop html:T] r"V
3
cmbx10Abstract ':
3
cmti10AUDyckUppathoflength2b>
3
cmmi10nisapathintwo-spacefrom(0;10)to(2n;0)whichusesonlysteps(1;1)(north-epast)eand(1;1!",
3
cmsy10 1)(south-east).F)urther,uaDyckpathdoesnotgobelowthex-axis.AepeakonahDyckppathisanodethatisimmediatelyprecededbyanorth-eaststepandimmediatelyfol Flowedbyagsouth-epaststep.Agpeakisatheightk3ifitsyd-coordinateiskX?:LetGȮ2 cmmi8k#(x)bethegeneratingfunctionforLthenumbperofDyckpathsoflength2nwithnopeaksatheightkվwithk1:ItisknownthatGz|{Y cmr81(x)|isthegenerpatingfunctionfortheFinenumbers(sequencefhtml:color push cmyk 0 1 0 0A000957 color pop html:in[html:color push cmyk 0 1 0 06 color pop html:]).Inthispaper,wederivetherpecurrencev㍑\GȮk#(x)
=!01=ڟ㦉 p @E
1n xGȮk6K cmsy8 1 (x)ER;kb2;Gz1(x)=+Y2=ڟ㦉 p S
ʱ1n+2x+epe p m1 4xY":v
It*nisinterpestingtoseethatinthecasekb=
2wegetGz2(x)=1 {+xC ȁ(x),Pwherpe*nC(x)isthegenerpatingfunctionR4fortheubiquitousCatalannumbpers(fhtml:color push cmyk 0 1 0 0A000108 color pop html:).֏ThismeansthatthenumberofDyckpathsof=:length2n+2;=:n0;withnoppeaksatheight2istheCatalannumberczn H=K
[1 p ̟Kdn+1'!eu
3
cmex10 2nA?in&I!e-H:Wealsoprpovide'acombinatorialproofforthislastfactbyintroducingabijectionbetweenthesetofal FlDyckppathsoflength2nn+2withnopeaksatheight2andthesetofal FlDyckpathsoflength2n:ӍKeyworpds:Dyc!kfpaths,CatalannumbMer,FinenumbMer,generatingfunction.Rhtml: html:&N