《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

erating Function 3 The Fibonacci Sequence Sometimes we can find nice generating functions for more complic example, here is a generating function for the Fibonacci numbers Cated sequences. For (0,1,1,2,3,5,8,13,21, The Fibonacci numbers are a fairly nasty bunch, but the generating function is simple Were going to derive this generating function and then use it to find a closed form for the n-Fibonacci number Of course, we already have a closed form for Fibonacci numbers obtained from the cookbook procedure for solving linear recurrences. But there are a couple reasons to cover the same ground again. First, we'll gain some insight into why the cookbook method for linear recurrences works. And, second, the techniques well use are applicable to a large class of recurrence equations, including some that we have no other way to tackle 3. inding a Generating Function Let' s begin by recalling the definition of the Fibonacci numbers fo f1=1 fn=fn-1+fr (forn≥2) We can expand the final clause into an infinite sequence of equations Thus the fibonacci numbers are defined by f1 + fo f2+f1 f3+f2 Now the overall plan is to define a function F(a) that generates the sequence on the left side of the equality symbols, which are the Fibonacci numbers. Then we derive a function that generates the sequence on the right side. Finally, we equate the two and solve for F(. Let's try this Fi F(ar)=fo+fir+ f2.2+f3 r+f4

6 Generating Functions 3 The Fibonacci Sequence Sometimes we can find nice generating functions for more complicated sequences. For example, here is a generating function for the Fibonacci numbers: x �0, 1, 1, 2, 3, 5, 8, 13, 21, . . .� ←→ 1 − x − x2 The Fibonacci numbers are a fairly nasty bunch, but the generating function is simple! We’re going to derive this generating function and then use it to find a closed form for the n­Fibonacci number. Of course, we already have a closed form for Fibonacci numbers, obtained from the cookbook procedure for solving linear recurrences. But there are a couple reasons to cover the same ground again. First, we’ll gain some insight into why the cookbook method for linear recurrences works. And, second, the techniques we’ll use are applicable to a large class of recurrence equations, including some that we have no other way to tackle. 3.1 Finding a Generating Function Let’s begin by recalling the definition of the Fibonacci numbers: f0 = 0 f1 = 1 fn = fn−1 + fn−2 (for n ≥ 2) We can expand the final clause into an infinite sequence of equations. Thus, the Fibonacci numbers are defined by: f0 =0 f1 =1 f2 =f1 + f0 f3 =f2 + f1 f4 =f3 + f2 . . . Now the overall plan is to define a function F(x) that generates the sequence on the left side of the equality symbols, which are the Fibonacci numbers. Then we derive a function that generates the sequence on the right side. Finally, we equate the two and solve for F(x). Let’s try this. First, we define: 3 + f4x 4 F(x) = f0 + f1x + f2x 2 + f3x + · · ·

Generating Functions Now we need to derive a generating function for the sequence (0,1,f1+f0,f2+f1,f3+f2,… One approach is to break this into a sum of three sequences for which we know generating functions and then apply the Addition rule (0. 0, 0,fo, .,6 0ff f2, 2F(a) 0.1+f0,f1+fo,f2+f1,f3+f2,…) c+F()+a F(ar) This sequence is almost identical to the right sides of the Fibonacci equations. The one blemish is that the second term is 1 fo instead of simply 1. However, this amounts to nothing, since fo=0 anyway witing down ail of the equations that define the Fibonacci numbers in one fell swoop. ta Now if we equate F()with the new function r+ar F(ar)+x F(r), then were implic F o+ f1 a+ f2 f3 x+ f2 x+xF(x)+x2F(x)=0+(1+f0)x+(f1+f0)x2+(f2+f1)x3+(f3+f2)x4+ olving for F(a) gives the generating function for the Fibonacci sequence (x) (x)+x2F(x) F(x)=1 Sure enough, this is the simple generating function we claimed at the outset 3.2 Finding a closed Form Why should one care about the generating function for a sequence There are several answers, but here is one: if we can find a generating function for a sequence, then we can often find a closed form for the n-th coefficient--which can be pretty useful! For example, a closed form for the coefficient of n in the power series for r/(1-x-c2)would be an explicit formula for the n-th Fibonacci number So our next task is to extract coefficients from a generating function. There are sev eral approaches. For a generating function that is a ratio of polynomials, we can use the method of partial fractions, which you learned in calculus. Just as the terms in a pa tial fractions expansion are easier to integrate, the coefficients of those terms are easy compute Let's try this approach with the generating function for Fibonacci numbers. First, we factor the denominator: (1-a1)(

� � � � � � � Generating Functions 7 Now we need to derive a generating function for the sequence: �0, 1, f1 + f0, f2 + f1, f3 + f2, . . .� One approach is to break this into a sum of three sequences for which we know generating functions and then apply the Addition Rule: � 0, 1, 0, 0, 0, . . . � ←→ x � 0, f0, f1, f2, f3, . . . � ←→ xF(x) + � 0, 0, f0, f1, f2, . . . � ←→ x2F(x) 0, 1 + f0, f1 + f0, f2 + f1, f3 + f2, . . . � ←→ x + xF(x) + x2F(x) This sequence is almost identical to the right sides of the Fibonacci equations. The one blemish is that the second term is 1 + f0 instead of simply 1. However, this amounts to nothing, since f0 = 0 anyway. Now if we equate F(x) with the new function x+xF(x)+x2F(x), then we’re implicitly writing down all of the equations that define the Fibonacci numbers in one fell swoop: F(x) = f0 + f1 x + f2 x2 + f3 x3 + f4 x4 + . . . x + xF(x) + x2F(x) = 0 + (1 + f0) x + (f1 + f0) x2 + (f2 + f1) x3 + (f3 + f2) x4 + · · · Solving for F(x) gives the generating function for the Fibonacci sequence: F(x) = x + xF(x) + x 2 F(x) x ⇒ F(x) = 1 − x − x2 Sure enough, this is the simple generating function we claimed at the outset! 3.2 Finding a Closed Form Why should one care about the generating function for a sequence? There are several answers, but here is one: if we can find a generating function for a sequence, then we can often find a closed form for the n­th coefficient— which can be pretty useful! For example, a closed form for the coefficient of xn in the power series for x/(1 − x − x2) would be an explicit formula for the n­th Fibonacci number. So our next task is to extract coefficients from a generating function. There are sev￾eral approaches. For a generating function that is a ratio of polynomials, we can use the method of partial fractions, which you learned in calculus. Just as the terms in a par￾tial fractions expansion are easier to integrate, the coefficients of those terms are easy to compute. Let’s try this approach with the generating function for Fibonacci numbers. First, we factor the denominator: 1 − x − x 2 = (1 − α1x)(1 − α2x)

erating Function where a1=2(1+v5)and a2=2(1-V5) Next, we find A1 and A2 which satisfy A A2 We do this by plugging in various values of a to generate linear equations in Al and A Ne can then find Al and A2 by solving a linear system. This gives a2 Substituting into the equation above gives the partial fractions expansion of F(a) Each term in the partial fractions expansion has a simple power series given by the geo- metric sum formula C1a 1-a2C Substituting in these series gives a power series for the generating function (1+a1x+a2x2+…)-(1+ 1-a2 fn 1+√5 This is the same scary formula for the n-th Fibonacci number that we found using the method for solving linear recurrences. And this alternate approach sheds some light on that method. In particular, the strange rules involving repeated roots of the characteristic equation are reflections of the rules for finding a partial fractions expansion 4 Counting with Generating Functions Generating functions are particularly useful for solving counting problems. In particular, problems involving choosing items from a set often lead to nice generating functions When generating functions are used in this way, the coefficient of a" is the number of ways to choose n items

� � � � 8 Generating Functions where 1 1 α1 = 2 (1 + √5) and α2 = 2 (1 − √5). Next, we find A1 and A2 which satisfy: x A1 A2 = + 1 − x − x2 1 − α1x 1 − α2x We do this by plugging in various values of x to generate linear equations in A1 and A2. We can then find A1 and A2 by solving a linear system. This gives: 1 1 A1 = = α1 − α2 √5 −1 1 A2 = = α1 − α2 −√5 Substituting into the equation above gives the partial fractions expansion of F(x): x 1 1 1 = 1 − x − x2 √5 1 − α1x − 1 − α2x Each term in the partial fractions expansion has a simple power series given by the geo￾metric sum formula: 1 2 = 1 + α1x + α2 1x 1 − α1x + · · · 1 2 = 1 + α2x + α2 2x 1 − α2x + · · · Substituting in these series gives a power series for the generating function: 1 1 1 F(x) = √5 1 − α1x − 1 − α2x 1 � 2 � 2 = √5 (1 + α1x + α2 1x + · · ·) − (1 + α2x + α2x 2 + · · ·) αn 1 − αn fn = √5 ⇒ 2 �� � 1 − √5 n � �n 1 1 + √5 � = √5 2 − 2 This is the same scary formula for the n­th Fibonacci number that we found using the method for solving linear recurrences. And this alternate approach sheds some light on that method. In particular, the strange rules involving repeated roots of the characteristic equation are reflections of the rules for finding a partial fractions expansion! 4 Counting with Generating Functions Generating functions are particularly useful for solving counting problems. In particular, problems involving choosing items from a set often lead to nice generating functions. When generating functions are used in this way, the coefficient of xn is the number of ways to choose n items

Generating Functions 4.1 Choosing distinct Items from a Set The generating function for binomial coefficients follows directly from the Binomial The- ,0,0,0, r+ 0 t ar Thus, the coefficient of z" in(1 +r)is the number of ways to choose n distinct items om a k-element set. For example, the coefficient of 2 is ) the number of ways to choose 2 items from a k-element set. Similarly, the coefficient of t is the number of ways to choose k+ l items from a k-element set, which is zero 4.2 Building Generating Functions that Count Often we can translate the description of a counting problem directly into a generating function for the solution. For example, we could figure out that(1+a) generates the number of ways to select n distinct items from a k-element subset without resorting to the binomial Theorem or even fussing with binomial coefficients! Here is how. First, consider a single-element set a1. The generating function for the number of ways to choose n elements from this set is simply 1 +r: we have 1 way to choose zero elements, 1 way to choose one element, and o ways to choose more than one element. Similarly, the number of ways to choose n elements from the set a2 is also given by the generating function 1+a. The fact that the elements differ in the two cases is irrelevant Now here is the the main trick: the generating function for choosing elements from a union of disjoint sets is the product of the generating functions for choosing from each set. We'll justify this in a moment, but let's first look at an example. According to this principle, the generating function for the number of ways to choose n elements from the (a1, a2) (1 +ar (1+x)=(1+ 1+2 OGF for OGF for a2 Sure enough, for the set (a1, a2), we have 1 way to choose zero elements, 2 ways to choose one element, 1 way to choose two elements and o ways to choose more than two ele- Repeated application of this rule gives the generating function for choosing n items from a k-element set a1, a2, .. ak H (1+x)·(1+x)…(1+x) OGF for OGF for OGF for OGF fo {a}{a2}

� � Generating Functions 9 4.1 Choosing Distinct Items from a Set The generating function for binomial coefficients follows directly from the Binomial The￾orem: �� � � � � � � � � � � � � � � � � k k k k k k k 2 k k , , , . . . , , 0, 0, 0, . . . + x + x + x 0 1 2 k ←→ 0 1 2 + · · · k = (1 + x) k Thus, the coefficient of xn in (1 + x)k is the number of ways to choose n distinct items k from a k­element set. For example, the coefficient of x2 is , the number of ways to 2 choose 2 items from a k­element set. Similarly, the coefficient of xk+1 is the number of ways to choose k + 1 items from a k­element set, which is zero. 4.2 Building Generating Functions that Count Often we can translate the description of a counting problem directly into a generating function for the solution. For example, we could figure out that (1 + x)k generates the number of ways to select n distinct items from a k­element subset without resorting to the Binomial Theorem or even fussing with binomial coefficients! Here is how. First, consider a single­element set {a1}. The generating function for the number of ways to choose n elements from this set is simply 1 + x: we have 1 way to choose zero elements, 1 way to choose one element, and 0 ways to choose more than one element. Similarly, the number of ways to choose n elements from the set {a2} is also given by the generating function 1 + x. The fact that the elements differ in the two cases is irrelevant. Now here is the the main trick: the generating function for choosing elements from a union of disjoint sets is the product of the generating functions for choosing from each set. We’ll justify this in a moment, but let’s first look at an example. According to this principle, the generating function for the number of ways to choose n elements from the {a1, a2} is: (1 + x) (1 + x) = (1 + x) 2 = 1 + 2x + x 2 � �� � · � �� � � �� � OGF for OGF for OGF for {a1} {a2} {a1, a2} Sure enough, for the set {a1, a2}, we have 1 way to choose zero elements, 2 ways to choose one element, 1 way to choose two elements, and 0 ways to choose more than two ele￾ments. Repeated application of this rule gives the generating function for choosing n items from a k­element set {a1, a2, . . . , ak}: (1 + x) (1 + x) (1 + x) = (1 + x) k � �� � · � �� � · · · � �� � � �� � OGF for OGF for OGF for OGF for {a1} {a2} {ak} {a1, a2, . . . , ak}

Generating functions This is the same generating function that we obtained by using the Binomial Theorem But this time around we translated directly from the counting problem to the generating function We can extend these ideas to a general principle Rule 5( Convolution Rule). Let A(r) be the generating function for selecting items from set A and let b(a) be the generating function for selecting items from set B. If A and B are disjoint, then the generating function for selecting items from the union A U B is the product A(). B(a) This rule is rather ambiguous: what exactly are the rules governing the selection of items from a set? Remarkably, the Convolution Rule remains valid under many inter pretations of selection. For example, we could insist that distinct items be selected or we might allow the same item to be picked a limited number of times or any number of times. Informally, the only restrictions are that (1) the order in which items are selected is disregarded and(2)restrictions on the selection of items from sets A and B also apply in selecting items from AU B.(Formally, there must be a bijection between n-element selections from AUB and ordered pairs of selections from A and B containing a total of n elements. Proof. Define B()=∑hnx,C()=A(x)·B(x)=∑cnx Let's first evaluate the product A(a). B(ar)and express the coefficient cn in terms of the a and b coefficients. We can tabulate all of the terms in this product in a table a1.l a1bzl a1b1.2 a1b2. a300.0 Notice that all terms involving the same power of r lie on a/-sloped diagonal. Collecting these terms together, we find that the coefficient of z" in the product is Cn= abn +a1bn-1+a2bn-2+..+anbo

� � � 10 Generating Functions This is the same generating function that we obtained by using the Binomial Theorem. But this time around we translated directly from the counting problem to the generating function. We can extend these ideas to a general principle: Rule 5 (Convolution Rule). Let A(x) be the generating function for selecting items from set A, and let B(x) be the generating function for selecting items from set B. If A and B are disjoint, then the generating function for selecting items from the union A ∪ B is the product A(x) · B(x). This rule is rather ambiguous: what exactly are the rules governing the selection of items from a set? Remarkably, the Convolution Rule remains valid under many inter￾pretations of selection. For example, we could insist that distinct items be selected or we might allow the same item to be picked a limited number of times or any number of times. Informally, the only restrictions are that (1) the order in which items are selected is disregarded and (2) restrictions on the selection of items from sets A and B also apply in selecting items from A ∪ B. (Formally, there must be a bijection between n­element selections from A ∪ B and ordered pairs of selections from A and B containing a total of n elements.) Proof. Define: ∞ ∞ ∞ A(x) = anx n , B(x) = bnx n , C(x) = A( B(x) = cnx n x) · . n=0 n=0 n=0 Let’s first evaluate the product A(x) B(x) and express the coefficient cn · in terms of the a and b coefficients. We can tabulate all of the terms in this product in a table: b0x0 b1x1 b2x2 b3x3 . . . a0x0 a0b0x0 a0b1x1 a0b2x2 a0b3x3 . . . a1x1 a1b0x1 a1b1x2 a1b2x3 . . . a2x2 a2b0x2 a2b1x3 . . . a3x3 a3b0x3 . . . . . . . . . Notice that all terms involving the same power of x lie on a /­sloped diagonal. Collecting these terms together, we find that the coefficient of xn in the product is: cn = a0bn + a1bn−1 + a2bn−2 + · · · + anb0