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πiCz−y−1(ez−1)xdzHereCisaHankelcontourwhichstartsat−∞,circlestheoriginandgoesbackto−∞subjectto|Imz|<2π.FlajoletandProdingerdonotconsiderthisproblemforStirlingnumbersofthefirstkindinthesamedetailalthoughtheydoestablishtheidentitySnk=s−k−n,wheresnk2denotestheStirlingnumberofthefirstkindusingtheirdefinitionofSyx.Thedefinitionofsyx
theygiveis
|syx|=y!
2πiC1logx1wy+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,
whereyx=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)
2y−x1+Oy1/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.ThenewcontourisC1C2C3C4C5inthecounterclockwisesense.WenowobservethatintheMoser-Wymananalysis[7]nandkcanbepositivereals.Werefertotheiranalysisleadingtotheirequation(4.3).NotethatStirling’sformulagivesanasymptoticexpansionforyxprovidedx,y−x→∞.Weobtainfromtheirequation(5.1)(aninstanceof(4.3),lettingx=mandy=ntheresult