15 251 Great Theoretical Ideas in Computer Science Generating Functions draft Anupam Gupta January 29 2012 A generating function represents an entire infinite sequence as a single mathematical object that can be manipulated algebraically The strength of the representation lies in the fact that many operations can be carried out a generating function including differentiation integration multiplication and others even though the underlying sequence may be defined in purely symbolic or combinatorial terms This makes generating functions an elegant and powerful counting technique In fact in the text Concrete Mathematics generating functions 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 as 2 A z a0 a1 z a2 z X ak z k 1 k 0 The adjective formal means that z is an abstract indeterminate and we are not concerned about numerical convergence of the series for any particular value of z The product of generating functions is defined as A z B z a0 a1 z a2 z 2 b0 b1 z b2 z 2 a0 b0 a0 b1 a1 b0 z a0 b2 a1 b1 a2 b0 z 2 c0 c1 z c2 z 2 C z 2 3 4 5 where ck k X ai bk i 6 i 0 Such a sum is sometimes called a discrete convolution Here s an application of this identity From the binomial theorem we have X r r 1 z zk k k 0 X s 1 z s zk k k 0 7 8 and therefore 1 z r 1 z s 1 z r s X r s zk k k 0 1 9 10 Therefore we have by the convolution identity k X r s r s k i k i i 0 11 We ve seen this before it s the number of ways of choosing k turns from a total of r avenues and s streets As another example using the binomial theorem we have 1 z r 1 z r 1 z 2 r X k r z 2k 1 k k 0 But now applying the convolution identity 6 on the left we obtain k X 0 if k is odd r r 1 i r k 2 i k i 1 if k is even k 2 i 0 This might look a bit strange let s check some small examples Taking k 2 r r r r r r r 2 r2 0 2 1 1 2 0 2 r r 1 which checks out Taking k 3 we get r r r r r r r r 0 0 3 1 2 2 1 3 0 12 13 14 15 16 17 18 which also checks 1 Math Counts To see the usefulness of generating functions for counting suppose that we have two disjoint sets A and B Also suppose that there are an ways of selecting n elements from A and bn ways of selecting n elements from B Then the number ways cn of selecting a total of n items from either A or B is n X cn ak bn k 19 k 0 To express this in terms of generating functions we have that the generating function for selecting items from either A or B is C z A z B z 20 We saw this earlier with choice trees and polynomials the generating function idea extends it to choice trees of infinite depth 2 2 A Fruity Example Here s a fun example from notes by Albert R Meyer and Clifford Smyth that illustrates how 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 quirky constraints 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 a basket of five fruits there are six possibilities apples bananas oranges pears 0 4 1 0 0 4 0 1 0 2 2 1 0 2 3 0 0 0 4 1 5 0 0 0 It 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 the sequence hbn i is h1 0 1 0 1 0 i and so the generating functions for bananas is B z X bn z n 1 z 2 z 4 n 0 1 1 z2 21 1 1 z5 22 Similarly the generating function for apples is A z X an z n 1 z 5 z 10 n 0 The generating functions O z and P z for oranges and pears are even easier O z 1 z z 2 z 3 z 4 P z 1 z 23 24 Now recall from our manipulations with geometric series that O z 1 z 5 1 z So when we multiply all of these functions together we get 1 1 1 z5 1 z 1 z5 1 z2 1 z 1 1 z 2 A z B z O z P z 3 25 26 Now we need to re expand this as a series To do this we use a little differentiation 1 1 d 2 1 z dz 1 z d X n z dz n 0 27 28 X d n z dz n 0 X n 1 X 29 nz n 1 30 n 1 z n 31 n 0 We ve determined that the number of ways of filling a basket with n fruits that satisfies our fruity constraints is n 1 That wasn t so bad after all Note that our special case above checks out there are six ways to take five fruits 3 Basic Properties of Generating Functions Let s now look at some of the basic ways we can manipulate generating functions which give us a bag of tricks to be used for counting problems Let A z and B z denote two generating functions for the sequences han i and hbn i respectively so that X A z a0 a1 z a2 z 2 ak z k 32 bk z k 33 k 0 B z b0 b1 z b2 z 2 X k 0 We can add the two functions and multiply by a scalar thus A z B z C z is the generating function for the sequence hcn i h an bn i We can also easily get the function for a sequence shifted m places to the right by multiplying by z m X X z m A z an z n m an m z n 34 n n which corresponds to the sequence shifted to the right 0 0 0 a0 a1 a2 z 35 m Shifting to …
View Full Document
Unlocking...