How to Compute the Catalan Number?

The Catalan number as described here is one of the well-known combinatorial number that has quite a few applications. For example, C(n) can be used to count the number of unique binary search trees of N nodes.

The Catalan numbers can be computed using the following equation:

catalan-number-equation

C(0) is defined as 1, and the first few Catalan numbers are:

• C(1) = 1
• C(2) = 2
• C(3) = 5
• C(4) = 14
• C(5) = 132
• C(6) = 429
• C(7) = 1430
• C(8) = 4862

Another equation to compute the catalan is:

catalan-number-equation-combinatices

And here is the most handy equation to compute the catalan number as we can iteratively compute C(n+1) based on the value of C(n).

where C(0) = 1

How to Compute the Catalan Numbers in Java?

Iteratively, we can use the above catalan equation to compute the catalan numbers, we need to store the intemediate results using the long type otherwise it may overflow.

1
2
3
4
5
6
7
8
9
10

class Solution {
  public long catalan(int n) {
    // Note: we should use long here instead of int, otherwise overflow
    long C = 1;
    for (int i = 0; i < n; ++ i) {
      C = C * 2 * (2 * i + 1) / (i + 2);
    }
    return C;
  }
}

class Solution {
  public long catalan(int n) {
    // Note: we should use long here instead of int, otherwise overflow
    long C = 1;
    for (int i = 0; i < n; ++ i) {
      C = C * 2 * (2 * i + 1) / (i + 2);
    }
    return C;
  }
}

O(N) time complexity and O(1) constant space.

How to Compute the Catalan Numbers in Python?

1
2
3
4
5
6
7
8
9
10

class Solution(object):
    def catalan(self, n):
        """
        :type n: int
        :rtype: int
        """
        C = 1
        for i in range(0, n):
            C = C * 2*(2*i+1)/(i+2)
        return int(C)

class Solution(object):
    def catalan(self, n):
        """
        :type n: int
        :rtype: int
        """
        C = 1
        for i in range(0, n):
            C = C * 2*(2*i+1)/(i+2)
        return int(C)

How to Compute the catalan Numbers in C/C++?

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    int64_t numTrees(int n) {
        int64_t C = 1;
        for (int i = 0; i < n; ++i) {
          C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int) C;        
    }
};

class Solution {
public:
    int64_t numTrees(int n) {
        int64_t C = 1;
        for (int i = 0; i < n; ++i) {
          C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int) C;        
    }
};

How to Compute the Catalan Numbers in Magik?

Magik is a programming language that is developed by GE.

_package sw
_global catalan << _proc@catalan(n)
  _local C << 1, i < < 1
  _while i < n
  _loop
    C < < C * 2 * (2 * i + 1) / (i + 2)
    i +<< 1
  _endloop
_endproc

Example usage:

Magik > catalan(2)
2

How to Compute the Catalan Numbers in Javascript?

1
2
3
4
5
6
7
8
9
10
11

/**
 * @param {number} n
 * @return {number}
 */
var catalan = function(n) {
    let C = 1;
    for (let i = 0; i < n; ++i) {
        C = C * 2 * (2 * i + 1) / (i + 2);
    }
    return C;
};

/**
 * @param {number} n
 * @return {number}
 */
var catalan = function(n) {
    let C = 1;
    for (let i = 0; i < n; ++i) {
        C = C * 2 * (2 * i + 1) / (i + 2);
    }
    return C;
};

There are also several different ways to compute the Catalan numbers: How to Compute the Catalan Numbers using Dynamic Programming Algorithm?

–EOF (The Ultimate Computing & Technology Blog) —