Asymptotic Estimates for Generalized Stirling Numbers

  • 格式:pdf
  • 大小:139.79 KB
  • 文档页数:13

Centrum voor Wiskunde en InformaticaAsymptotic estimates for generalized Stirling numbersR. Chelluri, L.B. Richmond, N.M. TemmeModelling, Analysis and Simulation (MAS)MAS-R9923 September 30, 1999Report MAS-R9923ISSN 1386-3703

CWIP.O. Box 940791090 GB AmsterdamThe Netherlands

CWI is the National Research Institute for Mathematicsand Computer Science. CWI is part of the StichtingMathematisch Centrum (SMC), the Dutch foundationfor promotion of mathematics and computer scienceand their applications.SMC is sponsored by the Netherlands Organization forScientific Research (NWO). CWI is a member ofERCIM, the European Research Consortium forInformatics and Mathematics.Copyright © Stichting Mathematisch CentrumP.O. Box 94079, 1090 GB Amsterdam (NL)Kruislaan 413, 1098 SJ Amsterdam (NL)Telephone +31 20 592 9333Telefax +31 20 592 4199AsymptoticEstimatesforGeneralizedStirlingNumbersR.ChelluriDepartmentofMathematics,CornellUniversityIthaca,NewYork14850,U.S.A.

L.B.RichmondDepartmentofCombinatoricsandOptimization,UniversityofWaterlooWaterloo,Ontario,N2L3G1,Canada

N.M.TemmeCWIP.O.Box94079,1090GBAmsterdam,TheNetherlands

e-mail:tc39@cornell.edu,lbrichmo@watdragon.uwaterloo.ca,nicot@cwi.nl

ABSTRACTUniformasymptoticexpansionsaregivenfortheStirlingnumbersofthefirstkindforintegralargumentsandforthesecondkindasdefinedforrealargumentsbyFlajoletandProdinger.ThelogconcavityoftheresultingrealvaluedfunctionofFlajoletandProdingerisestablishedforarangeincludingtheclassicalintegraldomain.

1991MathematicsSubjectClassification:11B73,41A60.Keywords&Phrases:generalizedStirlingnumbers,asymptoticexpansions.Note:WorkcarriedoutunderprojectMAS1.3Partialdifferentialequationsinporousmediaresearch.ThisreporthasbeenacceptedforpublicationinAnalysis.

RecentlyFlajoletandProdinger[4]havegivenasolutiontotheproblemofGraham,KnuthandPatashnik[5]whichasksforagoodgeneralizationoftheStirlingnumbersofthesecondkind,denotedherebySnkforcomplexnumbersnandk.Theydefine(equation(2)of[4])

Syx=y!2πi󰀂Cz−y−1(ez−1)xdzHereCisaHankelcontourwhichstartsat−∞,circlestheoriginandgoesbackto−∞subjectto|Imz|<2π.FlajoletandProdingerdonotconsiderthisproblemforStirlingnumbersofthefirstkindinthesamedetailalthoughtheydoestablishtheidentitySnk=s−k−n,wheresnk2denotestheStirlingnumberofthefirstkindusingtheirdefinitionofSyx.Thedefinitionofsyx

theygiveis

|syx|=y!

2πi󰀂C1logx󰀇1wy+1,

whereC1isthe”raindropcontour”,theimageofCunderw=ez−1.ItisnaturaltoconsidertheabsolutevalueoftheStirlingnumbersofthefirstkindasMoser-Wyman[7]andTemme[11]havedonesincequestionsofsignareavoidedand|snk|isthenumberofpermutationsonnsymbolswithkcycles.Itisnaturalforus,followingtheseauthors,todefineforpositiverealxandy

syx=1Γ(u+1)du

nu0=1−e−u0.(Itiseasilyseenthatu/(1−e−u)isanincreasingfunction).Lett0=(y−x)/x,φ(u)=−ylogu+xlog(eu−1),andA=φ(u0)−xt0+(y−x)logt0.

Letf(t0)=(t0/(1+t0)(u0−t0))1/2.

(Wedefinet0,Aandf(t0)asTemme[11]does).Finallylet

2H0(u)=eu(eu−1)−1−ueu(eu−1)−2.3Theorem1.TherelationSyx∼eAxy−xf(t0)󰀇yx󰀊,

where󰀑yx󰀓=y!/x!(y−x)!holdsuniformlyasy→∞forδy−y1/3then

Syx=y!

2uy0

1

2y−xy2(y−x)

x!󰀕1+O󰀉(logy)−1/2󰀌󰀙.

If(logy)1/2syx=Γ(y+1+u1)

2󰀆y−x󰀉1+O󰀄y1/3󰀆󰀌.

Theorem3.ThefunctionSyxisalog-concavefunctionofxforδenough.

Remark1.Theorem3extendsthewell-knownresultsthatSnkislog-concaveasafunctionofthediscretevariablek.

Remark2.WedependveryheavilyupontheanalysisofMoser-Wyman[6,7].Weassumethereaderhasacopyofthesepapersinhand.ThefirststatementinTheorem1andinTheorem2isfoundinTemme[11].ThesubsequentstatementsineachTheoremarederivedfirstfollowingMoserandWyman.Thefirststatementsarethenshowntofollow.Inour4approachmostoftheeffortcomesfromshowingthatTemme’sresultsareequivalenttotheMoser-Wymanresultsintheextremevaluesofxwithrespecttoy.SincetheMoser-WymanresultsareverysimplyexpressedthisseemsofvalueinitsownrighthoweverourmainpointisthatTemme’sformulaunifiestheresultsofMoser-Wyman.SeeSection3forfurtherdiscussion.

Remark3.ItseemsverylikelythatitisnotdifficulttoestablishTheorem2forrealxandyusingourdefinitionofsyxandaTheorem3forsyxusingtheFlajolet-Prodingerdefinitionofsyx.Itwouldbemoreworktoestablishbothresultsusingonlyonedefinition.

2.1.ProofofTheorem1Letu0bedefinedasinTheorem1.AsignificantdifferencewiththeMoser-Wymananalysisariseshere.Thepointskπiarejustzerosoftheintegrandwhenxisanintegerandacontourcanbemovedthroughthemwithnodifficulty.Whenxisnotanintegerweavoiddoingso.WedeformthecontourCtothefollowingcontour:LetC1bethestraightlineIm(z)=−2π+δ,0isasmallpositivenumber.WeletC2bethestraightlineRe(z)=ǫ,goingfromǫ+i(δ−2π)tothecircle|z|=u0,C5andC4bethereflectionsintherealaxisofC1andC2respectively.WeletC3betheportionofthecircle|z|=u0,meetingC2andC4.ThenewcontourisC1󰀍C2󰀍C3󰀍C4󰀍C5inthecounterclockwisesense.WenowobservethatintheMoser-Wymananalysis[7]nandkcanbepositivereals.Werefertotheiranalysisleadingtotheirequation(4.3).NotethatStirling’sformulagivesanasymptoticexpansionfor󰀑yx󰀓providedx,y−x→∞.Weobtainfromtheirequation(5.1)(aninstanceof(4.3),lettingx=mandy=ntheresult