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:
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 [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
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.)
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.
The post Combinators and Catalan numbers first appeared on John D. Cook.