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
Catalan’s Triangle output
Output (n = 5):
1 1 1 1 2 2 1 3 5 5 1 4 9 14 14

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.
- Fill an array with
nzeros and setrow[0] = 1. - Run the outer loop for
ifrom 0 ton − 1. - For
jfrom 1 toi, setrow[j] = row[j − 1] + row[j]. - Print
row[0]torow[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.









