Catalan Numbers(2016)

#Catalan numbers

July 29, 2023

The Catalan numbers are a sequence of natural numbers that occur in various problems in combinatorial mathematics. For example, the number of expressions containing $n$ valid pairs of parentheses is the $n$th Catalan number. Suppose you have a grid of $n \times n$ squares, the $n$th Catalan number represents the number of paths with a length of $2n$ that lead from the upper left corner to the lower right corner without intersecting the diagonal dotted line running from the upper left to the lower right. Later in the page, we will derive explicit formulas for the Catalan numbers in two different ways.

A string of parentheses is valid if you begin at the left as you move to the right, add 1 each time you pass an open and subtract 1 each time you pass a closed parenthesis, then the sum is always non-negative. The sum must be 0 when you reach at the end of the string. For example, The number of the valid strings is 0 if $n$ is $0$ or $1$. The number is $2$ if n is $2$(i.e., “()()“and “(())"). The number of the valid groupings of n pairs of parentheses is the $n$th Catalan number.

Let us assume that we already have the counts for $0, 1, 2, 3, \cdots , n − 1$ pairs and we would like to obtain the count for $n$ pairs. Any $n(>0)$ valid pairs of parentheses can be represented as “(A)B.” A and B are balanced sets of parentheses. If A contains $k$ pairs, then B contains $n − k − 1$ pairs. $k$ is between $0$ and $n-1$, and we conclude that: $$ C_n = C_{n-1}C_0 + C_{n-2}C_1 + \cdots + C_1C_{n-2} + C_0C_{n-1} $$

We will obtain an explicit formula for the Catalan numbers by analyzing the number of the diagonal-avoiding paths. The total number of paths through an $n\times n$ grid is $\binom{2n}{n}$ because every path from the upper left corner to the lower right corner contains $n$ steps to the right and $n$ steps down.

We will count the number of diagonal-avoiding paths by counting the total number of paths through the grid and then subtract the number of paths that hit the diagonal. The following figure illustrates a path that crosses the dotted diagonal line. grid

A point $P$ is the first grid point it touches on the wrong side of the diagonal. Every diagonal-avoiding path has the first grid point. If you swap steps to the right and steps down that are in a sub path begins at P, the swapped path contains $n-1$ steps to the right and $n+1$ steps down: $$ C_n = \binom{2n}{n} - \binom{2n}{n+1} $$

Reference

Tom Davis, Catalan Numbers, 2016

The above figure was cited from the paper.