|
|
| (5 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| =Knuth: Volume 1: Fundamental Algorithms=
| | #REDIRECT [[AOCP/Generating Functions]] |
| | |
| ==Chapter 1: Basic Concepts: Generating Functions==
| |
| | |
| You absolutely, positively must read the preceding chapters to follow Knuth here. There are a number of subtle steps that he moves through quite fast, about as quickly as he moves through the other material, except he's now integrating his method of presenting all 8 prior sections, including both explicit and passing references to prior material.
| |
| | |
| As with the binomial coefficients...
| |
| | |
| | |
| | |
| | |
| =Example Problems=
| |
| | |
| ==Knuth AOCP Section 1.2.9 Exercise 1==
| |
| | |
| '''Exercise 1.''' What is the generating function for <math><2^n + 3^n> = \{ 2, 5, 13, 35, \dots \}</math>?
| |
| | |
| For this problem, don't be fooled by the complexity of the preceding section - it's back to the basics. This sequence of numbers looks a lot like, oh, I dunno, two sequences of numbers added together. Specifically,
| |
| | |
| <pre>
| |
| 2 4 8 16 32
| |
| 3 9 27 81 243
| |
| </pre>
| |
| | |
| If we can find the generating function for 2^n, and find the generating function for 3^n, we can use the addition property of generating functions to combine them.
| |
| | |
| To find the generating function for <math>2^n</math>:
| |
| | |
| <math>
| |
| \begin{align}
| |
| G_{2^n}(z) &=& 1 + 2z + 4z^2 + \dots \\
| |
| z G_{2^n}(z) &=& 0 + z + 2z^2 + \dots \\
| |
| 2z G_{2^n}(z) &=& 0 + 2z + 4z^2 + \dots
| |
| \end{align}
| |
| </math>
| |
| | |
| Now subtracting the first and last quantities gives:
| |
| | |
| <math>
| |
| (1-2z) G_{2^n}(z) = 1 + 0 + 0 + 0 + \dots
| |
| </math>
| |
| | |
| which yields the generating function for <math>2^n</math>:
| |
| | |
| <math>
| |
| G_{2^n}(z) = \dfrac{1}{1 - 2z}
| |
| </math>
| |
| | |
| Repeating the process for <math>3^n</math> gives:
| |
| | |
| <math>
| |
| G_{3^n}(z) = \dfrac{1}{1 - 3z}
| |
| </math>
| |
| | |
| Now to get the overall generating function for <math><2^n + 3^n></math> we add these two functions together and combine into a single rational expression:
| |
| | |
| <math>
| |
| G(z) = \dfrac{1}{1-2z} + \dfrac{1}{1 - 3z} = \dfrac{2-5x}{1-5x+6x^2}
| |
| </math>
| |
| | |
| Now for the cool part. If we do a Taylor Series expansion of <math>G(z)</math>, we can compute <math>2^n + 3^n</math> simply by obtaining the <math>n^{th}</math> coefficient of the Taylor Series polynomial. While this may seem like a pointless mathematical trick for a function like <math>2^n + 3^n</math>, the real utility of the method comes when we apply this approach to much more general functions.
| |