# 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 . 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: Specifically, Wolfram is speaking about S and K combinators. (See a brief etymology of combinator names here.)

The Catalan numbers are defined by 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 . 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 and Catalan numbers correspond to f(n, 2)/(n + 1). That post showed that 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.)