Mathematics for Computer Science
15.2. Counting with Generating Functions 633 (see Problem 15.5), so Œxnç 1 .1x/k D dn dnx 1 .1x/k .0/ 1 nŠ D k.kC1/.k ...
Chapter 15 Generating Functions634 15.2.6 An Absurd Counting Problem So far everything we’ve done with generating functions we c ...
15.3. Partial Fractions 635 The Convolution Rule says that the generating function for choosing from among all four kinds of fru ...
Chapter 15 Generating Functions636 We can use the quadratic formula to find the rootsr 1 ;r 2 of the denominator, 1 xx^2. r 1 D ...
15.3. Partial Fractions 637 Each term in the partial fractions expansion has a simple power series given by the geometric sum fo ...
Chapter 15 Generating Functions638 15.4 Solving Linear Recurrences 15.4.1 A Generating Function for the Fibonacci Numbers The Fi ...
15.4. Solving Linear Recurrences 639 Figure 15.1 The initial configuration of the disks in the Towers of Hanoi problem. 15.4.2 T ...
Chapter 15 Generating Functions640 1 2 3 4 5 6 7 Figure 15.2 The 7-step solution to the Towers of Hanoi problem when there are n ...
15.4. Solving Linear Recurrences 641 Stage 2. Move the largest disk from the first post to the third post. This takes just 1 ste ...
Chapter 15 Generating Functions642 Reasoning as we did for the Fibonacci recurrence, we have T.x/ D t 0 C t 1 x C C tnxnC ...
15.5. Formal Power Series 643 used above to derive generating functions for the Fibonacci and Tower of Hanoi examples carries ov ...
Chapter 15 Generating Functions644 To prove this identity, note that from (15.16), we have ŒxnçH.x/WWDnnŠD.nC1/ŠnŠDŒxnç F.x/ ...
15.5. Formal Power Series 645 These operations on infinite sequences have lots of nice properties. For example, it’s easy to che ...
Chapter 15 Generating Functions646 In the ring of formal power series, equation (15.20) implies that the zero se- quenceZhas no ...
15.6. References 647 Problem 15.2. What is the coefficient ofxnin the generating function 1 Cx .1x/^2 ‹ Problems for Section 15. ...
Chapter 15 Generating Functions648 Class Problems Problem 15.5. LetA.x/D P 1 nD 0 anx n. Then it’s easy to check that anD A.n/.0 ...
15.6. References 649 (c)Write the generating function for the number of ways to use only nickels and pennies to changencents. (d ...
Chapter 15 Generating Functions650 She brings a positive number of songbirds, which always come in pairs. She may or may not ...
15.6. References 651 LetTnbe the number of different combinations ofnmishaps that Dan can suffer in one day (where we regard dif ...
Chapter 15 Generating Functions652 (b)Letgnbe the the number of different ways for T-Pain to bringnitems (burg- ers, pairs of fl ...
«
28
29
30
31
32
33
34
35
36
37
»
Free download pdf