Catalan numbers

Numbers of Catalan

n ${displaystyle C_{n},}$ 0 1 1 1 2 2 3 5 4 14 5 42 6 132 7 429 8 1.430 9 4.862 10 16.796 11 58.786 12 208.012 13 742.900 14 2.674.440 15 9.694.845 16 35.357.670 17 129.644.790 18 477.638.700 19 1.767.263.190 20 6.564.120.420 21 24.466.267.020 22 91.482.563.640 23 343.059.613.650 24 1.289.904.147.324 25 4.861.946.401.452

In combinatorics, the Catalan numbers form a sequence of natural numbers that appears in various counting problems that are usually recursive. Its name refers to the Belgian mathematician Eugène Charles Catalan (1814-1894).

The nth Catalan number is obtained, applying binomial coefficients, from the following formula:

${displaystyle C_{n}={frac {1}{n+1}}}{2n choose n}={frac {(2n)!}{(n+1)!,n!}}qquad {mbox{ with }ngeq 0. !$

History

The Catalan number sequence was described in the 18th century by Leonhard Euler. The sequence is named after Eugène Charles Catalan, who discovered the connection to parenthetical expressions during his exploration of the Towers of Hanoi puzzle.

In 1988, it came to light that the Catalan numerical sequence had been used in China by the Mongolian mathematician Minggatu around 1730. It was when he began writing his book Ge Yuan Mi Lu Jie Fa [The quick method for obtaining the precise division ratio of a circle], which was completed by his student Chen Jixin in 1774, but published sixty years later.

Properties

An alternative expression for C_n is

${displaystyle C_{n}={2n choose n}-{2n choose n-1}quad {mbox{ con }ngeq 1. !$

This other expression shows that C_n is a natural number, which is not obvious a priori observing the first formula given.

A curious way to generate C_n, derived from the previous formulas, is from the factorial of any integer par ${displaystyle (2n)}$. All terms on the left of the factor are divided ${displaystyle n+1}$, among all the terms placed on your right and the result will be the number of Catalan.

The Catalan numbers satisfy the following recurrence relation:

${displaystyle C_{0}=1quad {mbox{y}}quad C_{n+1}=sum _{i=0}{n}C_{i},C_{n-i}quad {mbox{con}}ngeq 0.}$

And they also satisfy:

${displaystyle C_{0}=1quad {mbox{y}}quad C_{n+1}={frac {2(2n+1)}{n+2}}}C_{n},}$

which may be a more efficient way to calculate them.

The expression in recursion form would be:

${displaystyle C_{n}={begin{cases}{mbox{si }n=0 fakeRightarrow 1{mbox{si }n fake0 pretendRightarrow {cfrac {2(2n-1)}{n+1}}}{n,C_{n-1}end{cases}}}}}$

Asymptotically, the Catalan numbers grow as:

${displaystyle C_{n}sim {frac {4^{n}}{n^{3/2}{sqrt {pi}}}}}}}$

considering that the quotient between the nth Catalan number and the expression on the right tends towards 1 when n → ∞ (this can be proven using the formula Stirling).

Combinatorial applications

There are multiple combinatorial problems whose solution is given by the Catalan numbers. The book Enumerative Combinatorics: Volume 2, by Richard P. Stanley contains a set of exercises that describe 66 different interpretations of the Catalan numbers. Some examples are shown here, with illustrations for the case C₃ = 5.

• C_n is the number of Dyck words in length 2n. A word of Dyck is a string of characters that consists of n X's and n And's so there's no initial segment that has more Y's than X's. For example, the following are the words of Dyck in length 6:

• Reinterpreting the X symbol as an open parenthesis and the Y as a closed parenthesis, C_n counts the number of expressions containing n pairs of correctly placed parentheses:

• C_n is the number of different forms of grouping n+ 1 factors by parenthesis (or the number of ways to associate n applications of a binary operator). Stop. n = 3 for example, we have the following five different ways of grouping the four factors:

${displaystyle (ab)c)dquad (a(bc))dquad (ab)(cd)quad a(bc)dquad a(b(cd))}$

• Successive applications of a binary operator can be represented with a binary tree. In this case, C_n is the number of binary trees of n+ 1 leaves, in which each node has zero or two children:

• C_n is the number of monotonous paths that can be traced through the lines of a mesh of n × n square cells, so you never cross the diagonal. A monotonous path is the one that starts in the lower left corner and ends in the upper right corner, and consists only of sections that point up or right. The count of these paths is equivalent to counting Dyck words: X means "move to the right" and Y means "move up." The following diagrams show the case n =

• C_n is the number of different ways to divide a convex polygon n+ 2 sides in triangles connecting vertices with diagonals without any being cut. The following figure illustrates the case of the ${displaystyle c_{4}}$ = 14 possible triangulations for a 6-side polygon: