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

Bell Triangle

Read summary with AI tools

The Bell triangle, also known as Aitken’s array or the Peirce triangle, produces the Bell numbers 1, 2, 5, 15, 52 along its right edge. Every row starts with the last number of the row above.

Quick answer: Keep the previous row in an array. A new row starts with the last number of the previous row. Each next number is its left neighbour plus the number above that neighbour: cur[j] = cur[j − 1] + prev[j − 1]. The row grows by one number each time.

This program is part of the Series Patterns collection.

Table of contents8 sections
  1. Output
  2. How the bell triangle works
  3. Program in C
  4. Program in C++
  5. Program in Java
  6. Program in Python
  7. Time and space complexity
  8. Frequently asked questions

Bell Triangle output

Output (n = 5):

  1
  1  2
  2  3  5
  5  7 10 15
 15 20 27 37 52
Bell Triangle layout diagram, row by row (n = 5)
The numbers of the bell triangle laid out row by row (n = 5).

How the bell triangle works

The rule is simple once you see it on paper. Row 3 starts with 5, the last number of row 2. The next number is 5 plus the 2 above that 5, which is 7. Then 7 plus the 3 above it gives 10, and 10 plus 5 gives 15. The program does exactly this with two arrays: prev holds the row above and cur is being built. After printing, cur is copied into prev for the next row.

  1. Print the first row, which is just 1, and store it in prev.
  2. For i from 1 to n − 1: set cur[0] = prev[i − 1].
  3. For j from 1 to i, set cur[j] = cur[j − 1] + prev[j − 1].
  4. Print cur[0] to cur[i], copy them into prev, and move to the next line.

Key takeaways

  • Each row starts where the last one ended.
  • Every other number is its left neighbour plus the number above that neighbour.
  • Both edges carry the Bell numbers: 1, 1, 2, 5, 15 on the left and 1, 2, 5, 15, 52 on the right.
  • Two arrays, one for the old row and one for the new, are all the memory the program needs.

Bell Triangle in C

#include <stdio.h>

int main(void) {
    int n = 5;
    int prev[20], cur[20];
    prev[0] = 1;
    printf("%3d\n", 1);

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

Bell Triangle in C++

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

int main() {
    int n = 5;
    vector<int> prev(n), cur(n);
    prev[0] = 1;
    cout << setw(3) << 1 << endl;

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

Bell Triangle in Java

public class BellTriangle {
    public static void main(String[] args) {
        int n = 5;
        int[] prev = new int[n], cur = new int[n];
        prev[0] = 1;
        System.out.printf("%3d%n", 1);

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

Bell Triangle in Python

n = 5
prev = [1]
print(f"{1:3d}")

for i in range(1, n):
    cur = [prev[-1]]
    for j in range(1, i + 1):
        cur.append(cur[j - 1] + prev[j - 1])
    print("".join(f"{x:3d}" for x in cur))
    prev = cur

Time and space complexity

Row i takes O(i) additions, so the program runs in O(n²) time and uses O(n) memory for the two arrays.

Frequently asked questions

What do Bell numbers count?

The number of ways to split a set into groups. Three people can be grouped in 5 ways: all together, all apart, or one of three different pairs plus a single person. That 5 is the Bell number at the end of row 2.

Can I do it with one array?

Not easily, because each new value needs the old value at position j − 1, which the same pass has just overwritten. Two arrays keep the code clear; the extra memory is only O(n).

How is it different from Pascal’s triangle?

In Pascal’s triangle every row starts with 1 and each number adds the two numbers above it. In the Bell triangle each row starts with the last number of the previous row and the sums go along the row, so the numbers grow much faster.

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.