Catalan numbers 1, 1, 2, 5, 14, 42, … count balanced bracket strings, binary tree shapes, ways to triangulate a polygon, and more.
The recurrence comes from splitting at the first "root":
C(0) = 1
C(n) = Σ C(i) × C(n − 1 − i) for i = 0 … n−1
That's O(n²) with a table. A closed form also exists, C(n) = C(2n, n) / (n + 1), which you can compute with the exact multiply-and-divide trick from the nCr lesson.