Lesson 2

Surprisingly, Catalan numbers appear in many different combinatorial problems.

We will see around ten such examples below. This sequence is seemingly one of the most popular (alongside powers of two, Fibonacci numbers, and binomial coefficients). The book “Catalan Numbers” lists \(214\) different manifestations of this sequence. The longest article in the Online Encyclopedia of Integer Sequences is dedicated specifically to the Catalan numbers.

As often happens (see Stigler's law of eponymy), the Catalan numbers were not named after their discoverer. As early as 1751, Euler found the formula for the number of triangulations of a polygon, and independently Segner proved it. The sequence and its formula were rediscovered multiple times. Catalan himself found the formula for the Catalan numbers in 1838. The term “Catalan numbers” came into use only in the 1960s.