您好，欢迎访问三七文档
AknowledgementsWewishtothanktheanonymousrefereewhosecommentshelpedusinimprovingthecon tentsandreadibilityofourpaper References E A Bender Asymptoticmethodsinenumeration SIAMReview W Feller Anintroductiontoprobabilitytheoryanditsapplications Wiley I M Gessel AfactorizationforformalLaurentseriesandlatticepathenumeration JournalofCombinatorialTheory SeriesA J R Goldman Formallanguagesandenumeration JournalofCombinatorialTheory SeriesA J R GoldmanandT Sundquist Latticepathenumerationbyformalschema Advancesinappliedmathematics J Labelle LanguagesdeDyckg en eralis es Ann Sci Math Qu ebec A I Markushevich Theoryoffunctionsofacomplexvariable Prentice Hall D Merlini D G Rogers R Sprugnoli andM C Verri Onsomealternativecharac terizationsofRiordanarrays CanadianJournalofMathematics G N Raney Functionalcompositionpatternsandpowerseriesreversion Trans Amer Math Soc M P Sch utzenberger Context freelanguageandpushdownautomata InformationandControl R Sprugnoli Riordanarraysandcombinatorialsums DiscreteMathematics R SprugnoliandM C Verri AsymptoticsforLagrangeinversion PureMathematicsandApplications dominatingsingularityt rofd t Byawell knownresult seeBender Theorem itfollowsthatdn k pk r tn d t Sincewealreadyknowtheasymptoticvalueof tn d t weonlyhavetocomputepk r foreveryk N Thisisnotdi cultandwecan ndaclosedformforpk r Lemma Theclosedformforthevalueofpk t computedatt ris pk r A k s k Bs k Cs k whereshasthesamevalueasbefore s sr r andA B CarethethreeconstantsA sr sr B sr sr sr s r C s r sr s r Proof Fromthelaststepinthederivationofdm t inLemma sproof wehave pk t pk t tpk t t qk t pk t tpk t t pk t wethereforeobtaintherecurrence pk r pk r rpk r r pk r whoseinitialconditionsarep r p r andp r r Ifwewritetherecurrencefork andexaminethegeneratingfunctionGfpk r g P t wehave pk r pk r rpk r r pk r P t t r t t P t tt rP t t r P t P t t rt r t Thedenominator srootscanbeeasilyfound theyaret t sandt sr r s Apartialfractionexpansionnowgivesus P t A t s B t s C t s andwecanimmediatelyderivetheclosedformfromit Thankstoallthepreviousresults wecanconcludewiththeasymptoticformulaforthegenericelementdn k i e thenumberoflatticepathsarrivingatthepoint n n k Theorem Theasymptoticvalueofdn k tn dk t is dn k A k B s k Cs k dn Ak np n sk rn Proof Theproofisimmediatefromthetwolemmasaboveandfromthepreviously mentionedtheorembyBender Itisnotdi cult butverylaborious to ndoutthatthisformulaisatrueapproximationwhenk o pn and therefore wehavethefollowingasymptoticapproximation dn a n a n a n r n Themaintermofthisexpressioncannowbefoundbyapplyingthewell knownasymptoticformulafor n dn s np nrn Letusnowgoontodn k tn dk t wheredk t isgivenbytherecurrenceintheformulasusedinExample Theinitialconditionsared t d t andd t td t d t d t t d t bytheformulade ningd t Therefore d t t d t td t h t t d t d t d t Thisexpressioncanbesimpli edbyusingtheinitialrelationintheformoft d t td t d t d t t d t Thequantityd t hasdisappearedhere andwecanprovethefollowingresult Lemma Foreveryvaluem N wehave dm t pm t d t qm t wherepm t andqm t arepolynomials suchthatqm t pm t p t q t Proof Thethreefunctionsd t d t andd t correspondtothetheorem sinitialcasesandtheyallowustoproceedbymathematicalinduction dm t dm t d t t dm t d t pm t d t qm t d t t d t pm t d t qm t pm t d t pm t qm t qm t d t t pm t d t t d t qm t pm t d t pm t qm t qm t d t pm t tpm t d t pm t d t t qm t d t pm t tpm t t qm t d t pm t qm t pm t qm t pm t d t Bytheinductionhypothesis qm t pm t and therefore d t disappears Wealsoobtain qm t pm t qm t pm t pm t whichprovesthe nalrelation Itisobviousthatthepolynomialsqm t aresimplecorrectionswhichreducetheinitialpartofthegeneratingfunctionsdm t to Asaresult theasymptoticvalueofdn k tn dk t onlydependsontheproductpk t d t andthepolynomialpk t isde nitelyanalyticatthe Theformulasfoundintheprevioussectioncanbeanalyzedfurthertoobtainsomemorepreciseinformationonthenumberofpathsgeneratedbythissimplescheme Letusbeginbydn tn d t thenumberofpathsarrivingatthepoint n n onthemaindiagonal Ifwesety y t td t theformulaford t canbewrittenas yt y t y ory t y y Sincey wecanapplytheLagrangeinversionformulaandobtainanexplicitexpressionfordn tn y t dn n yn y y n n n Xk n k n kn k Fromtheformerformula wecanderivetheasymptoticexpressionfordnbyusingthemethodofimplicitfunctions seeMarkushevitch asdescribedinSprug
三七文档所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
扫描二维码
我低调地华丽
本文标题：Journal of Combinatorial Theory, Series A, 28321{3
链接地址：https://www.777doc.com/doc-4055439 .html