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 AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
You TubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved