Catalan Numbers

Combinatorics Progress

Completed0/11

0 completed0 in progress

Catalan Numbers

Catalan Numbers and its applications in combinatorics.

Author: Jaden Park

Introduction

Catalan numbers form a sequence of natural numbers that play an important role in various counting problems, often involving recursively-defined structures. They are named after the Belgian mathematician Eugène Charles Catalan.

The sequence of Catalan numbers begins with $1, 1, 2, 5, 14, 42, 132,$ and so on. Each number in the sequence is denoted as $C_{n},$ where $n$ is the position in the sequence, starting from $0.$

Formula

The $n$ th Catalan number can be directly calculated using the formula:

C_{n} = \frac{1}{n + 1}{{2n} \choose {n}} = \frac{(2n)!}{(n + 1)! n!}

where $n \geq 0$ and ${{2n} \choose {n}}$ is the binomial coefficient.

Recursive Definition

Catalan numbers can also be defined recursively as follows:

C_{0} = 1 \;\;\textrm{and}\;\; C_{n +1} = \sum_{i = 0}^{n}{C_{i} C_{n - i}} \;\;\textrm{for}\;\; n \geq 0

Applications

Basically all the different stuff you might see involving them (not just math competitons).

Counting the number of correct bracket expressions involving $n$ pairs of brackets.
Counting the number of rooted binary trees with $n + 1$ leaves.
Counting the number of ways a convex polygon with $n + 2$ sides can be cut into triangles by connecting vertices with non-crossing lines.
Counting the number of paths along the edges of a grid (without crossing the diagonal) from one corner to the opposite corner.
Counting the number of non-isomorphic ordered trees with $n + 1$ vertices.

Here are some examples.

Example

How many correct bracket expressions can be made with $3$ pairs of brackets?

Solution

Here, we look for $C_{3},$ the third Catalan number.

Using the formula:

C_{3} = \frac{1}{3 + 1} {{2 \cdot 3} \choose {3}} = \frac{1}{4} {{6} \choose {3}} = \frac{1}{4} \cdot \frac{6!}{3!3!} = 5

So, there are $5$ different correct bracket expressions that can be made with $3$ pairs of brackets.

Example

How many rooted binary trees are there with 4 leaves?

A binary tree is a tree in which each node has at most two children. The children are usually called left and right.

Solution

For rooted binary trees, we use $C_{n - 1}$ for $n$ leaves. So, for $4$ leaves, we find $C_{3}.$

We already calculated $C_{3} = 5.$

Example

How many ways can a hexagon ( $6$ sides) be divided into triangles by connecting non-crossing lines between the vertices?

Solution

For a hexagon, we have $n + 2 = 6,$ so $n = 4.$

Using the formula:

C_{4} = \frac{1}{4 + 1} {{2 \cdot 4} \choose {4}} = \frac{1}{5} {{8} \choose {4}} = \frac{1}{5} \cdot \frac{8!}{4!4!} = 14

Therefore, a hexagon can be divided into triangles in $14$ different ways.

Example

How many paths can you take along the edges of a $4 \times 4$ grid from the bottom left corner to the top right corner without crossing the diagonal?

Solution

For a square grid of size $n \times n,$ the number of such paths is given by the $n$ th Catalan number, $C_{n}.$ Here, $n = 4.$

Using the formula:

C_{4} = \frac{1}{4 + 1} {{2 \cdot 4} \choose {4}} = \frac{1}{5} \cdot \frac{8!}{4!4!} = 14

Therefore, there are $14$ different paths that you can take along the edges of a $4 \times 4$ grid from one corner to the opposite corner without crossing the diagonal.

Example

How many non-isomorphic ordered trees are there with $5$ vertices?

A non-isomorphic ordered tree is a tree in which the order of children at each node is considered.

Solution

The number of non-isomorphic ordered trees with $n + 1$ vertices is given by the $n$ th Catalan number. Here $n + 1 = 5,$ so $n = 4.$

We already know $C_{4}$ from the previous example, which is $14.$

Therefore, there are $14$ non-isomorphic ordered trees with $5$ vertices.

Here's a practice problem.

Practice Problem

(1993 AIME Q7)

Three numbers, $a_{1}, a_{2}, a_{3}$ , are drawn randomly and without replacement from the set

\{1, 2, 3, \ldots, 1000\}.

Three other numbers, $b_1, b_2, b_3$ , are then drawn randomly and without replacement from the remaining set of $997$ numbers. Let $p$ be the probability that, after suitable rotation, a brick of dimensions $a_1 \times a_2 \times a_3$ can be enclosed in a box of dimension $b_1 \times b_2 \times b_3$ , with the sides of the brick parallel to the sides of the box. If $p$ is written as a fraction in lowest terms, what is the sum of the numerator and denominator?

Final Notes and Tips

Somewhat useful to know, but pretty rare to get on a math contest.

Geometric Probability

Generating Functions

Combinatorics Progress

Counting

Principles

Miscellaneous

Introduction

Formula

Recursive Definition

Applications

Example

Solution

Example

Solution

Example

Solution

Example

Solution

Example

Solution

Practice Problem

Final Notes and Tips

Introduction

Formula

Recursive Definition

Applications

Example

Solution

Example

Solution

Example

Solution

Example

Solution

Example

Solution

Practice Problem

Final Notes and Tips