A Brief Discussion on Catalan Numbers

Introduction#

The essence of $Catalan$ is recursion, and many problems have a recursive form similar to that of $Catalan$ , indicating that they share commonalities and can utilize the thinking methods of $Catalan$ numbers, which opens a new window for us in problem-solving.

Definition#

$|A|: sequence length$
$a set of solutions: a string of valid sequences$
$operator\ +: sequence concatenation$

Number of Binary Tree Types Problem#

Divide and conquer: left + self + right

We have the following definition

H_n=\begin{cases} 1, n=0,1\\ \sum_{i=1}^nH_{n-i}\cdot H_{i-1}, n\geq 2 \end{cases}

Valid Sequences#

$n$ instances of $+1$ and $n$ instances of $-1$ form $2n$ terms $a_1,a_2, \cdots ,a_{2n}$ , whose partial sums satisfy $a_1+a_2+ \cdots +a_k \geq 0(k=1,2,3, \cdots ,2n)$ What is this sequence for $n$ ?

At first glance, it seems difficult, but let's analyze it carefully.

It seems inconvenient to obtain the result directly, so we use the principle of inclusion-exclusion.

We subtract the number of invalid sequences from the total.

Total Count#

Place $n$ instances of $+1$ in a long $2n$ sequence, with the rest being $-1$ , thus the total count is $\binom{2n}{n}$ .

Invalid Count#

First, we consider the invalid cases.
There is only one situation that leads to invalidity:
That is, during the process of some prefix sum, the partial sum first becomes less than zero.

Constructing Invalid Count#

Let $A$ be a set of valid solutions, and $B$ be any sequence (simultaneously satisfying that $B$ is missing exactly one $-1$ and has $|B|=n-1$ ).
That is, $|A|+|B|=2n-1$ .

Clearly, at this point, we have $H=(A, -1, B)$ , which is a set of invalid solutions.

Warning

At this point, although it is an invalid solution, the counts of $+1$ and $-1$ in $H$ are both $n$ .

How do we distinguish between valid and invalid solutions?
We define (taking the complement of the $B$ sequence)

\hat{B_i}=\begin{cases} +1, B_i=-1\\ -1, B_i=+1 \end{cases}

Now $\hat{B}$ is a sequence that has one more and only one more $-1$ (it has changed from having one less to one more).

Now $\hat{H}=(A, -1, \hat{B})$ is a sequence with $n+1$ instances of $-1$ and $n-1$ instances of $+1$ .

It seems we have distinguished them; let's verify the feasibility.
Consider whether it can be done without omission or duplication.

Carefully thinking, $\hat{B}$ and $B$ form a bijective set.
This means that all invalid solutions correspond to such a $\hat{H}$ .

So how do we count them?
We can enumerate the counts of $+1$ or $-1$ .

That is $\binom{2n}{n-1}$ or $\binom{2n}{n+1}$ .

Final Solution#

$H_n=\binom{2n}{n}-\binom{2n}{n-1}$