《Mathematics for Computer》Generating functions

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

团购合买资源类别：文库，文档格式：PDF，文档页数：13，文件大小：276.13KB

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 sequences into problems about functions. This is great because we’ve got piles of mathematical 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 doublesided 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 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: 1 3 1 + z + z 2 + z + · · · = 1 − z

� � � � � � � 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 nth 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 nth Fibonacci number. So our next task is to extract coefficients from a generating function. There are several 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 partial 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)

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 Theorem: �� 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 kelement set. For example, the coefficient of x2 is , the number of ways to 2 choose 2 items from a kelement set. Similarly, the coefficient of xk+1 is the number of ways to choose k + 1 items from a kelement 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 kelement subset without resorting to the Binomial Theorem or even fussing with binomial coefficients! Here is how. First, consider a singleelement 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 elements. Repeated application of this rule gives the generating function for choosing n items from a kelement 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}

点击进入文档下载页（PDF格式）

共13页，试读已结束，阅读完整版请下载

点击下载（PDF格式）

浏览记录