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.

Start with the recurrence relation:

     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

And so adding all these

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/