Catalan sequence
The Catalan sequence is a sequence of positive integers that arise as the solution to a wide variety of combinatorial problems. The first few terms of the Catalan sequence are , , , , .... In general, the th term of the Catalan sequence is given by the formula , where is the th central binomial coefficient.
Introduction
The Catalan sequence can be used to find:
- The number of ways to arrange pairs of matching parentheses.
- The number of ways a convex polygon of sides can be split into triangles by nonintersection diagonals.
- The number of rooted binary trees with exactly leaves.
- The number of paths with steps on a rectangular grid from to that do not cross above the main diagonal.
A recursive definition of the Catalan sequence is
Example
In how many ways can the product of ordered number be calculated by pairs? For example, the possible ways for are and .