Generating Functions

For coverage of generating functions specific to Donald Knuth's Art of Computer Programming, see AOCP/Generating Functions.

Notes

Trotter

Chapter 8: Generating Functions

Alternative Generating Functions Introduction

An alternative way to approach generating functions: consider the problem of distributing apples among children.

We can even boil it down to a super simple case: distributing n apples among n children.

In this case, if there are no apples, the coeff is 0. If there is 1 apple, 1 way to distribute. If 2 apples, 1 way to distribute. Etc.

This makes the generating function:

$ x + x^2 + x^3 + \dots = x ( 1 + x + x^2 + x^3 + \dots) $

And this is, as we already know, equivalent to:

$ \dfrac{x}{1-x} = x + x^2 + x^3 + \dots $

Now consider the two-child case. We can get to that by multiplying two copies of the generating function together:

$ (x + x^2 + x^3 + \dots ) ( x + x^2 + x^3 + \dots ) $

Now in this case, there is no leading term (no zero-apples case), but there is also no one-apples case, either, since there is no way to obtain an x term. This corresponds to the scenario we have set up, in which each child must have one apple.

That is, when we defined the generating function, we defined the generating function such that if there are no apples, there are no possible configurations. This means that any child getting zero apples is not a possible configuration.

If we went back and changed the generating function to

$ 1 + z + z^2 + z^3 + \dots $

then we would end up with one possible configuration when there are zero apples. This would carry through, so that when there are two children, there is one possible configuration when there are zero apples (z = 0; the leading constant term is 1), and there are also two possible configurations (z + z = 2z) for the case when there is one apple (z = 1; the 2z term becomes 2).

So, as mentioned the series $ \sum_{k \geq 0} z^k $ contains no terms for the $ k=0 $ case, because each child must have 1 apple.

If we extend this to n children, we will multiply n copies of the original series. Consider the 5-child case:

$ (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) $

Here, the smallest term is $ z^5 $ which corresponds to a single possible configuration when there are five apples.

If we look at the term $ z^n $ this represents the number of ways we can distribute n apples among a certain number of children (the number of children determines the final form of the function, i.e., the structure of the problem; n just determines which coefficient of the function we're asking for, i.e., the size of the problem).

Therefore, the coefficient of $ x^n $ in our generating function represents the number of ways that we can combine the number of apples each child gets (indexed by k):

$ k_1 + k_2 + k_3 + \dots + k_i = n $

Suppose we have 6 apples. Then we are asking, how many ways can we distribute 6 apples among 5 children? This should be obvious - it is a question that we can answer with the binomial coefficient. However, if we think more deeply about this problem, we're asking how many ways we can combine 5 k's to get 6.

This comes from:

$ (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) $

so we can have

$ \{ z, z, z, z, z^2 \}, \{ z, z, z, z, z^2, z \}, \{ z, z, z, z^2, z, z \}, \dots $

which is 5 choose 1, or $ \binom{5}{1} = \binom{5}{4} $

We could also get this result through a little bit ore advanced use of calculus and derivatives: suppose that we replace the long expanded generating function with the shorter version, to get a generating function for the one-child case:

$ G_1 (z) = \dfrac{z}{1-z} $

and for the five-child case:

$ G_5(z) = \dfrac{z^5}{(1-z)^5} = z^5 \dfrac{1}{(1-z)^5} $

Now we can observe that the denominator can be obtained via:

$ \dfrac{d^n}{dz^n} \left( \dfrac{1}{1-z} \right) = \dfrac{n!}{(1-z)^{n+1}} $

so that

$ \dfrac{z^5}{(1-z)^5} = z^5 \left( \dfrac{1}{4!} \dfrac{d^4}{dz^4} \left( \dfrac{1}{1-z} \right) \right) $

now this can be simplified to

$ \dfrac{z^5}{4!} \left( \dfrac{d^4}{dz^4} \left( z + z^2 + z^3 + \dots \right) \right) $

Almost finished. Now we can use

$ \begin{align} \dfrac{d^4 G(z)}{d z^4} &=& \dfrac{d^4}{dz^4} \left( \sum_{n=1}^{\infty} z^n \right) \\ &=& \dfrac{d^4}{dz^4} \left( z + z^2 + z^3 + \dots \right) \\ &=& (n)(n-1)(n-2)(n-3)z^{n-4} \end{align} $