The Catalan Numbers

# The Catalan Numbers

We will now look at a rather interesting set of counting numbers which we define below.

 Definition: The Catalan Numbers $C_0, C_1, C_2, ...$ are numbers defined for each nonnegative integer $n$ as $C_n = \frac{1}{n + 1} \binom{2n}{n}$.

For example, if $n = 0$, $n = 1$, $n = 2$, or $n = 5$ then the corresponding Catalan numbers are:

(1)
\begin{align} \quad C_0 = \frac{1}{0 + 1} \binom{0}{0} = \frac{1}{1} \cdot \frac{0!}{0! \cdot 0!} = 1 \end{align}
(2)
\begin{align} \quad C_1 = \frac{1}{1 + 1} \binom{2}{1} = \frac{1}{2} \cdot 2 = 1 \end{align}
(3)
\begin{align} \quad C_2 = \frac{1}{2 + 1} \binom{4}{2} = \frac{1}{3} \cdot 6 = 2 \end{align}
(4)
\begin{align} \quad C_5 = \frac{1}{5 + 1} \binom{10}{5} = \frac{1}{6} \cdot 252 = 42 \end{align}

The Catalan numbers appear in rather interesting situations - one of the most applicable is given and proven in the following theorem.

 Theorem 1: Let $(a_i)_{i=1}^{2n} = (a_1, a_2, ..., a_n, a_{n+1}, ..., a_{2n})$ be a sequence of $2n$ terms where $n$ of the terms in $(a_i)_{i=1}^{2n}$ are $+1$s and $n$ of the terms in $(a_i)_{i=1}^{2n}$ are $-1$s. Consider the $2n$ partial sums $s_1, s_2, ..., s_n, s_{n+1}, ..., s_{2n}$ where for each $k \in \{ 1, 2, ..., n, n+1, ..., 2n \}$ we have $s_k = \sum_{i=1}^{k} a_i = a_1 + a_2 + ... + a_k$. Then there are $C_n$ many sequences $(a_i)_{i=1}^{2n}$ such that $s_k \geq 0$ for all $k \in \{ 1, 2, ..., n, n+1, ..., 2n \}$.
• Proof: Let $(a_i)_{i=1}^{2n} = (a_1, a_2, ..., a_n, a_{n+1}, ..., a_{2n})$ be a sequence of $2n$ terms where $n$ are $+1$s and $n$ are $-1$s.
• Let $T$ be the set of all sequences $(a_i)_{i=1}^{2n}$ where $n$ terms are $+1$ and $n$ terms are $- 1$.
• For each sequence $(a_i)_{i=1}^{2n} \in T$ we have that it either satisfies the condition that $s_k \geq 0$ for all $k \in \{1, 2, ..., n, n+1, ..., 2n \}$ or $s_k < 0$ for some $k \in \{1, 2, ..., n, n+1, ..., 2n \}$. Let $A \subset T$ be the set of these sequences $(a_i)_{i=1}^{2n} \in T$ that satisfy this condition and let $A' \subset T$ be the set of sequences $(a_i)_{i=1}^{2n}$ of $n$ that do not satisfy this condition. Then $A$ and $A'$ partition $T$:
(5)
\begin{align} \quad T = A + A' \end{align}
• By the principle of addition we have that:
(6)
\begin{align} \quad \mid T \mid = \mid A \mid + \mid A' \mid \\ \quad \mid A \mid = \mid T \mid - \mid A' \mid \end{align}
• Our goal is to determine the value of $\mid A \mid$. We first note that if every sequence $(a_i)_{i=1}^{2n} \in T$ is comprised of only two different numbers, namely $n$ many $+1$s and $n$ many $-1$s then the total number of sequences in $T$ is:
(7)
\begin{align} \quad \mid T \mid = \binom{2n}{n} \end{align}
• That is, we take all $2n$ terms and choose $n$ of them to be $+1$s (or equivalently $n$ of them to be $-1$s) which uniquely defines a sequence in $T$.
• Now consider a sequence $(a_i)_{i=1}^{2n} \in A'$, that is, $(a_i)_{i=1}^{2n}$ is such that $s_k < 0$ for some $k \in \{1, 2, ..., n, n+1, ..., 2n \}$. There then exists a first $k$ such that $s_k < 0$. We have that then:
(8)
\begin{align} \quad s_k < 0 \\ \quad a_1 + a_2 + ... + a_{k-1} + a_k \end{align}
• We must have $a_k = -1$ since $k$ if the first number such that $s_k < 0$. We must also have that $a_1 + a_2 + ... + a_{k-1} = 0$ and so there is an equal number of $+1$s as there are $-1$s in the subsequence $(a_1, a_2, ..., a_{k-1})$, i.e., $k$ is odd.
• Take each term in $a_i$ for $i \in \{1, 2, ..., k \}$ and multiply it by $-1$ to change the sign of each terms and consider the resulting sequence:
(9)
\begin{align} \quad (a_i')_{i=1}^{2n} = (-a_1, -a_2, ..., -a_{k-1}, -a_k, a_{k+1}, ..., a_{2n}) \end{align}
• We note that this sequence $(a_i')_{i=1}^{2n} \in A'$ since there must be a partial sum $s_j' < 0$ where $j < k$ since we multiplied each of these first $k$ terms by $-1$. In the original sequence $(a_i)_{i=1}^{2n}$ the number of $+1$s balanced out the number of $-1$. When we multiplied an odd number, $k$ terms, by $-1$ to form $(a_i')_{i=1}^{2n}$ we end up with the sequence $(a_i')_{i=1}^{2n}$ to be a sequence containing $n+1$ many $+1$s and $n - 1$ many $-1$s. Conversely, given any sequence $(a_i')_{i=1}^{2n}$ of $n + 1$ many $+1$s and $n - 1$ many $-1$s we can construct a sequence $(a_i)_{i=1}^{2n} \in A'$ by taking the first $k$ terms in $(a_i')_{i=1}^{2n}$ where the number of $+1$s exceeds the number of $-1$s so that when we multiply these terms by $-1$ we obtain a sequence $(a_i)_{i=1}^{2n}$ where $s_k < 0$. Therefore the number of sequences in $A'$ is equal to the number of sequences containing $n + 1$ many $+1$s and $n - 1$ many $-1$s, that is:
(10)
\begin{align} \quad \mid A' \mid = \binom{2n}{n + 1} = \frac{(2n)!}{(n + 1)!(n - 1)!} \end{align}
• Therefore we have that:
(11)
\begin{align} \quad \mid A \mid = \mid T \mid - \mid A' \mid \\ \quad \mid A \mid = \binom{2n}{n} - \binom{2n}{n+1} \\ \quad \mid A \mid = \frac{(2n)!}{n! \cdot n!} - \frac{(2n)!}{(n + 1)! \cdot (n - 1)!} \\ \quad \mid A \mid = \frac{(2n)!}{n! \cdot (n - 1)!} \left ( \frac{1}{n} - \frac{1}{n+1}\right ) \\ \quad \mid A \mid = \frac{(2n)!}{n! \cdot (n - 1)!} \cdot \frac{(n + 1) - n}{n(n+1)} \\ \quad \mid A \mid = \frac{(2n)!}{n! \cdot n!} \cdot \frac{1}{1 + n} \\ \quad \mid A \mid = \frac{1}{1 + n} \binom{2n}{n} \quad \blacksquare \end{align}

For example, suppose that we wanted to determine the number of sequences $(a_i)_{i=1}^{6}$ of $3$ many $+1$s and $3$ many $-1$s such that the partial sums of this sequence are always nonnegative. Theorem 1 tells us that there will be $C_{3} = \frac{1}{1 + 3} \binom{6}{3} = \frac{1}{4} \cdot 20 = 5$ many of these sequences. We list them in the following table:

 $(+1, -1, +1, -1, +1, -1)$ $(+1, +1, -1, -1, +1, +1)$ $(+1, +1, +1, -1, -1, -1)$ $(+1, +1, -1, +1, -1, -1)$ $(+1, -1, +1, +1, -1, -1)$