New: 201 pattern programs with tested code in C, C++, Java and Python Explore patterns

Catalan’s Triangle

Read summary with AI tools

Catalan’s triangle looks a little like Pascal’s triangle, but each number is the sum of the number to its left and the number above it. The last number in every row is a Catalan number: 1, 1, 2, 5, 14.

Quick answer: Keep one row in an array that starts as 1 followed by zeros. For each new row i, update the array from left to right with row[j] = row[j − 1] + row[j] for j from 1 to i, then print the first i + 1 values. The right-hand end of each row is the Catalan number.

This program is part of the Series Patterns collection.

Table of contents8 sections
  1. Catalan’s Triangle output
  2. How the catalan’s triangle works
  3. Catalan’s Triangle in C
  4. Catalan’s Triangle in C++
  5. Catalan’s Triangle in Java
  6. Catalan’s Triangle in Python
  7. Time and space complexity
  8. Frequently asked questions

Catalan’s Triangle output

Output (n = 5):

  1
  1  1
  1  2  2
  1  3  5  5
  1  4  9 14 14
Catalan's Triangle layout diagram, row by row (n = 5)
The numbers of the catalan’s triangle laid out row by row (n = 5).

How the catalan’s triangle works

The rule for the triangle is C(i, j) = C(i, j − 1) + C(i − 1, j): the number to the left in the same row plus the number above in the previous row. A single array can hold both rows at once. Going left to right, row[j − 1] already holds the new value for this row, while row[j] still holds the old value from the row above. Adding them gives the new row[j]. At the end of a row, row[i] was still 0, so the last number copies its left neighbour, which is why each row ends with a repeated value.

  1. Fill an array with n zeros and set row[0] = 1.
  2. Run the outer loop for i from 0 to n − 1.
  3. For j from 1 to i, set row[j] = row[j − 1] + row[j].
  4. Print row[0] to row[i], three characters wide, and move to the next line.

Key takeaways

  • Each number is the one to its left plus the one above.
  • Updating the array from left to right lets one array hold the old row and the new row at the same time.
  • Every row ends with two equal numbers, and that number is the next Catalan number.
  • Catalan numbers count balanced bracket strings: there are 5 ways to write three pairs of brackets.

Catalan’s Triangle in C

#include <stdio.h>

int main(void) {
    int n = 5;
    int row[20] = {1};

    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= i; j++)
            row[j] = row[j - 1] + row[j];
        for (int j = 0; j <= i; j++)
            printf("%3d", row[j]);
        printf("\n");
    }
    return 0;
}

Catalan’s Triangle in C++

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int main() {
    int n = 5;
    vector<int> row(n, 0);
    row[0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= i; j++)
            row[j] = row[j - 1] + row[j];
        for (int j = 0; j <= i; j++)
            cout << setw(3) << row[j];
        cout << endl;
    }
    return 0;
}

Catalan’s Triangle in Java

public class CatalansTriangle {
    public static void main(String[] args) {
        int n = 5;
        int[] row = new int[n];
        row[0] = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= i; j++)
                row[j] = row[j - 1] + row[j];
            for (int j = 0; j <= i; j++)
                System.out.printf("%3d", row[j]);
            System.out.println();
        }
    }
}

Catalan’s Triangle in Python

n = 5
row = [1] + [0] * (n - 1)

for i in range(n):
    for j in range(1, i + 1):
        row[j] = row[j - 1] + row[j]
    for j in range(i + 1):
        print(f"{row[j]:3d}", end="")
    print()

Time and space complexity

Each row costs O(i) additions, so n rows take O(n²) time. The array holds one row, so the extra memory is O(n).

Frequently asked questions

What are Catalan numbers used for?

They count many things that grow in the same way: balanced strings of brackets, the shapes of binary trees with n nodes, and the ways to split a polygon into triangles. For 3 pairs of brackets there are 5 balanced strings, which matches the 5 at the end of row 3.

How is it different from Pascal’s triangle?

In Pascal’s triangle each number adds the two numbers above it and the rows are symmetrical. In Catalan’s triangle each number adds the number above and the number to its left, and the rows are not symmetrical: 1 3 5 5.

Why must the inner loop go from left to right?

Because row[j] needs the new value of row[j − 1] and the old value of row[j]. Going left to right gives exactly that. Going right to left would mix up the two rows and print wrong numbers.

Authored by

Ghanendra Yadav runs Pattern Programs from Bangalore, India. The site started in 2020 to help students practise loops and logic through pattern programs in C, C++, Java and Python. Every program published here is compiled and run before it goes live, and the output shown is the real output.

Latest articles

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.