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.