15-251: Great Theoretical Ideas in Computer Science Anupam GuptaGenerating Functions (draft!!) January 29, 2012A generating function represents an entire, infinite sequence as a single mathematical objectthat can be manipulated algebraically. The strength of the representation lies in the factthat many operations can be carried out a generating function, including differentiation,integration, multiplication, and others, even though the underlying sequence may be definedin purely symbolic or combinatorial terms. This makes generating functions an elegantand powerful counting technique. In fact, in the text Concrete Mathematics [?], generatingfunctions are described as “the most important idea in this whole book.”If a0, a1, a2, . . . is a sequence, then we define the formal power series A(z) asA(z) = a0+ a1z + a2z2+ · · · =∞Xk=0akzk. (1)The adjective formal means that z is an abstract indeterminate, and we are not concernedabout numerical convergence of the series for any particular value of z.The product of generating functions is defined asA(z)B(z) =a0+ a1z + a2z2+ · · ·b0+ b1z + b2z2+ · · ·(2)= a0b0+ (a0b1+ a1b0) z + (a0b2+ a1b1+ a2b0) z2+ · · · (3)= c0+ c1z + c2z2+ · · · (4)= C(z) (5)whereck=kXi=0aibk−i. (6)Such a sum is sometimes called a discrete convolution.Here’s an application of this identity. From the binomial theorem we have(1 + z)r=Xk≥0rkzk(7)(1 + z)s=Xk≥0skzk(8)and therefore(1 + z)r(1 + z)s= (1 + z)r+s(9)=Xk≥0r + skzk. (10)1Therefore we have, by the convolution identity,r + sk=kXi=0risk − i. (11)We’ve seen this before—it’s the number of ways of choosing k turns from a total of r avenuesand s streets.As another example, using the binomial theorem we have(1 − z)r(1 + z)r= (1 − z2)r(12)=Xk≥0(−1)krkz2k. (13)But now applying the convolution identity (6) on the left, we obtainkXi=0(−1)irirk − i=(0 if k is odd;(−1)k/2rk/2if k is even.(14)This might look a bit strange; let’s check some small examples. Taking k = 2,r0r2−r1r1+r2r0= 2r2− r2(15)= −r (16)= −r1(17)which checks out. Taking k = 3, we getr0r3−r1r2+r2r1−r3r0= 0 (18)which also checks.1 Math CountsTo see the usefulness of generating functions for counting, suppose that we have two disjointsets A and B. Also, suppose that there are anways of selecting n elements from A and bnways of selecting n elements from B. Then the number ways cnof selecting a total of n itemsfrom either A or B iscn=nXk=0akbn−k(19)To express this in terms of generating functions, we have that the generating function forselecting items from either A or B isC(z) = A(z)B(z). (20)We saw this earlier with choice trees and polynomials; the generating function idea extendsit to choice trees of “infinite depth.”22 A Fruity ExampleHere’s a fun example (from notes by Albert R. Meyer and Clifford Smyth) that illustrateshow generating functions can solve some seemingly very messy counting problems.Suppose that we want to fill a basket with fruit, but we impose on ourselves some very quirkyconstraints:1. The number of apples must be a multiple of five (an apple a [week]day...)2. The number of bananas must be even (eaten before 15-251 on Tues/Thurs...)3. We can take at most four oranges (too acidic...).4. There can be at most one pear (get mushy too fast...)If we try to count the number of ways directly, it looks complicated. For example, with abasket of five fruits, there are six possibilities:apples 0 0 0 0 0 5bananas 4 4 2 2 0 0oranges 1 0 2 3 4 0pears 0 1 1 0 1 0It’s hard to see any clear pattern here that would extend to bigger baskets.Let’s give generating functions a shot. Since the number of bananas must be even, thesequence hbni is h1, 0, 1, 0, 1, 0, . . .i, and so the generating functions for bananas isB(z) =Xn≥0bnzn= 1 + z2+ z4+ · · · =11 − z2. (21)Similarly, the generating function for apples isA(z) =Xn≥0anzn= 1 + z5+ z10+ · · · =11 − z5. (22)The generating functions O(z) and P (z) for oranges and pears are even easier:O(z) = 1 + z + z2+ z3+ z4(23)P (z) = 1 + z. (24)Now, recall from our manipulations with geometric series that O(z) = (1 − z5)/(1 − z). So,when we multiply all of these functions together, we getA(z)B(z)O(z)P(z) =11 − z511 − z21 − z51 − z(1 + z) (25)=1(1 − z)2. (26)3Now, we need to re-expand this as a series. To do this, we use a little differentiation:1(1 − z)2=ddz1(1 − z)(27)=ddz∞Xn=0zn(28)=∞Xn=0ddzzn(29)=∞Xn=1nzn−1(30)=∞Xn=0(n + 1)zn. (31)We’ve determined that the number of ways of filling a basket with n fruits that satisfies ourfruity constraints is n + 1. That wasn’t so bad after all! Note that our special case abovechecks out: there are six ways to take five fruits.3 Basic Properties of Generating FunctionsLet’s now look at some of the basic ways we can manipulate generating functions, whichgive us a bag of tricks to be used for counting problems. Let A(z) and B(z) denote twogenerating functions for the sequences hani and hbni respectively, so thatA(z) = a0+ a1z + a2z2+ · · · =∞Xk=0akzk(32)B(z) = b0+ b1z + b2z2+ · · · =∞Xk=0bkzk. (33)We can add the two functions, and multiply by a scalar; thus αA(z) + βB(z) = C(z) is thegenerating function for the sequence hcni = hαan+ βbni. We can also easily get the functionfor a sequence shifted m places to the right by multiplying by zm:zmA(z) =Xnanzn+m=Xnan−mzn(34)which corresponds to the sequence shifted to the right:0, 0, . . . , 0| {z }m, a0, a1, a2. . . (35)Shifting to the left is simple as well:A(z) − a0− a1z − . . . am−1zm−1zm=Xn≥manzn−m=Xn≥0an+mzn(36)4which corresponds to the sequenceam, am+1, am+2. . . (37)where the first m coefficients are dropped. Another useful technique is to replace the variablez by cz, where c is a constant, yieldingA(cz) =Xnancnzn(38)which is the generating function for the sequence hancni. If we want to replace hani by hnanithen the thing to do is differentiate and multiply by z:zA0(z) = zXnnanzn−1=Xnnanzn(39)This highlights our perspective that generating functions are formal power series; we arenot concerned with the numerical convergence of the series, and whether the derivative isdefined, etc. In a similar fashion, we can take the integral and useZx0zndt =1n + 1zn+1(40)to obtainZx0A(t) dt =Xn≥11nan−1zn(41)We’ve seen above that
View Full Document
Unlocking...