gen-define-catalan-numbers-and-give-one-short-worked-example-5062

Define Catalan numbers and give one short worked example.

# Catalan Numbers The **nth Catalan number** is defined as: $$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$$ for $n \geq 0$. The first few values are: $C_0=1, C_1=1, C_2=2, C_3=5, C_4=14, C_5=42, ...$ They also satisfy the recurrence: $C_0 = 1$ and $C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$ ## Worked Example **Find $C_3$:** $$C_3 = \frac{1}{3+1}\binom{2(3)}{3} = \frac{1}{4}\binom{6}{3}$$ $$= \frac{1}{4} \cdot \frac{6!}{3!3!} = \frac{1}{4} \cdot \frac{720}{6 \cdot 6} = \frac{1}{4} \cdot 20 = 5$$ **Interpretation:** $C_3 = 5$ counts, for example, the number of ways to parenthesize a product of 4 factors: - $((ab)c)d$ - $(a(bc))d$ - $(ab)(cd)$ - $a((bc)d)$ - $a(b(cd))$