First Post

This was my first ever on-line posting, to sci.math in 1988. The world wide web wasn't invented until 1989 so we didn't have links---I added them in 2004 when I posted this to my blog.

Kristian Damm Jensen wrote:

Consider a string of matching parentheses, i.e. a string of parentheses where each prefix contains more left-parentheses than right-parentheses.

Now, given n left- and right parentheses, in how many ways can you order them and still get a string of matching parentheses?

"The Invisible Man" replied:

Here's as far as I got. Possibly far enough, perhaps too far. It looks like someone better at this sort of thing can get a result in closed form.

Let f(n) be the number of valid paren strings of n pairs of parens. (and define f(0) to be 1). We can get a recurrence relationship as follows:

Any string of n paren pairs can be derived uniquely from 2 smaller paren pair strings by considering it to be 1 leading string (possibly null) contained in parens followed by a trailing string: the rest. For example, (())(()())() is a combination of (()) and (()())(). We can thus say that f(n) = sum j=0 to n-1 of f(j)*f(n-1-j)

If this isn't far enough yet, consider g(x) = sum j=0 to infinity of f(j)*(x^j) This is the generating function for f() (see Knuth Vol 1) Using the above recurrence, note that

g^2 = (g - 1)/x

which solved for g gives:

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

This can also (i.e. if it does any good) be written as:

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

What we want now is an expression for the nth coefficient for the expansion of g as a power series in x. So, what's the next step?

OK, we want the series for sqrt(1-4x). The binomial thereom gives

sqrt(1-4x)= (1-4x)^(1/2)
          = sum i=0 to infty of C(1/2,i)(-4)^ix^i

where C(n,r)=n!/(r!(n-r)!) is the binomial coefficient. If you're worried about calculating (1/2)! just trust me.

C(n,r)= product i from 1 to r of (n-(i-1))/i
C(1/2,i)(-4)^i = (1/2)(1/2-1)(1/2-2)....(1/2-(i-1))
                 -----------------------------------(-4)^i
                    1   2      3    ....  i
              (-1)(1)(3)...(2i-3)
            = -------------------2^i
                      i!

            = (-1)(1)(3)...(2i-3)(2)(4)(6)...(2i)
              -----------------------------------
                      i! i!
            = -C(2i,i)/(2i-1)
So sqrt(1-4x)= sum i=0 to infty of (-C(2i,i)/(2i-1))x^i.

             = -1 - sum i=1 to infty of (C(2i,i)/(2i-1))x^i

let j = i-1

             = -1 - sum j=0 to infty of (C(2j+2,j+1)/(2j+1))x^(j+1)

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

           = (sum j=0 to infty of (C(2j+2,j+1)/(2j+1))x^(j+1))/2x

           = sum j=0 to infty of (C(2j+2,j+1)/(4j+2))x^j

So f(n) = C(2n+2,n+1)/(4n+2) = C(2n,n)(2n+2)(2n+1) = C(2n,n)/(n+1).

                               -------------------

                                (n+1)(n+1)(4n+2)

This is called the Catalan number. It is also the number of different ways of triangulating a convex polygon with n+2 sides, the number of different binary trees with n nodes and the number of different ways of folding a strip of n stamps.