Lesson 1

The Catalan number \(C(n)\) is defined as the number of correct bracket sequences with \(n\) opening and \(n\) closing brackets. The number \(C(n)\) can be found using the following recurrence relation. A correct bracket sequence must begin with an opening bracket. Let us find the matching closing bracket. The whole sequence then looks like this: \[\textcolor{#90ee90}{(}\underbrace{(())()((()))}_{\text{\(l\) pairs}}\textcolor{#90ee90}{)}\underbrace{(()(())()())()}_{\text{\((n-1-l)\) pairs}}\] It is easy to see that between these two brackets, as well as immediately after them, there must be correct bracket sequences. Therefore, \[C(n)=\sum_{l=0}^{n-1}C(l)C(n-1-l)=\sum_{l+r=n-1}C(l)C(r) \ .\] At the same time, \(C(0)=1\): there is one way to place no brackets at all. Accordingly, the Catalan numbers can be computed sequentially: \[\begin{align*}C(0)&= 1,\\ C(1)&= C(0)C(0)=1 \times 1 = 1,\\ C(2)&= C(0)C(1)+C(1)C(0) = 1 \times 1 + 1 \times 1 = 2,\\ C(3)&= C(0)C(2)+C(1)C(1)+C(2)C(0)=1 \times 2 + 1 \times 1 + 2 \times 1 = 5.\\\end{align*}\]

The first few Catalan numbers: