6.042/18.] Mathematics for Computer Science Apri7,2005 Srini devadas and Eric Lehman Lecture notes Generating functions Generating functions are one of the most surprising, useful, and clever inventions in discrete math. Roughly speaking, generating functions transform problems about se- quences into problems about functions. This is great because weve got piles of mathe- matical machinery for manipulating functions. Thanks to generating functions, we can apply all that machinery to problems about sequences. In this way, we can use generating functions to solve all sorts of counting problems. There is a huge chunk of mathematics concerning generating functions, so we will only get a taste of the subject In this lecture, well put sequences in angle brackets to more clearly distinguish ther from the many other mathemtical expressions floating around 1 Generating functions The ordinary generating function for the infinite sequence(9o, 91, 92, 93. )is the formal Power series G(x)=9+91x+9x2+93x3+… A generating function is a"formal"power series in the sense that we usually regard a a placeholder rather than a number. Only in rare cases will we let a be a real number and actually evaluate a generating function, so we can largely forget about questions of convergence. Not all generating functions are ordinary, but those are the only kind we'll consider here Throughout the lecture, well indicate the correspondence between a sequence and its enerating function with a double-sided arrow as follows 9o,9,g2,g,…)←→9+91x+g2x2+g3x3+ For example, here are some sequences and their generating functio (0,0,0,0,…)←→0+0x+0x2+0x3+…=0 (1,0,0,0,…〉←→1+0x+0x2+0x3+…=1 (3,2,1,0,)←→3+2x+1x2+0 3+2x+x2 The pattern here is simple: the i-th term in the sequence(indexing from O)is the coefficient of z' in the generating function Recall that the sum of an infinite geometric series is: 1+z+z2+23+6.042/18.062J Mathematics for Computer Science April 7, 2005 Srini Devadas and Eric Lehman Lecture Notes Generating Functions Generating functions are one of the most surprising, useful, and clever inventions in discrete math. Roughly speaking, generating functions transform problems about se￾quences into problems about functions. This is great because we’ve got piles of mathe￾matical machinery for manipulating functions. Thanks to generating functions, we can apply all that machinery to problems about sequences. In this way, we can use generating functions to solve all sorts of counting problems. There is a huge chunk of mathematics concerning generating functions, so we will only get a taste of the subject. In this lecture, we’ll put sequences in angle brackets to more clearly distinguish them from the many other mathemtical expressions floating around. 1 Generating Functions The ordinary generating function for the infinite sequence �g0, g1, g2, g3 . . .� is the formal power series: 3 G(x) = g0 + g1x + g2x 2 + g3x + · · · A generating function is a “formal” power series in the sense that we usually regard x as a placeholder rather than a number. Only in rare cases will we let x be a real number and actually evaluate a generating function, so we can largely forget about questions of convergence. Not all generating functions are ordinary, but those are the only kind we’ll consider here. Throughout the lecture, we’ll indicate the correspondence between a sequence and its generating function with a double­sided arrow as follows: 2 3 �g0, g1, g2, g3, . . .� ←→ g0 + g1x + g2x + g3x + · · · For example, here are some sequences and their generating functions: 3 �0, 0, 0, 0, . . .� ←→ 0 + 0x + 0x 2 + 0x + · · · = 0 3 �1, 0, 0, 0, . . .� ←→ 1 + 0x + 0x 2 + 0x + · · · = 1 3 �3, 2, 1, 0, . . .� ←→ 3 + 2x + 1x 2 + 0x = 3 + 2x + x 2 + · · · The pattern here is simple: the i­th term in the sequence (indexing from 0) is the coefficient of xi in the generating function. Recall that the sum of an infinite geometric series is: 1 3 1 + z + z 2 + z + · · · = 1 − z