Catalan Numbers and their Properties(Part - 1)

image

Almost all of you people are familiar or even madly in love with Fibonacci numbers.But in this post I will introduce you to another sequence of numbers known as Catalan numbers which like the Fibonacci numbers crop up in many unexpected areas!!By reading this post you'll surely be answer questions like what to do if you don't have spare change at hand and the number of possible restricted random walks :D

$\textbf{Definition:}$The Catalan sequence is a sequence of numbers $C_0,C_1,......C_n,...$ where $C_n = \frac{1}{n+1}\dbinom{2n}{n}$ where $n = 0,1,2,3,...$ is the $n$-th Catalan number, The first few Catalan numbers are :-

$C_0 = 1$ $C_1 = 1$ $C_2 = 2$ $C_3 = 5$ $C_4 = 14$ $C_5 = 42$

$\textbf{Theorem:}$The number of sequences $a_1,a_2,....,a_n$ of $2n$ terms that can be formed by using $n$ number of $+1$s and $n$number of $-1$s whose partial sums satisfy $a_1+a_2+....+a_k \ge 0$ for $k=1,2,3,4....2n$ equals the n-th Catalan number.

$\textbf{Proof:-}$Let us call a sequence of $n$ number of $+1$ s and $n$ number of $-1$ s to be acceptable if it satisfies the above condition and unacceptable otherwise.We denote the number of acceptable sequences by $A_n$ and the number of unacceptable sequences by $U_n$.

The total number of sequences of $+1$s and $-1$s can be regarded as a permutations of objects with two different types with $n$ different objects of one type and $n$ of the other.So the total number of such sequences is $\dbinom{2n}{n} = \frac {2n!}{n!n!}$

Now we will calculate $A_n$ by first calculating $U_n$.We will try to find a bijection. Let us consider an unacceptable sequence of $n$ $+1$s and $n$ $-1$s.So in case there must exist a smallest $k$ for which the partial sum $a_1+a_2+....+a_k$ is negative.Now as we have considered $k$ to the smallest of such numbers,there must be an equal number of $+1$ s and $-1$s preceding $a_k$!So we must have $a_1+a_2+...+a_{k-1} = 0$ and $a_k = -1$. So k is an odd integer!!and among the terms $a_1,a_2,...a_k)$ there are $\frac{k-1}{2}$ number of $+1$s and $\frac{k-1}{2}+1=\frac{k+1}{2}$ number of $-1$s.Among the remaining terms,that is, (a{k+1},....,a{2n}) we have $n - \frac{k-1}{2}$ number of $+1$s and $n - \frac{k+1}{2}$ number of $-1$s.

Now we have the most important part of the argument.Let us reverse the signs of each of the first $k$ terms.,that is we replace $a_i$ by $-a_i$ for each $i= 1,2,...k$ but we leave unchanged the remaining terms $a_{k+1},....,a_{2n}$.Now this new sequence obtained say $b_1,b_2,b_3,...b_2n$ will have $\frac{k+1}{2}$ $+1$s and $\frac{k-1}{2}$ $-1$s in the first $k$ terms and but the rest of the terms will have the same number of $+1$s and $-1$s as that of the previous sequence. So total number of $+1$s in this sequence is $\frac{k+1}{2}+ n- \frac{k-1}{2} = n+1$. The total number of $-1$s is $\frac{k-1}{2}+ n- \frac{k+1}{2} = n-1$. So $b_i$ for $i = 1,2,...2n$ is simply a sequence of $n+1$ $+1$s and $n-1$ $-1$s!!Also we can notice further that for any sequence of $n+1$ $+1$s and $n-1$ $-1$s there must be a point where the number of $+1$s exceed the number of $-1$s .There has to be such a point as the number of $+1$s are more!!Reversing the signs upto that point results in an unacceptable sequence.So we have found a bijection between the number of unacceptable sequences and the number of sequences of $(n+1)$ $+1$s and $(n-1)$ $-1$s.Clearly the number of sequences of $n+1$ $+1$s and $n-1$ $-1$s is $\frac{2n!}{(n+1)!(n-1)!}$.By bijection, this is also equal to the number of unacceptable sequences!!!So the total number of unacceptable sequences $U_n = \frac{2n!}{(n+1)!(n-1)!}$.

So the number of acceptable sequences is : $A_n = \frac{2n!}{(n)!(n)!} - U_n$ $A_n = \frac{2n!}{(n)!(n)!} - \frac{2n!}{(n+1)!(n-1)!}$ $A_n = \frac{1}{(n+1)} \frac{2n!}{(n)!(n)!}$

So $A_n$ is the $n$ -th Catalan number!!!

Now that you have understood this lets have some fun and play with this idea!!

$\textbf{APPLICATIONS:-}$

$\textbf{1.The empty cash register:-}$There are $2n$ people in a line to buy candy.Of the $2n$ people, $n$ have 50 cents and $n$ have $1\$$ bills.But the shopkeeper stupidly begins with an empty cash register.In how many ways can the people line up so that whenever a person with $\$1$ buys a candy the cash register has a 50 cent piece to make change.

img

$\textbf{Solution:-}$In this case we consider that people are indistinguishable.So we simply have a sequence of $n$ $50$ cent pieces and n $1\$$ bills.We can easily consider the 50$ pieces as $+1$s and the 1$ pieces as $-1$s,then this problem falls directly under the result of the above theorem.So by the given theorem the number of possible arrangements is the n-th Catalan number.$\frac{1}{(n+1)} \frac{2n!}{(n)!(n)!}$.

$\textbf{2.Restricted Random Walks:-}$A person works $n$ blocks north and $n$ blocks south of her residence.Every day he has $2n$ blocks to walk.How many routes are possible if he never crosses the diagonal line from home to office.

imgrandomwalk

$\textbf{Solution:}$Clearly each acceptable route is either above the diagonal or below the diagonal and both of these paths are symmetric.So we calculate the number of paths above the diagonal and multiply it by 2.Each route is a sequence of n northerly blocks and n easterly blocks.We identify north with $+1$ and east with $-1$.Each route corresponds to a sequence $a_1,a_2,....,a_{2n}$ of n$+1$s and n $-1$s .But in order that the route not dip below the diagonal,we must have $a_1+a_2+......+a_k \ge 0$ for $k=1,2,...........2n$.So the theorem the number of acceptable routes above the diagonal equals the n-th Catalan number and the total number of acceptable routes is $2C_n = \frac{2}{(n+1)} * \frac{2n!}{(n)!(n)!}$.The diagram shows all the possibilities for $n=5$.Notice that it is equal to $C_5 = 42$.

If you have any questions or suggestions feel free to post in the comment box.Have a nice day and stay tuned for my next post!! :)