generatingfunctionology - h. wilf

《generatingfunctionology - h. wilf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、generatingfunctionologyHerbertS.WilfDepartmentofMathematicsUniversityofPennsylvaniaPhiladelphia,PennsylvaniaCopyright1990and1994byAcademicPress,Inc.Allrightsre-served.ThisInternetEditionmaybereproducedforanyvalideducationalpurposeofaninstitutionofhigherlearning,inwhichcaseonlythereason-ableco

2、stsofreproductionmaybecharged.Reproductionforpro¯torforanycommercialpurposesisstrictlyprohibited.viPrefaceThisbookisaboutgeneratingfunctionsandsomeoftheirusesindiscretemathematics.ThesubjectissovastthatIhavenotattemptedtogiveacomprehensivediscussion.InsteadIhavetriedonlytocommunicatesomeofthe

3、mainideas.Generatingfunctionsareabridgebetweendiscretemathematics,ontheonehand,andcontinuousanalysis(particularlycomplexvariablethe-ory)ontheother.Itispossibletostudythemsolelyastoolsforsolvingdiscreteproblems.Assuchthereismuchthatispowerfulandmagicalinthewaygeneratingfunctionsgiveuni¯edmetho

4、dsforhandlingsuchprob-lems.Thereaderwhowishedtoomittheanalyticalpartsofthesubjectwouldskipchapter5andportionsoftheearliermaterial.Toomitthosepartsofthesubject,however,islikelisteningtoastereobroadcastof,say,Beethoven'sNinthSymphony,usingonlytheleftaudiochannel.Thefullbeautyofthesubjectofgener

5、atingfunctionsemergesonlyfromtuninginonbothchannels:thediscreteandthecontinuous.Seehowtheymakethesolutionofdi®erenceequationsintochild'splay.Thenseehowthetheoryoffunctionsofacomplexvariablegives,virtuallybyinspection,theapproximatesizeofthesolution.Theinterplaybetweenthetwochannelsisvitallyim

6、portantfortheappreciationofthemusic.Inrecentyearstherehasbeenavigoroustrendinthedirectionof¯ndingbijectiveproofsofcombinatorialtheorems.Thatis,ifwewanttoprovethattwosetshavethesamecardinalitythenweshouldbeabletodoitbyexhibitinganexplicitbijectionbetweenthesets.Inmanycasesthefactthatthetwosets

7、havethesamecardinalitywasdiscoveredinthe¯rstplacebygeneratingfunctionarguments.Also,eventhoughbijectiveargumentsmaybeknown,thegeneratingfunctionproofsmaybeshorterormoreelegant.Thebijectiveproofsgiveoneacertainsatisfyingfeelingthatone`re-ally'