Catalan Numbers

Definition

The $n$-th Catalan number can be directly obtained from binomial coefficients

$$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$$

Applications in Counting

Parentheses Association

$C_n$ is the number of ways to parenthesis the product of $n+1$ numbers to specify the order of multiplication. For example, if $n=3$, we have

$$((ab)c)d(a(bc))d(ab)(cd)a((bc)d)a(b(cd))$$

That is $5$ ways in total.

We can derive this by the recurrence relation

$$C_n=C_0{C}_{n-1}+C_1{C}_{n-2}+\cdots +C_{n-2}{C}_1+C_{n-1}{C}_0$$

with the initial condition $C_0=C_1=1$