Math + You = 1

# Catalan numbers: Properties and applications

After the numbers of mersenne, here are the Catalan numbers! Catalan numbers are a sequence of natural numbers used in counting. Let's see together their definition, various properties and some applications!

## Definition of Catalan numbers

We can define the Catalan numbers by binomial coefficients, here is their definition! The n-th number of Catalan, denoted Cn, is defined by

C_n = \dfrac{1}{n+1} \biname{2n}{n}

They can be rewritten with factorials by:

C_n = \dfrac{(2n)!}{(n+1)!n!}

Or again, with a product or a difference of binomial coefficients:

C_n =\prod_{k=2}^n \dfrac{n+k}{k} = \binom{2n}{n} - \binom{2n}{n+1}

The first 15 Catalan numbers are

• 1
• 1
• 2
• 5
• 14
• 42
• 132
• 429
• 1430
• 4862
• 16796
• 58786
• 208012
• 742900
• 2674440

## Properties of Catalan numbers

### First property: Equivalent

We can find an equivalent for them. For this, we will use the Stirling's formula on the definition with factorials:

\begin{array}{ll} C_n &= \dfrac{(2n)!}{(n+1)!n!} \\ & \sim \dfrac{\sqrt{2\pi 2n} \left( \frac{2n}{e}\right)^{2n}}{\sqrt{2\pi (n+1)} \left( \frac{n+1}{e}\right) ^{n+1}\sqrt{2\pi n} \left( \frac{n}{e}\right)^n}\\ & \sim \dfrac{2\sqrt{\pi n} \left( \frac{2n}{e}\right)^{2n}}{2\sqrt{\pi n} \left( \frac{n+1}{e}\right)^{n+1}\sqrt{ \pi n} \left( \frac{n}{e}\right)^n}\\ & \sim \dfrac{ \left( \frac{2n}{e}\right)^{2n}}{\ left( \frac{n+1}{e}\right)^{n+1}\sqrt{\pi n} \left( \frac{n}{e}\right)^n}\\ & \sim \dfrac{4^ne^{n+n+1-2n} n^{2n}}{\left( n+1\right)^{n+1}\sqrt{\pi n} n^n}\ \ & \sim \dfrac{4^ne n^{2n}}{n^{n+1}\left( 1+\frac{1}{n}\right)^{n+1}\sqrt{\ pi n} n^n}\\ & \sim \dfrac{4^ne n^{2n}}{n^{n+1}e\sqrt{\pi n} n^n}\\ & \sim \ dfrac{4^nn^{2n-n-(n+1)}}{\sqrt{\pi n} }\\ & \sim \dfrac{4^n}{n\sqrt{n\pi} }\ \ \end{array}

### Parity

The Catalan number Cn is odd if and only if n = 2k - 1

### Recurrence relation

Catalan numbers satisfy the following recurrence formula:

C_0=1,C_{n+1} = \sum_{k=0}^n C_i C_{ni}

Using this formula as the Cauchy product, we get the following integer series:

 \dfrac{1-\sqrt{1-4x}}{2x}=\sum_{n=0}^{+\infty} C_n x^n

\sum_{n+0}^{+\infty} \dfrac{1}{C_n} = 2 + \dfrac{4\pi}{9 \sqrt{3}}

### Integral representation

A complete C scriptn East :

C_n = \dfrac{1}{\pi} \int_0^2 x^{2n}\sqrt{4-x^2}dx

### Functional representation

If we are looking for a continuous function C such that C(n) = Cn, and even an indefinitely differentiable and even meromorphic function for those familiar with complex analysis. Then, the unique meromorphic function which fits and which is a suitable function is:

C(s) =\dfrac{\Gamma(2s + 1)}{\Gamma(s + 1)\Gamma(s + 2)}

Where Γ is the gamma function which we talked about in a previous article

## Applications of Catalan numbers

As you will see below, Catalan numbers appear in various applications related to counting.

### Dyck's Words

A Dyck word is a string of characters made up of n letters X and n letters Y. Such a word must not have any prefix containing strictly more X than Y. For example, Dyck words of length 2 are:

• XXYY
• XYXY

Which corresponds well to C2. Cn is therefore the number of Dyck words formed of n letters X and Y.

We obtain the following corollary: The number of vectors of {-1;1}2n whose partial sums of the coordinates are all positive and whose total sum is zero is equal to Cn.

### Polygon triangulations

If we cut a convex polygon with n+2 sides by connecting some of its vertices by segments, we have Cn ways to do it. Example with n = 3 and the pentagon:

### Associativity

The number of ways to calculate a non-associative product of n + 1 terms is Cn.

### Binary trees

And finally, one last application: Cn is the number of binary trees with n nodes.