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

2ⁿ CatalanNumber[n-1] = 2ⁿ 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 2ⁿ 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 2ⁿ/n. (Asymptotically there’s no difference between n and n-1 in the denominator.)

More posts on Catalan numbers