odlyzko. asymptotic enumeration methods (book)(192s)

《odlyzko. asymptotic enumeration methods (book)(192s)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、AsymptoticEnumerationMethodsA.M.OdlyzkoAT&TBellLaboratoriesMurrayHill,NewJersey079741.IntroductionAsymptoticenumerationmethodsprovidequantitativeinformationabouttherateofgrowthoffunctionsthatcountcombinatorialobjects.Typicalquestionsthatthesemeth-odsanswerare:(1)Howdoesthenumbero

2、fpartitionsofasetofnelementsgrowwithn?(2)Howdoesthisnumbercomparetothenumberofpermutationsofthatset?Theredoexistenumerationresultsthatleavenothingtobedesired.Forexample,ifandenotesthenumberofsubsetsofasetwithnelements,thenwetriviallyhavean=2n.Thisansweriscompactandexplicit,andyie

3、ldsinformationaboutallaspectsofthisfunction.Forexample,congruencepropertiesofanreducetowell-studiednumbertheoryquestions.(Thisisnottosaythatallsuchquestionshavebeenanswered,though!)Theformulaan=2nalsoprovidescompletequantitativeinformationaboutan.Itiseasytocomputeforanyvalueofn,i

4、tsbehaviorisaboutassimpleaspossible,anditholdsuniformlyforalln.However,suchexamplesareextremelyrare.Usually,evenwhenthereisaformulaforthefunctionweareinterestedin,itisacomplicatedone,involvingsummationsorrecurrences.Thepurposeofasymptoticmethodsistoprovidesimpleexplicitformulasth

5、atdescribethebehaviorofasequenceforlargevaluesofindices.Thereisnosatisfactorydenitionofwhatismeantbysimple"orbyexplicit."However,wecanillustratethisconceptbysomeexamples.Thenumberofpermutationsofnlettersisgivenbybn=n!.Thisisacompactnotation,butonlyinthesensethatfactorialsareso

6、widelyusedthattheyhaveaspecialsymbol.Thesymboln!standsforn
(n1)
(n2)
:::
2
1,anditisthelatterformulathathastobeusedtoanswerquestionsaboutthenumberofpermutations.Ifoneisafterarithmeticinformation,suchasthehighestpowerof7,say,thatdividesn!,onecanobtainitfromtheproductformula,bute

7、venthensomeworkhastobedone.Formostquantitativepurposes,however,n!=n
(n1)
:::
2
1isinadequate.Sincethisformulaisaproductofnterms,mostofthemlarge,itisclearthatn!growsrapidly,butitisnotobviousjusthowrapidly.Sinceallbutthelasttermare2,wehaven!2n1,andsinceallbutthelasttwotermsare

8、3,wehaven!3n2,andsoon.Ontheotherhand,e