# 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 .