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

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

or in general

2

^{n}CatalanNumber[n-1] = 2^{n}Binomial[2n– 2,n– 1]/nor 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[2*n* – 2, *n* – 1]/*n*

as claimed above.

The formula for the number of combinators is easy to derive [1]. There are 2^{n} 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 2^{n}/*n*. (Asymptotically there’s no difference between *n* and *n*-1 in the denominator.)

## More posts on Catalan numbers

- How many ways can you parenthesize an expression?
- Calculating ΞΆ(3) faster
- Large matrices rarely have saddle points
- Number of digits in 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.