Combinatorics (Fall 2010)/Generating functions

Generating Functions

In Stanley's magnificent book Enumerative Combinatorics, he comments the generating function as "the most useful but most difficult to understand method (for counting)".

The solution to a counting problem is usually represented as some [math]\displaystyle{ a_n }[/math] depending a parameter [math]\displaystyle{ n }[/math]. Sometimes this [math]\displaystyle{ a_n }[/math] is called a counting function as it is a function of the parameter [math]\displaystyle{ n }[/math]. [math]\displaystyle{ a_n }[/math] can also be treated as a infinite series:

[math]\displaystyle{ a_0,a_1,a_2,\ldots }[/math]

The ordinary generating function (OGF) defined by [math]\displaystyle{ a_n }[/math] is

[math]\displaystyle{ G(x)=\sum_{n\ge 0} a_nx^n. }[/math]

So [math]\displaystyle{ G(x)=a_0+a_1x+a_2x^2+\cdots }[/math]. An expression in this form is called a formal power series, and [math]\displaystyle{ a_0,a_1,a_2,\ldots }[/math] is the sequence of coefficients.

Furthermore, the generating function can be expanded as

G(x)=[math]\displaystyle{ (\underbrace{1+\cdots+1}_{a_0})+(\underbrace{x+\cdots+x}_{a_1})+(\underbrace{x^2+\cdots+x^2}_{a_2})+\cdots+(\underbrace{x^n+\cdots+x^n}_{a_n})+\cdots }[/math]

so it indeed "generates" all the possible instances of the objects we want to count.

Usually, we do not evaluate the generating function [math]\displaystyle{ GF(x) }[/math] on any particular value. [math]\displaystyle{ x }[/math] remains as a formal variable without assuming any value. The numbers that we want to count are the coefficients carried by the terms in the formal power series. So far the generating function is just another way to represent the sequence

[math]\displaystyle{ (a_0,a_1,a_2,\ldots\ldots) }[/math].

The true power of generating functions comes from the various algebraic operations that we can perform on these generating functions. We use an example to demonstrate this.

Fibonacci numbers

Consider the following counting problems.

• Count the number of ways that the nonnegative integer [math]\displaystyle{ n }[/math] can be written as a sum of ones and twos (in order).

The problem asks for the number of compositions of [math]\displaystyle{ n }[/math] with summands from [math]\displaystyle{ \{1,2\} }[/math]. Formally, we are counting the number of tuples [math]\displaystyle{ (x_1,x_2,\ldots,x_k) }[/math] for some [math]\displaystyle{ k\le n }[/math] such that [math]\displaystyle{ x_i\in\{1,2\} }[/math] and [math]\displaystyle{ \sum_{i=1}^k x_i=n }[/math].

Let [math]\displaystyle{ F_n }[/math] be the solution. We observe that a composition either starts with a 1, in which case the rest is a composition of [math]\displaystyle{ n-1 }[/math]; or starts with a 2, in which case the rest is a composition of [math]\displaystyle{ n-2 }[/math]. So we have the recursion for [math]\displaystyle{ F_n }[/math] that

[math]\displaystyle{ F_n=F_{n-1}+F_{n-2} }[/math].

• Count the ways to completely cover a [math]\displaystyle{ 2\times n }[/math] rectangle with [math]\displaystyle{ 2\times 1 }[/math] dominos without any overlaps.

Dominos are identical [math]\displaystyle{ 2\times 1 }[/math] rectangles, so that only their orientations --- vertical or horizontal matter.

Let [math]\displaystyle{ F_n }[/math] be the solution. It also holds that [math]\displaystyle{ F_n=F_{n-1}+F_{n-2} }[/math]. The proof is left as an exercise.

In both problems, the solution is given by [math]\displaystyle{ F_n }[/math] which satisfies the following recursion.

[math]\displaystyle{ F_n=\begin{cases} 0 & \mbox{if }n=0\\ 1 & \mbox{if }n=1\\ F_{n-1}+F_{n-2} & \mbox{if}n\ge 2. \end{cases} }[/math]

[math]\displaystyle{ F_n }[/math] is called the Fibonacci number.

Theorem

[math]\displaystyle{ F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right) }[/math], where [math]\displaystyle{ \phi=\frac{1+\sqrt{5}}{2} }[/math] and [math]\displaystyle{ \hat{\phi}=\frac{1-\sqrt{5}}{2} }[/math].

The quantity [math]\displaystyle{ \phi=\frac{1+\sqrt{5}}{2} }[/math] is the so-called golden ratio, a constant with some significance in mathematics and aesthetics.

We now prove this theorem by using generating functions.

The ordinary generating function for the Fibonacci number [math]\displaystyle{ F_{n} }[/math] is

[math]\displaystyle{ G(x)=\sum_{n\ge 0}F_n x^n }[/math].

We have that [math]\displaystyle{ F_{n}=F_{n-1}+F_{n-2} }[/math] for [math]\displaystyle{ n\ge 2 }[/math], thus

[math]\displaystyle{ \begin{align} G(x) &= \sum_{n\ge 0}F_n x^n &= x+\sum_{n\ge 2}(F_{n-1}+F_{n-2})x^n. \end{align} }[/math]

For generating functions, there are general ways to generate [math]\displaystyle{ F_{n-1} }[/math] and [math]\displaystyle{ F_{n-2} }[/math], or the coefficients with any smaller indices.

[math]\displaystyle{ \begin{align} xG(x) &=\sum_{n\ge 0}F_n x^{n+1}=\sum_{n\ge 1}F_{n-1} x^n=\sum_{n\ge 2}F_{n-1} x^n\\ x^2G(x) &=\sum_{n\ge 0}F_n x^{n+2}=\sum_{n\ge 2}F_{n-2} x^n. \end{align} }[/math]

So we have

[math]\displaystyle{ G(x)=x+(x+x^2)G(x)\, }[/math],

hence

[math]\displaystyle{ G(x)=\frac{x}{1-x-x^2} }[/math].

The value of [math]\displaystyle{ F_n }[/math] is the coefficient of [math]\displaystyle{ x^n }[/math] in the Taylor series for this formular, which is [math]\displaystyle{ \frac{G^{(n)}(0)}{n!}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n }[/math]. Although this expansion works in principle, the detailed calculus is rather painful.

---

There is an easier way to get this coefficient than directly expanding the Taylor series.

[math]\displaystyle{ 1-x-x^2 }[/math] has two roots [math]\displaystyle{ \frac{-1\pm\sqrt{5}}{2} }[/math].

Denote that [math]\displaystyle{ \phi=\frac{2}{-1+\sqrt{5}}=\frac{1+\sqrt{5}}{2} }[/math] and [math]\displaystyle{ \hat{\phi}=\frac{2}{-1-\sqrt{5}}=\frac{1-\sqrt{5}}{2} }[/math]. Then [math]\displaystyle{ (1-x-x^2)=(1-\phi x)(1-\hat{\phi}x) }[/math], so we can write

[math]\displaystyle{ \begin{align} \frac{x}{1-x-x^2} &=\frac{x}{(1-\phi x)(1-\hat{\phi} x)}\\ &=\frac{\alpha}{(1-\phi x)}+\frac{\beta}{(1-\hat{\phi} x)}, \end{align} }[/math]

where [math]\displaystyle{ \alpha }[/math] and [math]\displaystyle{ \beta }[/math] satisfying that

[math]\displaystyle{ \begin{cases} \alpha+\beta=0\\ \alpha\phi+\beta\hat{\phi}= -1. \end{cases} }[/math]

Solving this we have that [math]\displaystyle{ \alpha=\frac{1}{\sqrt{5}} }[/math] and [math]\displaystyle{ \beta=-\frac{1}{\sqrt{5}} }[/math]. And

[math]\displaystyle{ G(x)=\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\phi x}-\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\hat{\phi} x} }[/math]

where [math]\displaystyle{ \phi=\frac{1+\sqrt{5}}{2} }[/math] and [math]\displaystyle{ \hat{\phi}=\frac{1-\sqrt{5}}{2} }[/math].

Note that the expression [math]\displaystyle{ \frac{1}{1-z} }[/math] has a well known expansion:

[math]\displaystyle{ \frac{1}{1-z}=\sum_{n\ge 0}z^n }[/math].

Therefore, [math]\displaystyle{ G(x) }[/math] can be expanded as

[math]\displaystyle{ \begin{align} G(x) &=\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\phi x}-\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\hat{\phi} x}\\ &=\frac{1}{\sqrt{5}}\sum_{n\ge 0}(\phi x)^n-\frac{1}{\sqrt{5}}\sum_{n\ge 0}(\hat{\phi} x)^n\\ &=\sum_{n\ge 0}\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)x^n. \end{align} }[/math]

So the [math]\displaystyle{ n }[/math]th Fibonacci number is given by

[math]\displaystyle{ F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n }[/math].

Solving recurrences

In the above analysis of Fibonacci numbers, we apply a general methodology which utilize the tools of generating functions to solve recurrence. The methodology can be concluded as follows.

1. Give a recursion that computes [math]\displaystyle{ a_n }[/math]; that is, an equation expressing [math]\displaystyle{ a_n }[/math] in terms of other elements of the sequence, such as

[math]\displaystyle{ a_n=f(a_0,a_1,\ldots,a_{n-1}) }[/math] for some function [math]\displaystyle{ f }[/math].

2. Multiply both sides of the equation by [math]\displaystyle{ x^n }[/math] and sum over all [math]\displaystyle{ n }[/math]. This gives the generating function

[math]\displaystyle{ G(x)=\sum_{n\ge 0}a_nx^n=\sum_{n\ge 0}f(a_0,a_1,\ldots,a_{n-1})x^n }[/math].

And manipulate the right hand side of the equation so that it becomes some other expression involving [math]\displaystyle{ G(x) }[/math].

3. Solve the resulting equation to derive an explicit formula for [math]\displaystyle{ G(x) }[/math].

4. Expand [math]\displaystyle{ G(x) }[/math] into a power series and read off the coefficient of [math]\displaystyle{ x^n }[/math], which is a closed form for [math]\displaystyle{ a_n }[/math].

The second step is somehow tricky. It involves first applying the recurrence to the coefficients of [math]\displaystyle{ G(x) }[/math], which is easy, and then manipulate the resulting formal power series to express it in terms of [math]\displaystyle{ G(x) }[/math], which is more difficult (because it works backwards).

We have several manipulation rules for the formal power series.

Generating function manipulation

Let [math]\displaystyle{ G(x)=\sum_{n\ge 0}g_nx^n }[/math] and [math]\displaystyle{ F(x)=\sum_{n\ge 0}f_nx^n }[/math]. [math]\displaystyle{ \begin{align} x^k G(x) &= \sum_{n\ge k}g_{n-k}x^n, &\qquad (\mbox{integer }k\ge 0)\\ \frac{G(x)-\sum_{i=0}^{k-1}g_iz^i}{x^k} &=\sum_{n\ge 0}g_{n+k}x^n, &\qquad (\mbox{integer }k\ge 0)\\ \alpha F(x)+\beta G(x) &= \sum_{n\ge 0} (\alpha f_n+\beta g_n)x^n\\ F(x)G(x) &= \sum_{n\ge 0}\sum_{k=0}^nf_kg_{n-k}x^n\\ G(cx) &= \sum_{n\ge 0} c^ng_n x^n\\ G'(x) &= \sum_{n\ge 0}(n+1)g_{n+1}x^n\\ \frac{G(x)}{1-x} &=\sum_{n\ge 0}\left(\sum_{k=0}^ng_k\right)x^n \end{align} }[/math]