Progress-in-maths

Math + You = 1

Catalonia
Courses Preparation course Math Facts

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 

In addition, note that:

\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.

Leave comments