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

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

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)$

Copy
#include <iostream>

using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1e6;

long long fac[MAXN + 1];
long long inv[MAXN + 1];

Copy
MAXN = 10**6
MOD = 10**9 + 7

fac = [0] * (MAXN + 1)
inv = [0] * (MAXN + 1)


 Code Snippet: Combinatorics Functions (from the module) (Click to expand)

n = int(input())

Problems