<aside> 💡 The Catalan numbers are a sequence of positive integers that appear in many counting problems in combinatorics. They count certain types of lattice paths, permutations, binary trees, and many other combinatorial objects. They satisfy a fundamental recurrence relation, and have a closed-form formula in terms of binomial coefficients.
</aside>
The Catalan numbers $C_0,C_1, \ldots, C_n$ are given by the formula:
$$ Cn= \frac{1}{n+1} {2n \choose n} $$
The first few Catalan numbers are:
$$ C_0 = 1 \\ C_1 = 1 \\ C_2 = 2 \\ C_3 = 5 \\ C_4 = 14 \\ C_5 = 42 $$
The Catalan numbers satisfy the recurrence relation:
$$ C_{n+1}=C_{0} C_{n}+C_{1} C_{n-1}+\cdots+C_{n} C_{0}=\sum_{k=0}^{n} C_{k} C_{n-k} $$
A nice recursive function in python to visualize the behaviour of Catalan Numbers:
# A recursive function to find nth catalan number
def catalan(n):
# Base Case
if n <= 1 :
return 1
# Catalan(n) is the sum of catalan(i)*catalan(n-i-1)
result = 0
for i in range(n):
result += catalan(i) * catalan(n-i-1)
return result
for i in range(10):
print(f'C_{i+1} =',catalan(i))
Output:
C1 = 1
C2 = 1
C3 = 2
C4 = 5
C5 = 14
C6 = 42
C7 = 132
C8 = 429
C9 = 1430
C10 = 4862
The generating function for the Catalan numbers is:
$$ \sum_{n=0}^{\infty} C_{n} x^{n}=\frac{1-\sqrt{1-4 x}}{2 x}=\frac{2}{1+\sqrt{1-4 x}} . $$
One really cool example to understand how Catalan numbers work is Dyck Paths and Acceptable Sequences:
<aside> 💡 A Dyck Path is a series of up and down steps. The path will begin and end on the same level; and as the path moves from left to right it will rise and fall, never dipping below the height it began on.
We can Also represent Dyck paths as valid sequences of balanced parentheses by considering the right parentheses to be +1s and left parentheses to be -1s.
Example:
( ( ) ) is a valid Dyck Path. Here we go up up twice +1 +1 then go down twice -1 -1 and end up at 0 which is the original height.
( ) ( ) can also represent a Dyck Path.
</aside>
Theorem: The number of valid parenthesis expressions that consist of $n$ right parentheses and $n$ left parentheses is equal to the $n^{th}$ Catalan number.
For example, $C_3 = 5$ and there are 5 ways to create valid expressions with 3 sets of parenthesis:
Proof:
Considering right parenthesis to be +1s, and left -1s we can rewrite the problem as:
<aside> 💡 The number of sequences $a_1,a_2, \ldots, a_{2n}$ of $2n$ terms that can be formed by using $n$ copies of +1's and $n$ copies of −1's whose partial sums satisfy:
$a_1+a_2+\\cdots+a_k \\ge 0$
for $k=1,2,3,…,2n$ equals the $n^\text{th}$ Catalan number.
</aside>
Let a sequence be valid if it satisfies the condition above and invalid if it doesn't satisfy the condition, such that $A_n =$ number of valid sequences and $U_n =$ number of invalid sequences.
Let's count the Total number of sequences:
The total number of sequences of +1s and −1s can be regarded as a permutation of objects with two different types with $n$ different objects of one type and $n$ of the other.
Therefore the total number of sequences is: ${2n \choose n} = \frac{(2n)!}{n!n!}$
We can then write: $A_n = {2n \choose n} - U_n$
Now let's try to count $U_n$:
Consider an invalid sequence of n copies of 1s and n copies of −1s. Then there is a smallest k for which the partial sum $a_1+a_2+\cdots+a_k$ is negative. Then there must be an equal number of +1s and -1s preceding $a_k$. In this case $k$ must be odd such that $a_1+a_2+\cdots+a_{k-1} = 0$ , and $a_k = -1$. Therefore we can say that there are $(k-1)/2$ copies of 1s and $(k+1)/2$ copies of -1s. Among the remaining terms we have, $n-(k-1)/2$ of 1s and $n - (k+1)/2$ copies of -1s. Now swap all left parentheses for right and all right for left in the first k positions of the sequence. This gives us a collection of $n+1$ left parentheses and $n−1$ right parentheses.
Now, let us say we are given a sequence M of $n+1$ left parentheses and $n−1$ right parentheses, and let $k$ be the first position where there are more left parentheses up to that point than right. Flipping those parentheses gives us back a sequence of $n$ left parentheses and $n$ right parentheses that is not legal, because there are more right parentheses up to than left.
From this we can say that the number of invalid sequences is equal to the number of sequences of $n+1$ copies of 1s and $n-1$ copies of -1s. Which is equal to:
$$ U_{n}= {2n \choose n+1} \\ =\frac{2 n !}{(n+1) !(n-1) !} $$
We now have:
$$ \begin{aligned}A_{n} &=\frac{(2 n) !}{n ! n !}-U_{n} \\&=\frac{(2 n) !}{n ! n !}-\frac{(2 n) !}{(n+1) !(n-1) !} \\&=\frac{(2 n) !}{n !(n-1) !}\left(\frac{1}{n}-\frac{1}{n+1}\right) \\&=\frac{(2 n) !}{n !(n-1) !} \frac{1}{n(n+1)} \\&=\frac{1}{n+1} \frac{(2 n) !}{n ! n !} \\&=C_{n} .\end{aligned} $$
This completes the proof.
Restricted random walks: