Generating function

The idea behind generating functions is to create a power series whose coefficients, $c_0, c_1, c_2, \ldots$ , give the terms of a sequence which is of interest. Therefore the power series (i.e. the generating function) is $c_0 + c_1 x + c_2 x^2 + \cdots$ and the sequence is $c_0, c_1, c_2,\ldots$ .

Simple Example

If we let $A(k)={n \choose k}$ , then we have ${n \choose 0}+{n \choose 1}x + {n \choose 2}x^2+\cdots+$ ${n \choose n}x^n$ .

This function can be described as the number of ways we can get ${k}$ heads when flipping $n$ different coins.

The reason to go to such lengths is that our above polynomial is equal to $(1+x)^n$ (which is clearly seen due to the Binomial Theorem). By using this equation, we can rapidly uncover identities such as ${n \choose 0}+{n \choose 1}+...+{n \choose n}=2^n$ (let ${x}=1$ ), also ${n \choose 1}+{n \choose 3}+\cdots={n \choose 0}+{n \choose 2}+\cdots$ .

More Examples

Many generating functions can be derived using the sum formula for geometric series $\frac{1}{1-x} = \sum_{k=0}^{\infty} x^k = 1 + x + x^2 + x^3 + \dots$ for $x \in (-1,1)$ .

For example, using a change of variables, $\frac{1}{1-ax} = \sum_{k=0}^{\infty} (ax)^k = \sum_{k=0}^{\infty} a^kx^k = 1 + ax + a^2x^2 + a^3x^3 + \dots$ for $x \in \left( -\frac{1}{a}, \frac{1}{a} \right)$ (if $a > 0$ ) or $x \in \left( \frac{1}{a}, -\frac{1}{a} \right)$ (if $a < 0$ ), generating the powers of $a$ for any real $a$ . The identity holds for all $x$ when $a = 0$ , but the result is uninteresting (both the generating function and the desired power series are just $1$ ).

Taking the derivative and multiplying by $x$ gives a generating function for the nonnegative integers: $x \left( \frac{1}{1-x} \right) ' = \frac{x}{(1-x)^2} = \sum_{k=0}^{\infty} kx^k = 0 + x + 2x^2 + 3x^3 + \dots$ for $x \in (-1,1)$ .

Convolutions

Suppose we have the sequences $a_0, a_1, a_2, ...$ and $b_0, b_1, b_2, ...$ . We can create a new sequence, called the convolution of $a$ and $b$ , defined by $c_n = a_0b_n + a_1b_{n-1} + ... + a_nb_0$ . Generating functions allow us to represent the convolution of two sequences as the product of two power series. If $A$ is the generating function for $a$ and $B$ is the generating function for $b$ , then the generating function for $c$ is $AB$ .

Simple Exercises

1. There are three baskets on the ground: one has 2 purple eggs, one has 2 green eggs, and one has 3 white eggs. Eggs of the same color are indistinguishable. In how many ways can I choose 4 eggs from the baskets?

Solution for problem 1: The generating function for the first basket is $1+x+x^2$ , since there is one way to choose 0 purple eggs (do nothing), 1 way to choose 1 purple egg (since eggs are indistinguishable), and 1 way to choose 2 purple eggs. In a similar fashion the generating function for the green egg basket is $1+x+x^2$ and the generating function for the white egg basket is $1+x+x^2+x^3$ . Now to find the number of ways to pick eggs from multiple baskets, just simply multiply the functions together, getting $1+3x+6x^2+8x^3+8x^4+6x^5+3x^6+x^7$ . We want the number of ways to choose 4 eggs, so we just need to look at the coefficient of $x^4$ and see that there are 8 ways to choose 4 eggs.

External Link

generatingfunctionology

Page

Toolbox

Search