Combinators and Catalan numbers

I seem to run into Catalan numbers fairly regularly. This evening I ran into Catalan numbers while reading Stephen Wolfram’s book Combinators: A Centennial View [1]. Here’s the passage.

The number of combinator expressions of size n grows like

{2, 4, 16, 80, 448, 2688, 16896, 109824, 732160, 4978688}

or in general

2n CatalanNumber[n − 1] = 2n Binomial[2n − 2, n − 1]/n

or asymptotically:

\frac{8^n}{4\,\sqrt{\pi}\,n^{3/2}}

Specifically, Wolfram is speaking about S and K combinators. (See a brief etymology of combinator names here.)

The Catalan numbers are defined by

C+n = \frac{1}{n+1} {2n \choose n}

Replacing n with n − 1 above shows that

CatalanNumber[n − 1] = Binomial[2n − 2, n − 1]/n

as claimed above.

The formula for the number of combinators is easy to derive [1]. There are 2n ways to write down a string of n characters that are either S or K. Then the number of ways to add parentheses is the (n − 1)st Catalan number, as explained here.

Wolfram’s asymptotic expression is closely related to a blog post I wrote two weeks ago called kn choose n. That post looked at asymptotic formulas for

f(n, k) = \binom{kn}{n}
and Catalan numbers correspond to f(n, 2)/(n + 1). That post showed that

f(n,2) \approx \frac{4^n}{\sqrt{\pi n}}

The asymptotic estimate stated in Wolfram’s book follows by replacing n with n-1 above and multiplying by 2n/n. (Asymptotically there’s no difference between n and n − 1 in the denominator.)

More posts on Catalan numbers

[1] Believe it or not, I’m reading this in connection with a consulting project. When Wolfram’s book first came out, my reaction was something like “Interesting, though it’ll never be relevant to me.” Famous last words.

[2] Later in the book Wolfram considers combinators made only using S. This is even simpler since are no choices of symbols; the only choice is where to put the parentheses, and CatalanNumber[n − 1] tells you how many ways that can be done.