Generating Function of Catalan NumbersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/