# Catalan Numbers

Author: Mihnea Brebenel

### Prerequisites

Resources | ||||
---|---|---|---|---|

cp-algo | Well documented article. |

The Catalan numbers are a sequence of positive integers that can be very useful in counting problems in combinatorics. The $n$-th Catalan can be expressed as follows using binomial coeffiecients:

They also have the recurrence formula

which can also be expressed as

The first $5$ Catalan numbers are

n | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|

$C_n$ | 1 | 1 | 2 | 5 | 14 | 42 |

# Applications

The Catalan numbers can be used to represent a wide variety of things.

For example, $C_n$ is equal to the number of valid parenthesis expressions of length $2n$. Take, for instance, $C_3=5$:

`()()()`

`(())()`

`()(())`

`((()))`

`(()())`

It's also equal to the number of full binary trees with $n+1$ leaves. The following image shows the $5$ binary trees with $4$ leaves:

$C_n$ is also the number of monotonic lattice paths along the edges of a $n \times n$ grid that don't pass above the diagonal. The paths start in the lower left corner and ends in the upper right corner.

For example, there are $C_4=14$ paths in a $4 \times 4$ grid:

The next two examples are a bit more niche, but they're still interesting to think about.

Consider a convex polygon with $n+2$ sides divided into $n$ triangles by connecting vertices with non-intersecting lines. The number of different ways to divide the polygon in this way is equal to $C_n$.

Here's the particular case for $n=3$ in which we have $C_3=5$:

$C_n$ is also equal to the number of mountain ranges of length $2n$ consisting of $n$ upstrokes and $n$ downstrokes.

# Bracket Sequences I

Focus Problem – try your best to solve this problem before continuing!

## Explanation

The problem is a direct application of Catalan numbers. The answer for $N$ is the $N/2$ Catalan Number.

## Implementation

**Time Complexity:** $\mathcal{O}(N)$

C++

#include <iostream>using namespace std;const int MOD = 1e9 + 7;const int MAXN = 1e6;long long fac[MAXN + 1];long long inv[MAXN + 1];

Python

MAXN = 10**6MOD = 10**9 + 7fac = [0] * (MAXN + 1)inv = [0] * (MAXN + 1)Code Snippet: Combinatorics Functions (from the module) (Click to expand)n = int(input())

# Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Leetcode | Easy | ## Show TagsCatalan, Combinatorics | |||

SPOJ | Normal | ## Show TagsCatalan, Combinatorics | |||

CSES | Hard | ## Show TagsCatalan, Combinatorics |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!