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} $

Just to take this example one step further, let's suppose we decide that no child can get more than 4 apples. Then the generating function for each child will terminate after 4 terms (any term beyond that represents the case where a child has more than 4 apples and therefore we do not have any possibilities) and will be:

$ G(z) = z + z^2 + z^3 + z^4 $

Example with Complicated Restrictions

Let's look at an example that uses less trivial restrictions.

Suppose we are preparing cans of marbles. Each can of marbles will have 20 red, blue, or green marbles. How many different outcomes are there if we require each jar have at least 1 red marble, no more than three blue marbles, any number of yellow marbles, and the number of green marbles must be a multiple of 4?

We begin this problem by starting with an easier problem: let's count the number of outcomes if we put n marbles into each can. We'll create a generating function whose coefficients give this number, and we can then find the 20th coefficient. As with the generating functions above, the term $ z^6 $ corresponds to six marbles in each can, and the coefficient indicates the number of different ways that our three k values $ k_{r}, k_{b}, k_{y}, k_{g} $ can be combined to get 6.

Now, to write the generating functions for each marble, given our various restrictions:

Start with red, which is easiest - we require at least one red marble, so the case of $ z^0 $ must correspond to 0 outcomes for red.

$ \begin{align} G_{r}(z) &=& z + z^2 + z^3 + z^4 + \dots \\ G_{r}(z) &=& z ( 1+z+z^2+\dots) \\ G_{r}(z) &=& z \left( \dfrac{1}{1-z} \right) \end{align} $

so finally we get our generating function for red:

$ G_{r}(z) = \dfrac{z}{1-z} $

Next, for blue, we require that we have no more than three blue marbles, so any terms larger than $ z^3 $ will be 0:

$ G_{b}(z) = 1 + z + z^2 + z^3 $

Yellow marbles can be any number:

$ G_{y}(z) = 1 + z + z^2 + z^3 + \dots $

Green marbles are a bit more tricky - we require they only occur in multiples of four, which means the coefficients of the generating function are nonzero only when the degree is divisible by 4:

$ G_{g}(z) = 1 + z^4 + z^8 + z^{12} + \dots $

Notice that we can do a variable transformation $ u = z^4 $, and this becomes the generating function:

$ G_{g}( \sqrt[4]{u} ) = 1 + u + u^2 + u^3 + \dots $

Now, this becomes:

$ G_{g}( \sqrt[4]{u} ) = \dfrac{1}{1-u} $

and undoing our substitution $ u = z^4 $ gives:

$ G_{g}(z) = \dfrac{1}{1 - z^4} $

Now the generating function for the entire lot is:

$ G(z) = G_r G_b G_y G_g = \dfrac{z}{1-z} \left( 1 + z + z^2 + z^3 \right) \dfrac{1}{1-z^4} \dfrac{1}{1-z} $

Simplifying with Mathematica or Wolfram Alpha:

$ G(z) = \dfrac{z}{(1-z)^3} $

Analysis of Generating Function

One step, at this point, is to find the Taylor Series expansion of this expression, which would give us our coefficients and the counts of different configurations. We will do that in the next section. However, we can do further analysis to get expressions for the coefficients analytically.

First, we can associate the $ (1-z)^3 $ on the bottom to the sum $ 1+x+x^2+\dots $ via the derivative:

$ \dfrac{d^2}{dx^2} \left( \dfrac{1}{1-x} \right) = \dfrac{2}{(1-x)^3} $

and recall that this gives us a link to an infinite series, because $ \dfrac{1}{1-x} = 1 + x + x^2 + \dots $, as we have seen many times thus far.

So, we can replace the derivative term with an infinite sum:

$ \dfrac{d^2}{dx^2} \left( \dfrac{1}{1-x} \right) = \sum_{n=0}^{\infty} n (n-1) x^{n-2} $

and this gives us the generating function in terms of a sum:

$ G(z) = \dfrac{x}{2} \sum_{n=0}^{\infty} n (n-1) x^{n-2} $

Why do all of this? The next steps give us the payoff: we get a closed form for the coefficients.

$ G(z) = x \sum_{n=0}^{\infty} \dfrac{n(n-1)}{2} x^{n-2} $

Notice the triangle number $ \dfrac{n(n-1)}{2} $, which we will see crop up in the next section. The triangle number in that form, $ \dfrac{n(n-1)}{2} $, rather than its usual form $ \frac{n(n+1)}{2} $ (which gives the sum of the integers from 1 to n), indicates that this is a binomial coefficient. Recall from AOCP/Binomial Coefficients that:

$ \binom{n}{2} = \dfrac{n(n-1)}{2} $

Thus, if we bring the x inside the infinite sum and simplify the expression, we get:

$ G(z) = \sum_{n=0}^{\infty} \binom{n}{2} x^{n-1} $

Last, we do a variable shift with the infinite series, shift n up by one, which pops out a 0 term, and write:

$ G(z) = \sum_{n=1}^{\infty} \binom{n+1}{2} x^{n} $

or equivalently,

$ G(z) = \sum_{n=1}^{\infty} \binom{n+1}{2} x^{n} $

Now we can give the closed-form answer to the question: How many fruit baskets are there? (n+1) choose 2. For a can of 20 marbles, that's:

$ 21 \mbox{ choose } 2 = 210 $

Indeed, this is a lot nicer than just using Mathematica, but Mathematica certainly scales better:

Taylor Series Analysis

Now, we can use this generating function to explore the possibilities in our system. Here's the Taylor Series expansion to the first 10 terms:

$ G(z) = z+3 z^2+6 z^3+10 z^4+15 z^5+21 z^6+28 z^7+36 z^8+45 z^9+55 z^{10}+O\left(z^{11}\right) $

We can actually verify the first few terms.

The case of the z term (k=1 marbles). Let us first examine the z term (k=1 marble). When we have a single marble, there is only one configuration that works, and that is the case of a single red marble. No other marbles are required, strictly speaking. Thus the coefficient is 1.

The case of the z^2 term (k=2 marbles). The case of 2 marbles is more interesting: one slot has to be occupied by a red marble, so the remaining slot can be occupied by a red marble, a blue marble, a yellow marble, or a green marble. But green marbles can only occur in multiples of 4, so they're out. That leaves 3 possible configurations:

RR, RB, RY

The case of the z^3 term (k=3 marbles). If we have 3 marbles, we must have one slot occupied by a red marble. The remaining slots can be occupied by red, blue, or yellow marbles. Green marbles are still out. This gives 3 additional possibilities, added to the prior 3 possibilities, for 6 total:

RRR
RRB
RRY

RBB
RBY

RYY

Notice the way that the configurations are arranged - in groups of size 3, 2, 1. The total possibilities are 3 + 2 + 1 = 6, which is a triangle number.

Another way to think about this is, we are selecting from a set of 3 colored marbles, which one to put in each spot. Each spot sees the same set of 3 colored marbles, so this is different from saying 3 marbles (RYB) are going into two slots. It is actually like saying, when we choose what color to put into the first slot we are choosing from three marbles (RYB), and when we choose what color to put into the second slot we are also choosing from three marbles (RYB).

The case of the z^4 term (k=4 marbles). This configuration has 10 possibilities. 10 is a triangle number - just like 6.

RRRR
RRRB
RRRY

RRBB
RRBY

RRYY

RBBB
RBBY

RBYY

RYYY

Again, notice the configuration arrangements: (3 + 2 + 1) + (2 + 1) + (1) = 4 + 3 + 2 + 1

These numbers are coming from the term in the Taylor Series analysis we did above:

$ \sum_{n=0}^{\infty} \binom{n+1}{2} x^n $

If we have a term like k-choose-2, that will result in the (k-1)th triangle number. In this case, we have a term (n-1)-choose-2, which will give us the nth triangle numbers. That's why, when we had 3 marbles, we got the 3rd triangle number, when we had 4 marbles, we had the 4th triangle number, etc.

Trotter: Chapter 8 Exercises

Problem 3

In problem 3, we're given some generating functions, and asked to find a closed form for the nth term.

Part a

$ G(x) = (1 + x)^{10} $

Solving this one is as simple as applying the binomial theorem:

$ \begin{align} (1+x)^n &=& \sum_{k=1}^{n} \binom{n}{k} x^k \\ (x+y)^n &=& \sum_{k=1}^{n} \binom{n}{k} x^k y^{n-k} \end{align} $

So the nth term will be:

$ \binom{10}{n} $

Part b

$ G(x) = \dfrac{1}{1-x^4} $

Not sure if there is an easier way to solve this one, but here's the method I used. Start by factoring this as $ (1-x^4) = (1-x)(1+x)(1+x^2) $, then do a partial fractions decomposition:

$ \dfrac{1}{4} \dfrac{1}{1-x} + \dfrac{1}{4} \dfrac{1}{1+x} + \dfrac{1}{2} \dfrac{1}{1+x^2} $

Now the goal is to combine these terms into a single series by re-expressing each expression with x in it in terms of $ \dfrac{1}{1-x} = 1 + x + x^2 + x^3 + \dots = \sum_{k \geq 0} x^k $, using various tricks shown above and from calculus.

The first term is simple enough:

$ \dfrac{1}{4} \dfrac{1}{1-x} = \dfrac{1}{4} \left( \sum_{k \geq 0}{x^k} \right) $

The second term can be written as a series in (-x):

$ \dfrac{1}{4} \dfrac{1}{1+x} = \dfrac{1}{4} \dfrac{1}{1-(-x)} = \dfrac{1}{4} ( 1 + (-x) + (-x)^2 + (-x)^3 + \dots) = \dfrac{1}{4} \sum_{k \geq 0} (-1)^k x^k $

The last term is a bit challenging. I used Wolfram Alpha to get a series expansion for this function. Here it is:

$ \dfrac{1}{1+x^2} = 1 - x^2 + x^4 - x^6 + x^8 - \dots $

Converting this to a series expression requires some imaginary numbers to eliminate the odd terms of the series. We have:

$ \dfrac{1}{1+x^2} = \sum_{k \geq 0} \dfrac{1}{2} x^k ((-i)^k + i^k) $

where $ i = \sqrt{-1} $.

These three terms can now be combined:

$ G(x) = \dfrac{1}{1-x^4} = \dfrac{1}{4} \left( \sum_{k \geq 0} x^k + \sum_{k \geq 0} (-1)^k x^k + \sum_{k \geq 0} x^k ((-i)^k + (i)^k) \right) $

which becomes

$ G(x) = \dfrac{1}{4} \left( \sum_{k \geq 0} \left( 1 + (-1)^k + ((-i)^k + (i)^k) \right) \right) $

(This is technically the final answer.)

Let's interpret this result a bit more.

Notice that the imaginary terms $ ((-i)^k+(i)^k) $ ensure the series has no odd values of k. For even values of k, the term has an alternating value of +2 or -2. Specifically, if k is divisible by 4 (0 mod 4), we have a value of +2, and if k is 2 mod 4, we have a value of -2.

The term $ 1 + (-1)^k $ will be +2 when k is even and 0 otherwise, so this contributes no odd terms to the series.

Since there are no odd terms and the values of k that are 2 mod 4 cancel out, we are left with:

$ G(x) = \sum_{k \geq 0} x^4k $

So the entire series looks like:

$ G(x) = 1 + x^4 + x^8 + x^12 + x^16 + \dots $

Part c

In part c we have the complement function to part b, so hold on to your hats.

$ G(x) = \dfrac{x^3}{1-x^4} = \dfrac{x^3}{(1-x)(1+x)(1+x^2)} $

The first two terms of the partial fraction expansion are the same as in part b:

$ \dfrac{x^3}{(1+x)(1-x)(1+x^2)} = \dfrac{1}{4} \dfrac{1}{1-x} - \dfrac{1}{4} \dfrac{1}{1+x} - \dfrac{x}{2(1+x^2)} $

The first two terms become:

$ \dfrac{1}{4} \dfrac{1}{1-x} - \dfrac{1}{4} \dfrac{1}{1+x} = \dfrac{1}{4} \left( \sum_{k \geq 0} \left( 1 - (-1)^k \right) x^k \right) $

The last term is a series that, analogous to the one from part b, has only odd terms; however, its Taylor series expansion is substantially more hairy:

$ \dfrac{x}{1+x^2} = x-x^3+x^5-x^7+x^9-x^{11}+x^{13} - \dots $

$ \dfrac{x}{1+x^2} = \sum_{k \geq 0} (-1)^k (1-x)^k (1+i) ( 2^{-2-k} ( (-1-i)^k -i(1+i)^k ) ) $