How to print the nth Catalan number

A series of positive integers are known as Catalan numbers. They can be seen in various counting problems and are used to count permutations, particular lattice path kinds, etc.

Catalan numbers have the following recursive formula:

C0 = 0 and Cn+1 = Σ Ci Cn-i for n>=0 and n=>i>=0

The first few numbers of the Catalan number series are as follows:

n Catalan Number
0 1
1 1
2 2
3 5
4 14

Problem statement

Given an integer n. Find the first n Catalan numbers.

Example 1:

  • Input: n=10
  • Output: 1 1 2 5 14 42 132 429 1430 4862

Example 2:

  • Input: n=5
  • Output: 1 1 2 5 14

Solution

We can use the following recursive formula to calculate the nth Catalan number:

C0 = 0 and Cn+1 = Σ Ci Cn-i for n>=0 and n=>i>=0

The steps to implement the recursive formula are as follows:

  1. Define n.

  2. The base case is, if n is less than or equal to 1, it returns 1.

  3. The recursive step is where we return the sum of the product of i-th Catalan number and n-i-1-th Catalan number for all i between 0 and n (0 inclusive).

    • Time complexity of this solutions is O(n2).
    • Space complexity of this solution is O(N).O(N).

Code example

Let’s look at the code below:

class Main {
    static int nthCatalanNum(int n) {
        int sum = 0;
        if(n<=1) return 1;
        for(int i=0; i<n; i++) {
            sum += nthCatalanNum(i) * nthCatalanNum(n-i-1);
        }
        return sum;
    }
    public static void main(String[] args) {
        int n=5;
        System.out.println("Catalan numbers upto " + n + " are as follows:");
        for (int i=0; i<n; i++) {
            System.out.print(nthCatalanNum(i) + " ");
        }
    }
}

Explanation

  • Line 3: We define the nthCatalan() funtion.
  • Line 4: We define sum and initialized it to zero.
  • Line 5: We have the base case, when n is less than or equal to 1, then return 1.
  • Lines 6-8: We implement the recursive step via the for loop to find the nth Catalan number.
  • Line 13: We define n.
  • Lines 15-17: We calculate the first n Catalan numbers.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved