Chapter 17 Generating Functions Generating Functions are one of the most surprising and useful inventions in Dis-crete Math. Roughly speaking, generating functions transform problems about sequences into problems about functions. This is great because we’ve got piles of mathematical machinery for manipulating functions. Thanks to generating func-tions, 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 chapter, we’ll put sequences in angle brackets to more clearly distinguish them from the many other mathematical expressions floating around. The ordinary generating function for �g0, g1, g2, g3 . . . � is the power series: G(x) = g0 + g1x + g2x 2 + g3x 3 + ··· . There are a few other kinds of generating functions in common use, but ordinary generating functions are enough to illustrate the power of the idea, so we’ll stick to them. So from now on generating function will mean the ordinary kind. 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 actu-ally evaluate a generating function by letting x take a real number value, so we generally ignore the issue of convergence. Throughout this chapter, we’ll indicate the correspondence between a sequence and its generating function with a double-sided arrow as follows: �g0, g1, g2, g3, . . . � ←→ g0 + g1x + g2x 2 + g3x 3 + ··· For example, here are some sequences and their generating functions: �0, 0, 0, 0, . . . � ←→ 0 + 0x + 0x 2 + 0x 3 + = 0 ··· �1, 0, 0, 0, . . . � ←→ 1 + 0x + 0x 2 + 0x 3 + = 1 ··· �3, 2, 1, 0, . . . � ←→ 3 + 2x + 1x 2 + 0x 3 + = 3 + 2x + x 2 ··· 385386 CHAPTER 17. GENERATING FUNCTIONS The pattern here is simple: the ith 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: 11 + z + z 2 + z 3 + = ··· 1 − z This equation does not hold when |z| ≥ 1, but as remarked, we don’t worry about convergence issues. This formula gives closed form generating functions for a whole range of sequences. For example: 1 �1, 1, 1, 1, . . . � ←→ 1 + x + x2 + x3 + ··· =1 − x 1 �1, −1, 1, −1, . . . � ←→ 1 − x + x2 − x3 + x4 − ··· = 1 + x � � 11, a, a2, a3 , . . . 1 + ax + a2x2 + a3x3 + = ←→ ··· 1 − ax 1 �1, 0, 1, 0, 1, 0, . . . � ←→ 1 + x2 + x4 + x6 + ··· =1 − x2 17.1 Operations on Generating Functions The magic of generating functions is that we can carry out all sorts of manipu-lations on sequences by performing mathematical operations on their associated generating functions. Let’s experiment with various operations and characterize their effects in terms of sequences. 17.1.1 Scaling Multiplying a generating function by a constant scales every term in the associated sequence by the same constant. For example, we noted above that: 1 �1, 0, 1, 0, 1, 0, . . . � ←→ 1 + x 2 + x 4 + x 6 + ··· =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, . . . �� � � � � � � 17.1. OPERATIONS ON GENERATING FUNCTIONS 387 Rule 11 (Scaling Rule). If �f0, f1, f2, . . . � ←→ F (x), then �cf0, cf1, cf2, . . . � ←→ c F (x).· The idea behind this rule is that: �cf0, cf1, cf2, . . . � ←→ cf0 + cf1x + cf2x 2 + ··· = c (f0 + f1x + f2x 2 + )· ··· = cF (x) 17.1.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, . . . �. They are, of course, equal: 1 + 1 =(1 + x) + (1 − x)= 2 1 − x 1 + x (1 − x)(1 + x) 1 − x2 Rule 12 (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). The idea behind this rule is that: ∞�f0 + g0, f1 + g1, f2 + g2, . . . � ←→ (fn + gn)x n n=0 ∞ ∞= fnx n + gnx n n=0 n=0 = F (x) + G(x)� �� � � � 388 CHAPTER 17. GENERATING FUNCTIONS 17.1.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: �0, 0, . . . , 0, 1, 1, 1, . . . � x k + x k+1 + x k+2 + x k+3 + � �� � ←→ ··· k zeroes = x k (1 + x + x 2 + x 3 + )· ··· kx= 1 − x Evidently, adding k leading zeros to the sequence corresponds to multiplying the generating function by xk. This holds true in general. Rule 13 (Right-Shift Rule). If �f0, f1, f2, . . . � ←→ F (x), then: �0, 0, . . . , 0, f0, f1, f2, . . . � ←→ x k F (x)� �� � · k zeroes The idea behind this rule is that: k zeroes �0, 0, . . . , 0, f0, f1, f2, . . . � ←→ f0x k + f1x k+1 + f2x k+2 + ··· = x k (f0 + f1x + f2x 2 + f3x 3 + )· ··· = x k F (x)· 17.1.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. …
View Full Document
Unlocking...