generating functionology 1994 wilf

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

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

2、eason-ablecostsofreproductionmaybecharged.Reproductionforpro¯torforanycommercialpurposesisstrictlyprohibited.viPrefaceThisbookisaboutgeneratingfunctionsandsomeoftheirusesindiscretemathematics.ThesubjectissovastthatIhavenotattemptedtogiveacomprehensivediscussion.InsteadIhavetriedon

3、lytocommunicatesomeofthemainideas.Generatingfunctionsareabridgebetweendiscretemathematics,ontheonehand,andcontinuousanalysis(particularlycomplexvariablethe-ory)ontheother.Itispossibletostudythemsolelyastoolsforsolvingdiscreteproblems.Assuchthereismuchthatispowerfulandmagicalinthew

4、aygeneratingfunctionsgiveuni¯edmethodsforhandlingsuchprob-lems.Thereaderwhowishedtoomittheanalyticalpartsofthesubjectwouldskipchapter5andportionsoftheearliermaterial.Toomitthosepartsofthesubject,however,islikelisteningtoastereobroadcastof,say,Beethoven'sNinthSymphony,usingonlythel

5、eftaudiochannel.Thefullbeautyofthesubjectofgeneratingfunctionsemergesonlyfromtuninginonbothchannels:thediscreteandthecontinuous.Seehowtheymakethesolutionofdi®erenceequationsintochild'splay.Thenseehowthetheoryoffunctionsofacomplexvariablegives,virtuallybyinspection,theapproximatesi

6、zeofthesolution.Theinterplaybetweenthetwochannelsisvitallyimportantfortheappreciationofthemusic.Inrecentyearstherehasbeenavigoroustrendinthedirectionof¯ndingbijectiveproofsofcombinatorialtheorems.Thatis,ifwewanttoprovethattwosetshavethesamecardinalitythenweshouldbeabletodoitbyexhi

7、bitinganexplicitbijectionbetweenthesets.Inmanycasesthefactthatthetwosetshavethesamecardinalitywasdiscoveredinthe¯rstplacebygeneratingfunctionarguments.Also,eventhoughbijectiveargumentsmaybeknown,thegeneratingfunctionproofsmaybeshorterormoreelegant.Thebijectiveproofsgiveoneacertain

8、satisfyingfeelingthatone`re-ally'