flajolet ph., sedgewick r. analytic combinatorics - symbolic combinatorics (free web version, 2002)(196s)_mac_

《flajolet ph., sedgewick r. analytic combinatorics - symbolic combinatorics (free web version, 2002)(196s)_mac_》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ANALYTICCOMBINATORICS—SYMBOLICCOMBINATORICSPHILIPPEFLAJOLET&ROBERTSEDGEWICKAlgorithmsProjectDepartmentofComputerScienceINRIARocquencourtPrincetonUniversity78153LeChesnayPrinceton,NJ08540FranceUSAFirstEdition,May25,2002



iABSTRACTThisbookletdevelopsinnearly200p

2、agesthebasicsofcombinatorialenumerationthroughanapproachthatrevolvesaroundgeneratingfunctions.Themajorobjectsofinterestherearewords,trees,graphs,andpermutations,whichsurfacerecurrentlyinallareasofdiscretemathematics.Thetextpresentsthecoreofthetheorywithchaptersonunlabe

3、lledenumer-ationandordinarygeneratingfunctions,labelledenumerationandexponentialgeneratingfunctions,andfinallymultivariateenumerationandgeneratingfunctions.Itislargelyori-entedtowardsapplicationsofcombinatorialenumerationtorandomdiscretestructuresanddiscretemathematicsm

4、odels,astheyappearinvariousbranchesofscience,likestatisticalphysics,computationalbiology,probabilitytheory,and,lastnotleast,computerscienceandtheanalysisofalgorithms.Acknowledgements.ThisworkwassupportedinpartbytheISTProgrammeoftheEUundercontractnumberIST-1999-14186(AL

5、COM-FT).TheauthorsaregratefultoXavierGourdonwhoincitedustoaddaseparatechapteronmultivariategeneratingfunctionsandtoBrigitteVallee´formanycriticalsuggestionsregardingthepresentationandglobalorganizationofthistext.Thisbookletwouldbesubstantiallydifferent(andmuchlessinfor

6、mative)withoutNeilSloane'sEncyclopediaofIntegerSequences,SteveFinch'sMathematicalConstants,bothavailableontheinternet.BrunoSalvyandPaulZimmermannhavedevelopedalgorithmsandlibrariesforcombinatorialstructuresandgeneratingfunctionsthatarebasedontheMAPLEsystemforsymbolicco

7、mputationsandhaveproventobeimmenselyuseful.“SymbolicCombinatorics”isasetoflecturenotesthatareacomponentofawiderbookprojecttitledAnalyticCombinatorics,whichwillprovideaunifiedtreatmentofanalyticmethodsincombinatorics.Thistextispartlybasedonanearlierdocumenttitled“TheAver

8、ageCaseAnalysisofAlgorithms:CountingandGeneratingFunctions”,INRIARes.Rep.#1888(1993),116pages,whichitnowsubsumes.cPh