Asymptotics of the average height of 2--watermelons with a w

We generalize the classical work of de Bruijn, Knuth and Rice (giving the asymptotics of the average height of Dyck paths of length $n$) to the case of $p$--watermelons with a wall (i.e., to a certain family of $p$ nonintersecting Dyck paths; simple Dyck p

ASYMPTOTICSOFTHEAVERAGEHEIGHTOF2–WATERMELONS

WITHAWALL.

MARKUSFULMEK

Abstract.WegeneralizetheclassicalworkofdeBruijn,KnuthandRice(givingtheasymptoticsoftheaverageheightofDyckpathsoflengthn)tothecaseofp–watermelonswithawall(i.e.,toacertainfamilyofpnonintersectingDyckpaths;simpleDyckpathsbeingthespecialcasep=1.)Weworkoutthisasymptoticsforthecasep=2only,sincethecomputationsinvolvedarealreadyquitecomplicated(butmightbeofsomeinterestintheirownright).

arXiv

:math/0607163v2 [math.CO] 4 Sep 2006

1.Introduction

ThemodelofviciouswalkerswasoriginallyintroducedbyFisher[9]andreceivedmuchinterest,sinceitleadstochallengingenumerativequestions.Here,weconsiderspecialcon gurationsofviciouswalkerscalledp–watermelonswithawall.

Brie ystated,ap–watermelonoflengthnisafamilyP1,...PpofpnonintersectinglatticepathsinZ2,where

Pistartsat(0,2i 2)andendsat(2n,2i 2),fori=1,...,p,

allthestepsaredirectednorth–eastorsouth–east,i.e.,leadfromlatticepoint(i,j)to(i+1,j+1)orto(i+1,j 1),

notwopathsPi,Pjhaveapointincommon(thisisthemeaningof“noninter-secting”).

Theheightofap–watermelonisthey–coordinateofthehighestlatticepointcontainedinanyofitspaths(sincethepathsarenonintersecting,itsu cestoconsiderthelatticepointscontainedinthehighestpathPp;seeFigure1foranillustration.)

Ap–watermelonoflengthnwithawallhastheadditionalpropertythatnoneofthepathsevergoesbelowtheliney=0(sincethepathsarenonintersecting,itsu cestoimposethisconditiononthelowestpathP1;seeFigure2foranillustration.).

In[2],BonichonandMosbahconsidered(amongstotherthings)theaverageheightH(n,p)ofp–watermelonsoflengthnwithawall,H(n,p)=

1

(1.67p 0.06)2n+o

Date:February2,2008.

ResearchsupportedbytheNationalResearchNetwork“AnalyticCombinatoricsandProbabilisticNumberTheory”,fundedbytheAustrianScienceFoundation.

1

√

We generalize the classical work of de Bruijn, Knuth and Rice (giving the asymptotics of the average height of Dyck paths of length $n$) to the case of $p$--watermelons with a wall (i.e., to a certain family of $p$ nonintersecting Dyck paths; simple Dyck p

2MARKUSFULMEK

Figure1.A6–watermelonoflength46andheight

20

20

Figure2.A3–watermelonwithawalloflength11andheight

12

Thepurposeofthispaperistoworkouttheexactasymptoticsforthesimplespecialcasep=2.ThiswillbedonebyimitatingtheclassicalreasoningofdeBruijn,KnuthandRice[5]forthecasep=1(i.e.,fortheaverageheightofDyckpaths).However,eventhecasep=2involvesrathercomplicatedcomputations.Inparticular,weshallneedinformationsaboutresiduesandevaluationsofadoubleDirichletseries,whichweshall(partly)obtainbyimitatingRiemann’srepresentationofthezetafunction[6,section1.12,(16)].

1.1.Notationalconventions.Fork,n∈Z,weshallusethenotationintroducedin[12]fortherisingandfallingfactorialpowers,i.e.

(n)

:=1,(n)

:=n·(n 1)···(n k+1)ifk>0.

:=0ifk<0,(n)0

Forthebinomialcoe cientweadopttheconvention

k

(n)nif0≤k≤n,k!:=k0else.

We generalize the classical work of de Bruijn, Knuth and Rice (giving the asymptotics of the average height of Dyck paths of length $n$) to the case of $p$--watermelons with a wall (i.e., to a certain family of $p$ nonintersecting Dyck paths; simple Dyck p

ASYMPTOTICSOFTHEAVERAGEHEIGHTOF2–WATERMELONSWITHAWALL.3

Moreover,weshalluseIverson’snotation:

1if“someassertion”istrue,

[someassertion]=

0else.

http://www.77cn.com.cnanizationofthematerialpresented.Thispaperisorganizedasfollows:

InSection2,wepresentexactenumerationformulasfortheaverageheightofp–watermelonswithawallintermsofcertaindeterminants.Moreover,wemaketheseformulasmoreexplicit(intermsofsumsofbinomialcoe cients)forthesimplecasesp=1andp=2.

InSection3,we rstreviewtheclassicalreasoningfortheasymptoticsoftheaverageheightof1–watermelonswithawall,whichwasgivenbydeBruijn,KnuthandRice[5].Thenweshowhowthisreasoningcanbemodi edforthecaseof2–watermelonswithawall.

InappendixA,wesummarizebackgroundinformationon

–Stirling’sapproximation,

–certainresiduesandvaluesofthegammaandzetafunction,–acertaindoubleDirichletseriesandJacobi’sthetafunctionwhichareneededinourpresentation.

1.3.Acknowledgements.IamverygratefultoProfessorKr¨atzelforpointingouttomehowthepolesandresiduesofcertainDirichletseriescanbeobtainedinasimplewaybyusingthereciprocitylawforJacobi’sthetafunction,andtoChristianKrattenthalerformanyhelpfuldiscussions.

2.Exactenumeration

Forastart,wegathersomeexactenumerationresults.

2.1.Thenumberofp–watermelonswithawall.Wehavethefollowinggeneral-izationoftheenumerationof1–watermelonswithawall(i.e.,Dyckpaths)oflengthn,whichisgivenbytheCatalannumbers

C(n)=

1

Proof.ThisisaspecialcaseofTheorem6in[13].

n+2j+1 .

n(2)

2.2.1–watermelonswithawallandheightrestrictions.Inordertoobtaintheaverageheight,wecountp–watermelonswithawalloflengthnwhichdonotexceedheighth.

Tothisend,weemploythefollowingformula(see[15,p.6,Theorem2]):

We generalize the classical work of de Bruijn, Knuth and Rice (giving the asymptotics of the average height of Dyck paths of length $n$) to the case of $p$--watermelons with a wall (i.e., to a certain family of $p$ nonintersecting Dyck paths; simple Dyck p

4MARKUSFULMEK

Theorem1.Letu,dbenonnegativeintegers,andletb,tbepositiveintegers,suchthat b<u d<t.Thenumberoflatticepathsfrom(0,0)to(u+d,u d),whichdonottouchneitherliney= bnorliney=t,equals

u+d u+d

.(3) …… 此处隐藏：17200字，全部文档内容请下载后查看。喜欢就下载吧 ……