A Note on Catalan Number

With the help from MS365 Copilot, I learned the Catalan numbers

$$ {2n \choose n} / (n+1), \ n = 1, 2, \ldots . $$

Here is the story:

• I looked through this post Computing pi by flipping a coin by Andrew Gelman.
• Then I studied Propp’s paper.
• I got interested in the Catalan numbers.

To introduce the Catalan numbers, let’s consider the following problem: Find the number of sequences $A_1A_2\cdots A_{2n}$ that satisfy the conditions:

1. $A_i$ for $1\le i \le 2n$ is either $-1$ or $1$.
2. $\sum_{i=1}^{2n} A_i = 0$.
3. $\sum_{i=1}^j A_i \le 0$ for $j=1,\ 2,\ \ldots, 2n.$

The answer is ${2n \choose n} / (n+1)$. But how do we derive the answer? I gave it try. It’s obvious that the number of sequences that satisfy Conditions 1 and 2 is

$$ {2n \choose n}. $$

I did a couple of examples but no substantial progress was made. So I asked MS365 Copilot, and it taught me the following key steps.

1. The $\hbox{answer} = {2n \choose n} - x$, where $x$ counts the “bad” sequences—those ones that satisfy Conditions 1 and 2 but not 3.

2. The set of “bad” sequences (denoted Set B) is in bijection relationship with the set of sequences (denoted Set D) that satisfy Condition 1 and Condition 4, namely: $\sum_{i=1}^{2n} A_i = -2.$ Notice that each sequence of Set D contains $n-1$ occurrences of $1$ and $n+1$ occurrences of $-1$. Thus the cardinality of Set D is ${2n \choose n+1}$. At this point, we have obtained the value of $x$.

3. Simple calculation gives

$$ {2n \choose n} - {2n \choose n+1} = {2n \choose n} / (n+1). $$

Updated on 8 March 2026

I had asked myself this question: Let $S_n$ (for $n=1,\ 2,\ \ldots$) be the number of sequences $A_1A_2\cdots A_n$ that satisfy the following conditions

• $A_i$ is either $-1$ or $1$, $1\le i\le n$;
• $\sum_{i=1}^j A_i \le 0$, for $1\le j\le n$.

What is $S_n$?

Clearly, this question is related to the stuff discussed in the above. It is easy to figure out that

$$ S_1 = 1, $$

and for $n=1, 2, \ldots,$

$$ \left\{ \begin{array}{ccl} S_{2n} &=& 2S_{2n-1}\\ S_{2n+1} &=& S_{2n} + \left(S_{2n} - {2n \choose n}/(n+1) \right)\\ &=& 2S_{2n} - {2n \choose n}/(n+1). \end{array} \right. $$

Using these recursive relationships, I can find the first nine numbers for $S_n$, i.e. ${1, 2, 3, 6, 10, 20, 35, 70, 126}$. Next, I checked the numbers at the OEIS website, and it told me that

$$ S_n = {n \choose \hbox{floor}(n/2)}; $$

please see this page.

Finally, I proved indeed

$$ S_n = {n \choose \hbox{floor}(n/2)} $$

by mathematical induction.