Associated Topics || Dr. Math Home || Search Dr. Math

### Generating Function of Catalan Numbers

```
Date: 04/04/2000 at 04:57:41
From: Chris
Subject: Combinatorics - generating functions

I don't know if you can be any help, but I was given a problem to
solve, which the professor has said is a little beyond where we are
but he wanted to know if anyone could answer it. I have worked on it
using books from the library but I am really confused.

h_n = h_1 h_(n-1) + h_2 h_(n-2) + ... + h_(n-1) h_1

where n >= 2 and h1 = 1

(h_n is h(sub)n, and h_2 is h(sub)2)

then it asks to show that the generating function satisfies:

(g(x))^2 - g(x) + x = 0

then show that hn = 1/n(2n-2 choose n-1)

I really don't understand the generating function idea. If anyone can
help or point me to a good tutorial on these types of problems I would
greatly appreciate it. Thanks.
```

```
Date: 04/04/2000 at 17:44:32
From: Doctor Anthony
Subject: Re: Combinatorics - generating functions

What you have quoted is the recurrence relation for the Catalan
numbers. These occur in a number of different problems. For example,
if you have an n x n square grid of roads and you need to count the
number of possible routes between two diagonally opposite corners such
that your routes never cross (but may touch) the diagonal, then the
Catalan numbers will provide the answer. Other problems include the
number of ways of dividing a convex polygon with n+1 sides into
triangular regions by inserting diagonals that do not intersect in the
interior, and the number of ways of parenthesizing a product such as
abcd into for example (((ab)c)d) or ((a(bc))d) or whatever.

Another example that we can use to explain the recurrence relation and
the generating function quoted above is by rooted binary trees. Before
doing that we note that if

inf
f(x) = SUM[ai.x^i]
i=0

is the generating function for  a0, a1, a2, a3, ... then

[f(x)]^2 generates a0.a0, a0.a1 + a1.a0, a0.a2 + a1.a1 + a2.a0,
..., a0.an + a1.a(n-1) + a2.a(n-2) + ... + a(n-1).a1 + an.a0

which is the convolution of a0, a1, a2, ... with itself.

In general a tree is an undirected graph that is connected and has no
loops or cycles. Here we examine rooted binary trees where the first
vertex denotes the root. These trees are called binary because from
each vertex there are at most two branches descending from that
vertex.

In particular these rooted binary trees are ordered in the sense that
a left branch descending from a vertex is considered different from a
right branch descending from that vertex. For the case of 3 vertices,
the five possible ordered binary trees are shown below.

*              *        *     *           *
/ \            /        /       \           \
/   \          /        /         \           \
*     *        *        *           *           *
/          \           \         /
/            \           \       /
*              *           *     *
(1)         (2)       (3)        (4)        (5)

The objective is to count the number, bn, of rooted, ordered binary
trees on n vertices.

Assuming that we know bi for 0 <= i <= n we use these to find b(n+1).
The trees rooted on vertices within the total structure are called
subtrees. Among the possible subtrees is the empty subtree of which
there is only 1. That is, b0 = 1.

If we start at the root (the very top of the diagram) there are two
subtrees one on the left and one on the right. Now consider how the n
vertices in these two subtrees can be divided up.

(1) 0 vertices on the left, n vertices on the right. This results in
b0.bn overall structures to be counted in b(n+1)

(2) 1 vertex on the left and n-1 vertices on the right giving
b1.b(n-1) rooted ordered binary trees on n+1 vertices.

(3) 2 vertices on the left and n-2 vertices on the right ...

:
:

(n+1) n vertices on the left and 0 vertices on the right contributing
bn.b0 trees

b(n+1) = b0.bn + b1.b(n-1) + b2.b(n-2) + .... + b(n-1).b1 + bn.b0 and

inf                   inf
SUM[b(n+1).x^(n+1)] = SUM[(b0.bn + .... + bn.b0)x^(n+1) ....[1]
n=0                   n=0

Now let

inf
f(x) = SUM[bn.x^n]
n=0

be the generating function for b0, b1, b2, ...

We write equation [1] as

inf
[f(x) - b0] = x.SUM[(b0.bn + b1.b(n-1) + ... + bn.b0)x^n]
n=0

= x.[f(x)]^2

and so we get the quadratic

x.[f(x)]^2 - f(x) + 1 = 0

and so

1 +- sqrt(1-4x)
f(x) = ---------------
2x

but

sqrt(1-4x) = (1-4x)^(1/2)
= C(1/2,0) + C(1/2,1)(-4x) + C(1/2,2)(-4x)^2 + ...

and the coefficient of x^n will be

C(1/2,n)(-4)^n

(1/2)(-1/2)(-3/2)(-5/2)...(-(2n-3)/2
= ------------------------------------ (-4)^n
n!

(-1)2^n.(1)(3) ... (2n-3)
= -------------------------
n!

(-1)2^n.n!.(1)(3) ... (2n-3)(2n-1)
= ----------------------------------
n! n! (2n-1)

(-1)(2)(4)(6) ... (2n) (1)(3) ... (2n-3)(2n-1)
= ----------------------------------------------
n! n! (2n-1)

(-1) C(2n,n)
=  ------------
2n-1

In f(x) we select the negative root; otherwise we would have negative
values for the bn's, and so

1            inf    1
f(x) = ----[ 1 - [1 - SUM[------- C(2n,n).x^n]]]
2x            n=1  (2n-1)

and bn the coefficient of x^n in f(x) is half the coefficient of
x^(n+1) in

inf   1
SUM[----- C(2n,n).x^n]
n=1 (2n-1)

and so

1      1
bn = ---[----------].C(2(n+1),n+1)
2  (2(n+1)-1)

(2n)!      1
= --------- = -----.C(2n,n)
(n+1)! n!   (n+1)

The numbers bn are the Catalan numbers that we described earlier.

-Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory
High School Number Theory
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search