Bell triangle

O(n²)

The Bell triangle is constructed row by row: row 0 is [1]. Each new row starts with the last element of the previous row, and every subsequent entry equals the entry to its left plus the entry diagonally up-left (previous row, same column index). The left-edge values 1, 1, 2, 5, 15, 52, 203, ... are the Bell numbers B_n, which count the total number of partitions of an n-element set across all possible numbers of blocks.

Number triangle
Press ▶ to run
Edit the input and press Play

How it works

  1. Start row 0 with the single value 1
  2. Begin each new row with the last element of the previous row
  3. Each subsequent entry = left neighbour + up-left diagonal entry
  4. Read off Bell numbers from the left edge

Pseudocode

1bellTriangle(n):                    # O(n²)2  rows = [[1]]3  for r in 1..n-1:4    rows[r] = array of r+1 nulls5    rows[r][0] = rows[r-1][r-1]    # carry last of prev row6    for c in 1..r:7      rows[r][c] = rows[r][c-1] + rows[r-1][c-1]8  # left edge rows[r][0] = Bell number B_r