Catalan numbers: Properties and applications

Contents of this article

1 Definition of Catalan numbers
2 Properties of Catalan numbers
3 Applications of Catalan numbers

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 C_n, 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 C_n is odd if and only if n = 2^k - 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

In addition, note that:

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

Integral representation

A complete C script_n 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) = C_n, 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 C₂. C_n 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}²ⁿ whose partial sums of the coordinates are all positive and whose total sum is zero is equal to C_n.

Polygon triangulations

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