generatingfunctionology - Penn Math

1 GeneratingfunctionologyHerbert S. WilfDepartment of MathematicsUniversity of PennsylvaniaPhiladelphia, PennsylvaniaCopyright 1990 and 1994 byAcademic Press, rights re-served. This Internet Edition may be reproduced for any valid educationalpurpose of an institution of higher learning, in which case only the reason-able costs of reproduction may be charged. Reproduction for profit or forany commercial purposes is strictly book is about generating functions and some of their uses indiscrete mathematics. The subject is so vast that I have not attempted togive a comprehensive discussion. Instead I have tried only to communicatesome of the main functions are a bridge between discrete mathematics, onthe one hand, and continuous analysis (particularly complex variable the-ory) on the other.

2 It is possible to study them solely as tools for solvingdiscrete problems. As such there is much that is powerful and magical inthe way generating functions give unified methods for handling such prob-lems. The reader who wished to omit the analytical parts of the subjectwould skip chapter 5 and portions of the earlier omit those parts of the subject, however, is like listening to a stereobroadcast of, say, Beethoven s Ninth Symphony, using only the left full beauty of the subject of generating functions emerges onlyfrom tuning in on both channels: the discrete and the continuous. Seehow they make the solution of difference equations into child s play. Thensee how the theory of functions of a complex variable gives, virtually byinspection, the approximate size of the solution.

3 The interplay between thetwo channels is vitally important for the appreciation of the recent years there has been a vigorous trend in the direction offinding bijective proofs of combinatorial theorems. That is, if we want toprove that two sets have the same cardinality then we should be able todo it by exhibiting an explicit bijection between the sets. In many casesthe fact that the two sets have the same cardinality was discovered in thefirst place by generating function arguments. Also, even though bijectivearguments may be known, the generating function proofs may be shorteror more bijective proofs give one a certain satisfying feeling that one re-ally understands why the theorem is true.

4 The generating function argu-ments often give satisfying feelings of naturalness, and oh, I could havethought of that, as well as usually offering the best route to finding exactor approximate formulas for the numbers in book was tested in a senior course in discrete mathematics at theUniversity of Pennsylvania. My thanks go to the students in that course forhelping me at least partially to debug the manuscript, and to a number ofmy colleagues who have made many helpful suggestions. Any reader whois kind enough to send me a correction will receive a then-current completeerrata sheet and many S. WilfPhiladelphia, PASeptember 1, 1989viiPreface to the Second EditionThis edition contains several new areas of application, in chapter 4,many new problems and solutions, a number of improvements in the pre-sentation, and corrections.

5 It also contains an Appendix that describessome of the features of computer algebra programs that are of particularimportance in the study of generating am indebted to many people for helping to make this a better Sagan, in particular, made many helpful suggestions as a result ofa test run in his classroom. Many readers took up my offer (which is nowrepeated) to supply a current errata sheet and my thanks in return for anyerrors S. WilfPhiladelphia, PAMay 21, 1992viiiCONTENTSC hapter 1: Introductory Ideas and An easy two term recurrence .. A slightly harder two term recurrence .. A three term recurrence .. A three term boundary value problem .. Two independent variables.

6 Another 2-variable case .. 2: Formal power series .. The calculus of formal ordinary power series generating functions The calculus of formal exponential generating functions .. Power series, analytic theory .. Some useful power series .. Dirichlet series, formal theory .. 3: Cards, Decks, and Hands: The Exponential Introduction .. Definitions and a question .. Examples of exponential families .. The main counting theorems .. Permutations and their cycles .. Set partitions .. A subclass of permutations .. Involutions, etc.. 2-regular graphs .. Counting connected graphs .. Counting labeled bipartite graphs.

7 Counting labeled trees .. Exponential families and polynomials of binomial type.. Unlabeled cards and hands .. The money changing problem .. Partitions of integers .. Rooted trees and forests .. Historical notes .. 4: Applications of generating Generating functions find averages, etc.. A generatingfunctionological view of the sieve method .. The Snake Oil method for easier combinatorial identities .. WZ pairs prove harder identities .. Generating functions and unimodality, convexity, etc.. Generating functions prove congruences .. The cycle index of the symmetric group .. How many permutations have square roots? .. Counting polyominoes.

8 Exact covering sequences .. 5: Analytic and asymptotic The Lagrange Inversion Formula .. Analyticity and asymptotics (I): Poles .. Analyticity and asymptotics (II): Algebraic singularities .. Analyticity and asymptotics (III): Hayman s method .. : 1 Introductory ideas and examplesA generating function is a clothesline on which we hang up a sequenceof numbers for that means is this: suppose we have a problem whose answer isa sequence of numbers,a0,a1,a2,.. We want to know what the sequenceis. What kind of an answer might we expect?A simple formula foranwould be the best that could be hoped for. Ifwe find thatan=n2+3 for eachn=0,1,2,.., then there s no doubt thatwe have answered the what if there isn t any simple formula for the members of theunknown sequence?

9 After all, some sequences are complicated. To takejust one hair-raising example, suppose the unknown sequence is 2, 3, 5, 7,11, 13, 17, 19,.., whereanis thenth prime number. Well then, it wouldbe just plain unreasonable to expect any kind of a simple functions add another string to your bow. Although giv-ing a simple formula for the members of the sequence may be out of thequestion, we might be able to give a simple formula forthe sum of a powerseries, whose coefficients are the sequence that we re looking instance, suppose we want the Fibonacci numbersF0,F1,F2,..,and what we know about them is that they satisfy the recurrence relationFn+1=Fn+Fn 1(n 1;F0=0;F1=1).The sequence begins with 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

10 Thereareexact, not-very-complicated formulas forFn, as we will see later, in example2 of this chapter. But, just to get across the idea of a generating function,here is how a generatingfunctionologist might answer the question:thenth Fibonacci number,Fn, is the coefficient ofxnin the expansion of thefunctionx/(1 x x2)as a power series about the may concede that this is a kind of answer, but it leaves a certainunsatisfied feeling. It isn treallyan answer, you might say, because wedon t have that explicit formula. Is it agoodanswer?In this book we hope to convince you that answers like this one areoften spectacularly good, in that they are themselves elegant, they allowyou to do almost anything you d like to do with your sequence, and gener-ating functions can be simple and easy to handle even in cases where exactformulas might be stupendously are some of the things that you ll often be able to do with gener-ating function answers:(a)Find an exact formula for the members of your always.