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 one 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} = -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). $$