《Mathematics for Computer》Generating functions

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

2 erating Functio This equation does not hold when [zl> 1, but once again we won't worry about conver- gence issues. This formula gives closed-form generating functions for a whole range of sequences. For example (1,1,1,1,)←→1+x+x2+x3 1+x 1+ax+a2x2+a3x3+ (1,0,1,0,1,0,……) 1+x2+x4+x6+ 2 Operations on Generating Functions The magic of generating functions is that we can carry out all sorts of manipulations on sequences by performing mathematical operations on their associated generating func- tions. Let' s experiment with various operations and characterize their effects in terms of 2.1 Scaling Multiplying a generating function by a constant scales every term in the associated se- quence by the same constant. For mple, we noted above that (1,0,1,0,1,0,)←→1+x2+x4+x°+ Multiplying the generating function by 2 gives 2 2+2x2+2x4+2x6+ which generates the sequence (2,0,2,0,2,0, Rule 1(Scaling Rule). If then cfo,cf1,cf2,…)←→c·F(x)

2 Generating Functions This equation does not hold when | | z ≥ 1, but once again we won’t worry about conver￾gence issues. This formula gives closed­form generating functions for a whole range of sequences. For example: 1 , 1, 1, 1, . . .� 1 + x + x �1 ←→ 2 + x3 + · · · = 1 − x 1 �1, −1, 1, −1, . . .� ←→ 1 − x + x2 − x3 + x4 − · · · = 1 + x 1 3 3 �1, a, a2, a , . . .� 1 + ax + a2x2 + a x = 1 − ax ←→ 3 + · · · 1 4 + x6 �1, 0, 1, 0, 1, 0, . . .� 1 + x2 + x = 1 − x ←→ 2 + · · · 2 Operations on Generating Functions The magic of generating functions is that we can carry out all sorts of manipulations on sequences by performing mathematical operations on their associated generating func￾tions. Let’s experiment with various operations and characterize their effects in terms of sequences. 2.1 Scaling Multiplying a generating function by a constant scales every term in the associated se￾quence by the same constant. For example, we noted above that: 1 4 6 �1, 0, 1, 0, 1, 0, . . .� ←→ 1 + x 2 + x + x = 1 − x2 + · · · Multiplying the generating function by 2 gives 2 = 2 + 2x 2 + 2x 4 + 2x 6 1 − x2 + · · · which generates the sequence: �2, 0, 2, 0, 2, 0, . . .� Rule 1 (Scaling Rule). If �f0, f1, f2, . . .� ←→ F(x), then �cf0, cf1, cf2, . . .� ←→ c · F(x)

Generating Functions Proof (cfo,cf1,cf2… cfo +cfia+cf222+ (o+fia+f2 2.2 Addition Adding generating functions corresponds to adding the two sequences term by term. For example, adding two of our earlier examples gives 1,1, 1.-1 1+ 2,0.2,0,2,0 1+ Weve now derived two different expressions that both generate the sequence (2, 0, 2, 0, .. Not surprisingly, they turn out to be equal 1 2 )(1+x)1-x2 Rule 2 (Addition Rule). If f,f1,f2, the Jfo+90,f1+g1,f2+g2,…)←→F(x)+G(x) Proof (fo+90,f1+g1,f2 (n+gn)r fn gn F(a)+G(a)

Generating Functions 3 Proof. �cf0, cf1, cf2, . . .� cf0 + cf1x + cf2x ←→ 2 + · · · = c · (f0 + f1x + f2x 2 + · · ·) = cF(x) 2.2 Addition Adding generating functions corresponds to adding the two sequences term by term. For example, adding two of our earlier examples gives: 1 � 1, 1, 1, 1, 1, 1, . . . � ←→ 1 − x 1 + � 1, −1, 1, −1, 1, −1, . . . � ←→ 1 + x 1 1 � 2, 0, 2, 0, 2, 0, . . . � ←→ + 1 − x 1 + x We’ve now derived two different expressions that both generate the sequence �2, 0, 2, 0, . . .�. Not surprisingly, they turn out to be equal: 1 1 (1 + x) + (1 − x) 2 + = = 1 − x 1 + x (1 − x)(1 + x) 1 − x2 Rule 2 (Addition Rule). If �f0, f1, f2, . . .� ←→ F(x), and �g0, g1, g2, . . .� ←→ G(x), then �f0 + g0, f1 + g1, f2 + g2, . . .� ←→ F(x) + G(x). Proof. �∞ �f0 + g0, f1 + g1, f2 + g2, . . .� ←→ (fn + gn)x n n=0 � � � � �∞ �∞ = fnx n + gnx n n=0 n=0 = F(x) + G(x)

erating Function 2.3 Right Shifting Let's start over again with a simple sequence and its generating function (1,1,1,1,}←→ Now let's right-shift the sequence by adding k leading zeros 0,……,0,1,1,1,… k zeroes (1+x+x2+x3 ating function by z. This holds true in genera ce corresponds to multiplying the gener- Evidently, adding k leading zeros to the sequel Rule 3(Right-Shift Rule). If(fo, f1, f2, .. F(a),then Q,0,……,0,f0,f1,f2,… k zeroes Proof. 0,0,…,0,f6,f1,f2,) fo z +fia++f2:c++ x2.(Jo+f1x+f2x2+f3x32+…) 2.4 Differentiation What happens if we take the derivative of a generating function? As an example, let's differentiate the now-familiar generating function for an infinite sequence of 1's d 1+2x+3x2+4x3+ (1,2.3.4…)←a-2 We found a generating function for the sequence (1, 2, 3, 4,...) In general, differentiating a generating function has two effects on the corresponding equence: each term is multiplied by its index and the entire sequence is shifted left one P

� �� � � � 4 Generating Functions 2.3 Right Shifting Let’s start over again with a simple sequence and its generating function: 1 �1, 1, 1, 1, . . .� ←→ 1 − x Now let’s right­shift the sequence by adding k leading zeros: k+1 k+2 k+3 �0, 0, . . . , 0, 1, 1, 1, . . .� x k + x + x + x � �� � ←→ + · · · k zeroes k 3 = x · (1 + x + x 2 + x + · · ·) k x = 1 − x Evidently, adding k leading zeros to the sequence corresponds to multiplying the gener￾ating function by xk. This holds true in general. Rule 3 (Right­Shift Rule). If �f0, f1, f2, . . .� ←→ F(x), then: �0, 0, . . . , 0, f0, f1, f2, . . .� ←→ x k F(x) � �� � · k zeroes Proof. k zeroes f0x k + f1x k+1 + f2x k+2 �0, 0, . . . , 0, f0, f1, f2, . . .� ←→ + · · · 3 = x k · (f0 + f1x + f2x 2 + f3x + · · ·) k = x F· (x) 2.4 Differentiation What happens if we take the derivative of a generating function? As an example, let’s differentiate the now­familiar generating function for an infinite sequence of 1’s. d d 1 (1 + x + x 2 + x 3 + x 4 = dx + · · ·) dx 1 − x 1 3 1 + 2x + 3x 2 + 4x = 2 + · · · (1 − x) 1 �1, 2, 3, 4, . . .� ←→ (1 − x)2 We found a generating function for the sequence �1, 2, 3, 4, . . .�! In general, differentiating a generating function has two effects on the corresponding sequence: each term is multiplied by its index and the entire sequence is shifted left one place

Generating Functions Rule 4(Derivative Rule). If (f0,f1,f2,f3,)←→F(x), th (f1,2f23/f3,)+→F(x Proof. (f1,2f2,3f3,…)=f1+2f2x+3f3x2+ (o+fic+f2 z+f3 The Derivative Rule is very useful. In fact, there is frequent, independent need for each of differentiation s two effects, multiplying terms by their index and left-shifting one place. Typically, we want just one effect and must somehow cancel out the other. For ex ample, let's try to find the generating function for the sequence of squares, 0, 1, 4, 9, 16,...) If we could start with the sequence (1,1,1,1,.. and multiply each term by its index two times, then wed have the desired result: (0·0.1·1,22,3:3,……)=(0,1,4,9,) A challenge is that differentiation not only multiplies each term by its index, but also shifts the whole sequence left one place. However, the Right-Shift Rule 3 tells how to cancel out this unwanted left-shift: multiply the generating function by a Our procedure, therefore, is to begin with the generating function for (1,1,1, 1,..., differentiate, multiply by a, and then differentiate and multiply by r once more (1,2,3,4,…)←→ 1 dr l-r ( (0,1,2,3,…) (1-x)2 (1,4,9,16,… 1+x dr(1-x)2(1-x)3 1+xx(1+x) (,.49…)一x(-x)=(1-x)3 Thus, the generating function for squares is

Generating Functions 5 Rule 4 (Derivative Rule). If �f0, f1, f2, f3, . . .� ←→ F(x), then � �f1, 2f2, 3f3, . . .� ←→ F (x). Proof. �f1, 2f2, 3f3, . . .� = f1 + 2f2x + 3f3x 2 + · · · d (f0 + f1x + f2x 2 + f3x 3 = + dx · · ·) d = F(x) dx The Derivative Rule is very useful. In fact, there is frequent, independent need for each of differentiation’s two effects, multiplying terms by their index and left­shifting one place. Typically, we want just one effect and must somehow cancel out the other. For ex￾ample, let’s try to find the generating function forthe sequence of squares, �0, 1, 4, 9, 16, . . .�. If we could start with the sequence �1, 1, 1, 1, . . .� and multiply each term by its index two times, then we’d have the desired result: �0 · · · · 0, 1 1, 2 2, 3 3, . . .� = �0, 1, 4, 9, . . .� A challenge is that differentiation not only multiplies each term by its index, but also shifts the whole sequence left one place. However, the Right­Shift Rule 3 tells how to cancel out this unwanted left­shift: multiply the generating function by x. Our procedure, therefore, is to begin with the generating function for �1, 1, 1, 1, . . .�, differentiate, multiply by x, and then differentiate and multiply by x once more. 1 �1, 1, 1, 1, . . .� ←→ 1 − x d 1 1 �1, 2, 3, 4, . . .� ←→ = dx 1 − x (1 − x)2 1 x �0, 1, 2, 3, . . .� ←→ x · = (1 − x)2 (1 − x)2 d x 1 + x �1, 4, 9, 16, . . .� ←→ = dx (1 − x)2 (1 − x)3 1 + x x(1 + x) �0, 1, 4, 9, . . .� ←→ x · = (1 − x)3 (1 − x)3 Thus, the generating function for squares is: x(1 + x) (1 − x)3