A000108

A000108 is the OEIS identifier for the sequence of Catalan numbers. This sequence of natural numbers arises in various combinatorial problems, often involving recursively defined objects. The first few terms of the sequence are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862.

Catalan numbers are denoted by C_n, where n starts from 0. The explicit formula for the n-th Catalan number is given by C_n = (1/(n+1)) * (2n choose n), which can also be written as C_n = (2n)! / ((n+1)! * n!). Alternatively, they can be defined by the recurrence relation C_0 = 1 and C_{n+1} = sum_{i=0 to n} (C_i * C_{n-i}) for n >= 0.

One of the most well-known applications of Catalan numbers is counting the number of ways to correctly match n pairs of parentheses. For example, with n=3, there are C_3 = 5 ways: ((())), (()()), (())(), ()(()), ()()(). They also count the number of full binary trees with n+1 leaves, the number of monotonic paths on a grid from (0,0) to (n,n) that do not go above the main diagonal, and the number of ways to triangulate a convex (n+2)-gon into n triangles.