Tuesday, March 25, 2014 CC-BY-NC
Catalan numbers continued, generating functions

Maintainer: admin

Some more things counted by the Catalan numbers. Introduction to generating functions, and some examples of how to use them.

1Things counted by the Catalan numbers

There are over 200 distinct categories of things that can be counted by the Catlan numbers. We'll only study a few in this course.

1.1Plane trees on $n+1$ vertices

Basically, trees of $n+1$ vertices where the order in which the children are drawn matters.

To show that there is a bijection between this and the Catalan numbers of length $n$, we perform a DFS on such a tree, starting from the root, and create a Catalan number in the process: every time we move downward (away from the root), we append a + to our Catalan number, and every time we move up (towards the root), we append a -. so there's a 1:1 mapping from the tree to the Catalan sequence of +'s and -'s representing its DFS, and vice versa.

1.2Planted trivalent trees with $2n+2$ vertices

A planted tree is one where the root has degree one, and a trivalent tree is one where each node has degree either 1 or 3. To show that there is a bijection between planted, trivalent trees with $2n+2$ vertices and the Catalan numbers of length $n$, we first remove the leaves, then perform a DFS from the root. Every time we reach a vertex, we append a + to our Catalan number; every time we move right, we append a -. Note that these trees are essentially binary trees, due to the trivalent condition.

1.3Decomposition of a polygon into triangles

Consider the problem of decomposing a polygon of $(n+2)$ sides into $n$ triangles using $n-1$ non-intersecting diagonals. We can create a bijection between this and the problem of planted, trivalent trees on $2n+2$ vertices above. Left as an exercise for the reader.

1.4Covering $\{1, 2, \ldots, n\}$ with non-comparable intervals

Suppose we want to cover the set $\{1, 2, \ldots, n \}$ using intervals that are not subsets of each other. Left as an exercise for the reader.

2Generating functions

Let $f(n)$ be the number of objects of size $n$. Then, the ordinary generating function is given by

$$F(x) = \sum_{n \geq 0} f(n) \cdot x^n$$

and the exponential generating function is given by

$$F(x) = \sum_{n \geq 0} f(n) \cdot \frac{x^n}{n!}$$

2.1Examples

If $S(n)$ is the number of subsets of a set of size $n$, then

$$S(x) = \sum_{n \geq 0} S(n) \cdot x^n = \sum_{n \geq 0} 2^n x^n = \sum_{n \geq 0} (2x)^n = \frac{1}{1-2x}$$

If $t(n)$ is the number of distinct labelled trees on $n$ vertices, then

$$T(x) = \sum_{n \geq 0} t(n) \cdot x^n = \sum_{n \geq 0} n^{n-2} \cdot x^n = ?$$

2.2Using recurrence relations

(A) Find a recursive function for $f(n)$ (remember the base case!)
(B) Multiply both sides of the recurrence by $x^n$ and sum over those values of $n$ where the recurrence holds
(C) Solve the resulting equation to find $f(x)$ (e.g., by partial fractions)
(D) Find $f(n)$ from $F(x)$

2.2.1Tower of Hanoi example

Tower of Hanoi: $n$ disks, 3 stands, no disk can be on top of a disk that is smaller than itself. Let $h(n)$ be the smallest number of moves required to get all the disks from stack 1 to stack 2, using stack 3 for temporary moves.

It's not hard to see that when we move the largest disk to stack 2, all the other disks should be in stack 3.

The procedure is as follows:

  1. Move $n-1$ smaller disks to stack 3. This takes $h(n-1)$ steps.
  2. Move the largest disk to stack 2. This takes one step.
  3. Move $n-1$ smaller disks from stack 3 to stack 2. This takes $h(n-1)$ steps.

Thus, for step (A), we have:

$$h(n) = 2h(n-1) + 1$$

For step (B), we try to remove the summation from our expression for $H(x)$:

$$\begin{align} H(x) & = \sum_{n \geq 0} h(n)\cdot x^n = h(0) \cdot x^0 + \sum_{n \geq 1} h(n) \cdot x^n \\ & = 0 + \sum_{n \geq 1} (2h(n-1) + 1)\cdot x^n \tag{using our expression for $h(n)$ from above} \\ & = \sum_{n \geq 1} 2h(n-1)\cdot x^n + \sum_{n \geq 1} x^n \\ & = 2x\sum_{n \geq 1} h(n-1) \cdot x^{(n-1)} + x\sum_{n \geq 1}x^{n-1} \tag{so we can start the sum from $n=0$} \\ & = 2x\sum_{n \geq 0} h(n) x^n + x\sum_{n \geq 0}x^n \\ & = 2x \cdot H(x) + x \cdot \frac{1}{1-x} \end{align}$$

Rearranging to solve for $H(x)$, we have:

$$H(x) - 2xH(x) = x \cdot \frac{1}{1-x} \quad \therefore H(x) \cdot (1-2x) = x \cdot \frac{1}{1-x} \quad \therefore H(x) = \frac{x}{(1-2x)(1-x)}$$

Next, we use partial fractions to get $H(x)$ in the form

$$H(x) = \frac{x}{(1-2x)(1-x)} = \frac{A}{1-2x} + \frac{B}{1-x}$$

where $A$ and $B$ are constants. To solve for $A$ and $B$, we multiply both sides by $(1-2x)(1-x)$:

$$\begin{align} x & = A(1-x) + B(1-2x) \\ & = A - Ax + B - 2Bx \\ & = (A+B) + (-A -2B)x \\ \therefore \; A + B & = 0 \mapsto B = -A \\ \therefore -A-2B & = -A + 2A = 1 \mapsto A = 1,\, B = -1 \end{align}$$

So we can write $H(x)$ as follows:

$$H(x) = \frac{x}{1-2x} - \frac{1}{1-x}$$

Finally, we have step (D), in which we try to find a non-recursive formula for $h(n)$. We can do so using the fact that

$$\begin{align} h(n) & = [x^n]H(x) \tag{i.e., the coefficient of $x^n$ in $H(x)$} \\ & = [x^n]\left ( \frac{1}{1-2x} - \frac{1}{1-x} \right ) \\ & = [x^n]\left (\left ( \sum_{n \geq 0} (2x)^n \right ) - \left ( \sum_{n \geq 0} x^n \right ) \right ) \\ & = [x^n] \left ( (1+2x + (2x)^2 + \cdots ) - (1 + x + x^2 + \cdots ) \right ) \\ & = 2n-1 \tag{think about it, it makes sense} \end{align}$$

2.2.2Subsets example

Let $f(n)$ be the number of subsets of $\{1, 2, \ldots, n\}$ that contain no pair of consecutive integers. The recurrence relation for this is

$$f(n) = f(n-1) + f(n-2)$$

since a subset $S$ can either contain $n$ (in which case, we can't have $n-1$ in our set, so we just look at all subsets up to $n-2$) or it doesn't contain $n$, in which case $S$ is a valid subset of $\{1, 2, \ldots, n-1\}$ and we just look at $f(n-1)$.

Incidentally, this is equivalent to the Fibonacci numbers.