Jason (jcreed) wrote,

Some of the the most mysterious and amazing things in mathematics are its bridges, things like Stone duality, (between topology and algebra) the Curry-Howard correspondence (between logic, programming languages, and category theory), and the theory of generating functions (between combinatorics and calculus). It's generating functions that are, once again, particularly astonishing to me lately. I was looking at Catalan numbers, and there is a no-cleverness route straight from the standard recurrence, through gfs, to a closed form expression. It's the "no-cleverness" part that's so amazing; it's almost entirely mechanical if you know a little calculus, compared to the moderately big insights about transforming monotone lattice paths that all the other proofs seem to require.

You start with the recurrence C_n = Σ_i=0^n-1 C_i C_{n-i-1} for n ≥ 1, and C_0 = 1. That is, the number of binary trees of size n is 1 if n is zero, and the sum over all possible ways of building a tree of size n out of two subtrees, the first of size i, and the second of size n-i-1. You say to yourself, hm, I'll try generating functions. That means sum both sides over x^n and give the left side a name. So we get some function g(x) such that:

g(x) = Σ_n=0^∞ C_n x^n = 1 + Σ_n=0^∞ Σ_i=0^n-1 x^n C_i C_{n-i-1}

(We get the "1 +" because we know C_0 is 1) Now the body of the sum on the right-hand side very naturally suggests the regrouping

x (C_i x^i) (C_{n-i-1} x^(n-i-1))

because this lets us reindex and separate sums:

g = 1 + x Σ_n=0^∞ Σ_i=0^{n-1} (C_i x^i) (C_{n-i-1} x^(n-i-1))
= 1 + x Σ_i=0^∞ Σ_v=0^∞ (C_i x^i) (C_v x^v)
= 1 + x (Σ_i=0^∞ C_i x^i) (Σ_v=0^∞ C_v x^v)
= 1 + x g^2

If you've seen generating functions before, you know "g = 1 + x g^2" is a very standard result of thinking about the datatype

'a tree ::= empty | node of 'a * tree * tree

which makes sense in any event, since catalan numbers are supposed, after all, to count binary trees with n internal nodes.

Anyway, you dig up the quadratic equation from the high-school section of your brain, and out comes

g(x) = (1 - sqrt(1 - 4x)) / 2x

Now what? Well, the coefficients of the power series for g(x) are the Catalan numbers. How do we compute them? Standard Taylor series stuff tell us we can always get out the nth coefficient of the series by differentiating n times, evaluating at zero, and dividing by n!. But differentiating with the square root upstairs and the non-vanishing 2x downstairs is a pain in the ass. Let's just do sqrt(1 + x) instead.

(1+x)^(1/2) = (1+x)^(1/2)
(d/dx)((1+x)^(1/2)) = (1/2)(1+x)^(-1/2)
(d/dx)^2((1+x)^(1/2)) = (1/2)(-1/2)(1+x)^(-3/2)
(d/dx)^3((1+x)^(1/2)) = (1/2)(-1/2)(-3/2)(1+x)^(-5/2)
(d/dx)^4((1+x)^(1/2)) = (1/2)(-1/2)(-3/2)(-5/2)(1+x)^(-7/2)

evaluating at zero and dividing by n! gives us the coefficients of the power series:

(1 / 0!) x^0 +
((1/2) / 1!) x^1 +
((1/2)(-1/2) / 2!) x^2 +
((1/2)(-1/2)(-3/2) / 3!) x^3 +
((1/2)(-1/2)(-3/2)(-5/2) / 4!) x^4 + ...

So the formula for the nth coefficient here (if n ≥ 1) is

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

How can we deal with that product of odd numbers? Well,
(2n - 2)! = (1 * 3 * 5 * .... 2n - 1) * (2 * 4 * 6 * ... 2n - 2)
= (1 * 3 * 5 * .... 2n - 1) * 2^{n-1} (n-1)!
so it's equal to 2((2n-2)! / 2^n (n-1)!) Our formula for the nth coefficient can be rewritten as

-(-1/4)^n (2/n) ((2n-2)!/(n-1)!(n-1)!)

which is nice because we can mention binomial coefficients now:

-(-1/4)^n (2/n) (2n-2 choose n-1)

This means (remembering that the 0th coefficient for sqrt(1+x) is 1) that

sqrt(1+x) = 1 - 2Σ_{n=0}^∞ (-1/4)^n (1/n) (2n-2 choose n-1) x^n

Here's where the magic really happens! It's delightful how the nastiness of this formula and the nastiness of the quadratic equation solution cancel each other out nicely.

If we substitute -4y for x that (-1/4)^n goes away:

sqrt(1-4y) = 1 - 2Σ_{n=0}^∞ (1/n) (2n-2 choose n-1) y^n

And if we hit both sides with 1, the "1 - " on the right goes away:

1 - sqrt(1-4y) = 2Σ_{n=0}^∞ (1/n) (2n-2 choose n-1) y^n

Divide by 2:

(1 - sqrt(1-4y))/2 = Σ_{n=0}^∞ (1/n) (2n-2 choose n-1) y^n

and now dividing by y, in generatingfunction-land, means a mere reindexing substitution of n+1 for n inside the sum:

(1 - sqrt(1-4y))/2y = Σ_{n=0}^∞ (1/(n+1)) (2n choose n) y^n

bingo! The nth catalan number is

(2n choose n) / (n+1)

quod erat trovitum or whatever the latin is for "which was to have been found".
Tags: math

  • (no subject)

    Something that's bugged me for a long time is this: How many paths, starting at the origin, taking N steps either up, down, left or right, end up at…

  • (no subject)

    Still sad that SAC seems to end up being as complicated as it is. Surely there's some deeper duality between…

  • (no subject)

    I had already been meaning to dig into JaneSt's "Incremental" library, which bills itself as a practical implementation (in ocaml) of the ideas in…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded