Lesson 1

Catalan numbers appear in a variety of combinatorial problems. There are two natural ways to prove that a given numerical sequence matches the sequence of Catalan numbers.

1. Construct a bijection between the considered objects and objects already known to form the sequence of Catalan numbers.

   For example, it is clear that there is a bijection between correct bracket sequences, mountain ranges, grid paths that do not enter the upper triangle, and ballot sequences where one candidate always has at least as many votes as the other. In all these problems, pairs of objects can be replaced by “\(+1\)” and “\(-1\)”, turning the condition into “the sum of each prefix is non-negative”.

2. Show that the considered sequence satisfies the same recurrence relation (or a similar one) as the Catalan numbers: \[C(n)=\sum_{l=0}^{n-1}C(l)C(n-1-l) \ .\]