Friday, October 19, 2018

Asymptotic growth of the Catalan numbers

The Catalan numbers have a convenient definition in terms of the central binomial coefficient, which is defined by the factorial. As such, we can compute the asymptotic growth of the Catalan numbers using the asymptotic definition of the factorial we already have acquired using Stirling's formula. The central binomial coefficient is equal to $2n$ factorial divided by $n$ factorial squared. $$\frac{(2n)!}{{(n!)}^2}$$ We can plug in the asymptotic definition of the factorial into the above equation to get the following formula. $$\frac{ \frac{\sqrt{2\pi (2n)} (2n)^{2n}}{e^{2n}} }{ (\frac{\sqrt{2\pi n} n^n}{e^n})^2 } $$ In order to reduce this formula first we will notice that the $e^{2n}$ on both sides of the equation can be eliminated. To simplify the denominator notice that the square root of four is two, which can be pulled out of the square root. Then simplify $(2n)^{2n}$ by pulling out each of its factors. Then to simplify the denominator square it by multiplying the exponent of the factors by two, eliminating the square root. This results in the following reduced formula $$\frac{ 2(\sqrt{\pi n}) 4^n n^{2n} }{ 2(\pi n) n^{2n} } $$ It is plainly apparent that $2$ and $n^{2n}$ can be eliminated from both sides of the ratio. Then the two terms involving $\pi n$ can be simplified by adding their exponents which effectively puts the square root in the denominator. $$\frac{4^n}{\sqrt{\pi n}}$$ This is the asymptotic definition of the central binomial coefficient. Then in order to get the asymptotic growth of the Catalan numbers from this all that we have to do is divide it by $n+1$. $$C_n \sim \frac{4^n}{\sqrt{\pi n}(n+1)}$$ This gets us the asymptotic definition of the Catalan numbers. They grow at the rate of an exponential function with a base of four. This demonstrates that the asymptotic definition of the Catalan numbers can be acquired just from the definition of the asymptotic growth of the factorial which we have already shown.

No comments:

Post a Comment