Catalan Number

The Catalan numbers are a sequence of natural numbers that arise in various counting problems such as counting binary trees, parenthesizations, and triangulations.

The nth Catalan number is given by the formula:

C(n) = (2n)! / (n+1)!n!

Or recursively:

C(n) = Σ C(i) * C(n-i-1) for i from 0 to n-1

Java example:

1
2
3
4
5
6
7
8
9

int catalanNumber(int n) {
  if (n <= 1) return 1;

  int res = 0;
  for (int i=0; i<n; i++) {
    res += catalanNumber(i) * catalanNumber(n-i-1);
  }
  return res;
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int catalanNumber(int n) {
  if (n <= 1) return 1;
  
  int res = 0;
  for (int i=0; i<n; i++) {
    res += catalanNumber(i) * catalanNumber(n-i-1); 
  }

  return res;
}

Python example:

1
2
3
4
5
6
7
8
9

def catalan_number(n):
  if n <= 1:
    return 1

  res = 0
  for i in range(n):
    res += catalan_number(i) * catalan_number(n-i-1)

  return res

The first few Catalan numbers are 1, 1, 2, 5, 14, 42…

Catalan numbers have applications in combinatorics and appear frequently in tree- and sequence-related problems.

Catalan numbers are a sequence of natural numbers that have many applications in combinatorial mathematics.

Imagine you want to find the number of different ways you can arrange a certain number of pairs of parentheses so that they are balanced. Catalan numbers provide the solution to this problem.

The nth Catalan number can be expressed with a formula, but for those new to the subject, it might be helpful to understand through an example:

  • For 0 pairs of parentheses, there’s only 1 way to arrange them (an empty string), so the 0th Catalan number is 1.
  • For 1 pair, there’s also only 1 way: (). So, the 1st Catalan number is 1.
  • For 2 pairs, there are 2 ways: (()) and ()(). The 2nd Catalan number is 2.
  • For 3 pairs, there are 5 ways, making the 3rd Catalan number 5.

You can see that the sequence starts: 1, 1, 2, 5, 14, …

Catalan numbers are not just about parentheses; they also show up in different areas like counting the number of paths in a grid, the number of expressions containing a certain number of matched pairs, and more.

Catalan numbers are a tool for counting certain arrangements or patterns that follow specific rules.

Divide and Conquer

The Divide and Conquer approach to generating parentheses is about finding the number of valid strings you can create with “n” pairs of parentheses. Here’s a simpler way to understand it:

Imagine you have a task to arrange a certain number of pairs of brackets (like these: ()) in a way that makes sense, meaning they are balanced and properly closed.

  • “Divide” means breaking the problem into smaller parts. Instead of figuring out all the arrangements at once, you work with a smaller number of pairs first.
  • “Conquer” means solving those smaller problems and then putting the solutions together to solve the original problem.

For example, if you want to arrange 3 pairs of parentheses, you can break it down and first find the arrangements for 1 pair and 2 pairs, and then use those solutions to figure out the arrangements for 3 pairs.

This Divide and Conquer approach helps simplify the problem, making it easier to find the number of valid strings formed with “n” pairs of parentheses.

Role of Catalan Numbers

Catalan numbers play a significant role in the Divide and Conquer approach to generating valid arrangements of parentheses, and here’s how:

A Catalan number is a sequence of numbers used in various counting problems. The nth Catalan number specifically tells you the number of valid ways to arrange n pairs of parentheses.

For example:

  • The 0th Catalan number is 1, meaning there’s only one way to arrange 0 pairs of parentheses (by having no parentheses at all).
  • The 1st Catalan number is also 1, meaning there’s one way to arrange 1 pair of parentheses: ().
  • The 2nd Catalan number is 2, meaning there are two ways to arrange 2 pairs of parentheses: (()) and ()().

When dealing with the problem of arranging n pairs of parentheses, you can directly use the nth Catalan number to tell you how many valid arrangements there are. It’s a mathematical shortcut to solving the problem, connecting the arrangement of parentheses to a well-known sequence of numbers.

In other words, instead of manually figuring out the arrangements through a Divide and Conquer algorithm, you can look up the nth Catalan number, and it will give you the answer for n pairs of parentheses. It’s like having a ready-made solution that applies to this specific problem.