1 What is a generating function?

1 Lecture notesMarch 1, 2015 generating FunctionsLecturer: Michel GoemansWe are going to discuss enumeration problems, and how to solve them using a powerful tool: generating functions. What is anenumeration problem? That s trying to determine the number ofobjects of sizensatisfying a certain definition. For instance,what is the number of permutations of{1,2,..,n}?(answer:n!), orwhat is the number of binary sequences of lengthn?(answer: 2n).Ok, now let us introduce some tools to answer more difficult enumerative What is a generating function? A generating function is just a different way of writing a sequence of numbers. Here we will bedealing mainly with sequences of numbers (an) which represent the number of objects of sizenfor an enumeration problem.

2 The interest of this notation is that certain natural operations ongenerating functions lead to powerful methods for dealing with recurrences (an)n 0be a sequence of numbers. Thegenerating functionassociated to thissequence is the seriesA(x) = n if we consider a classAof objects to be enumerated, we callgenerating functionof this classthe generating functionA(x) = n 0anxn,whereanis the number of objects of sizenin the that the variablexin generating functions doesn t stand for anything but serves as aplaceholder for keeping track of the coefficients generating function associated to the class of binary sequences (where thesizeof a sequence is its length) isA(x) = n 02nxnsince there arean= 2nbinary sequences of a positive integer.

3 The generating function associated to the sequencean=(kn)forn kandan= 0 forn > kis actually a polynomial:A(x) = n 0(kn)xn= (1 +x) the second equality uses the binomial theorem . ThusA(x) = (1 +x)kis the generating func-tion of the subsets of{1,2,..,k}(where thesizeof a subset is its number of elements).GenFun-1We see on this second example that the generating function has a very simple form. In fact,more simple than the sequence itself. This is the first magic of generating functions: in manynatural instances the generating function turns out to be very us now modify this example in connection with probabilities. Suppose we have a coin havingprobabilitypof landing on heads and a probabilityq= 1 pof landing on tails.

4 We toss itktimesand denote byanthe probability of getting exactlynheads. What is the generating function ofthe sequence (an)? Well, it can be seen thatan=(kn)qk npnthus the generating function isA(x) = n 0(kn)qk npnxn= (q+px)k,using the binomial theorem , observe that the generating function is(q+px)(q+px)(q+px) (q+px),which is just multiplyingktimes the generating function (q+px) corresponding to a single toss of thecoin1. This is the second magic of generating functions: the generating function for complicatedthings can be obtained from the generating function for simple things. We will explain this indetails, but first we consider an Operations on classes and generating functionsWe start with an easy observation.

5 Suppose thatAandBare disjoint classes of objects, andC=A]Bis their union (the symbol]denotes disjoint union). For instanceAcould be the set ofpermutations andBcould be the set of binary sequences. Can we express the generating functionofC(x) ofCin terms of the generating functionA(x) = n 0anxnofAandB(x) = n 0bnxnofB? Well yes it is simplyC(x) = n 0(an+bn)xn= n 0anxn+ n 0bnxn=A(x) +B(x)since the numbercnof objects of sizeninCisan+ have just seen addition of generating functions, and we will now look at multiplication ofgenerating functions. Consider the following problem. We have a die with six faces (numbered 1to 6) and a die with eight faces (numbered 1 to 8).

6 We roll the dice and we consider the sum ofthe dice. We want to know the number of wayscnof getting each claim that that the generating functionC(x) = n 0cnxnis given byC(x) = (x+x2+x3+x4+x5+x6) (x+x2+x3+x4+x5+x6+x7+x8).1 This is not a coincidence: if we were to expand out the product into a sum, it would be a sum of 2kterms, each ofwhich takes either aqor apxfrom each of thekterms in the product. Hence each terms can be seen as a particularsequence of tails (represented byq) and head tosses (represented bypx). In this calculation, thex s were a devicefor keeping track of the number of the first part accounts for the possible outcomes of the first die and the second part accountsfor the possible outcome of the second die.

7 For instance getting the sum 5 by getting 2 from thefirst die and 3 from the second die is accounted by the multiplication of the monomialx2from thefirst parenthesis with monomialx3from the second parenthesisx3, etc. Multiplying this out, wegetC(x) =x2+ 2x3+ 3x4+ 4x5+ 5x6+ 6x7+ 6x8+ 6x9+ 5x10+ 4x11+ 3x12+ 2x13+ the above problem we see that multiplying generating function is meaningful. Let us nowtry to generalize the above reasoning. Given two sets,AandBtheCartesian productA Bisdefined as the set of pairs (a,b) witha Aandb B. So ifAandBare finite the cardinality ofthese sets are related by|A B|=|A| |B|. We also suppose that thesizeof a pair (a,b) is thesize ofaplus the size instance, in the example above the classArepresents the possible numbers of the first die,so thatA={1,2,3,4,5,6}and the classBrepresents the possible number of the second die, sothatB={1,2,3,4,5,6,7,8}.

8 NowC=A Brepresents the possible numbers of the two dice. Thesizeof a number on the first die is just that number, so the generating function forAisA(x) =x+x2+x3+x4+x5+x6while the generating function forBisB(x) =x+x2+x3+x4+x5+x6+x7+ thesizeof a pair of number (a,b) Cis the sum of the numbers of the two dice. So we want todeterminecnwhich is the number of pairs (a,b). We have claimed above thatC(x) =A(x) B(x).We now prove a generalization of the above relation between generating classes of objects and letA(x)andB(x)be their generating the classC=A Bhas generating functionC(x) =A(x)B(x). the number of objects of sizenin the Cartesian productC=A B.

9 These objectsc= (a,b) are obtained by picking an objecta Aof sizek n(akchoices) and an objectb Bof sizen k(bn kchoices). Thuscn=n k=0akbn let us consider product of generating functionsA(x)B(x) = k 0akxk k 0bkxk .In order to get a monomialxnin this product, one must multiply a monomialakxkfork nfromthe first sum with a monomialbn kxn kfrom the second sum. Thus one hasA(x)B(x) = n 0(n k=0akbn k) completes the denote byAk=A A Athe set ofk-tuples of elements inA. Using theorem 1 wesee that this class has generating functionA(x)k=A(x) A(x) A(x) (whereA(x) is theGenFun-3generating function ofA). For instance, the generating function for the sum of numbers obtainedby rolling 4 dice with 6 faces isC(x) = (x+x2+x3+x4+x5+x6) we defineSeq(A) = k 0Ak,as the set of finite sequences of elements inA.

10 For instance ifA={0,1}thenA3={000,001,010,011,100,101 ,110,111}and Seq(A) is the set of binary sequences. Because of theorem 1 we see that the generating functionof the classC= Seq(A) isC(x) = k 0A(x)kwhereA(x) is the generating function ofA. Observe also that k 0A(x)k=11 A(x)since(1 A(x)) k 0A(x)k= (1 A(x)) (1 +A(x) +A(x)2+A(x)3+..) = instance for the binary sequences,A={0,1}has generating functionA(x) = 2x(Acontains2 binary sequences of length 1 and nothing else) so the class of binary sequencesC= Seq(A) hasgenerating functionC(x) = k 0A(x)k= k 0(2x)k=11 will know use these results to treat various Number of ways of giving changeLet us look at the following simple question.