Catalan's triangle

O(n²)

Catalan's triangle (also called the ballot-number triangle) has 1s in the leftmost column and satisfies C[r][k] = C[r][k-1] + C[r-1][k] for k ≥ 1, treating out-of-range cells as 0. The entry C[r][k] counts the number of sequences of r+1 votes in which candidate A always leads candidate B with a final tally of k+1 to r-k. The rightmost entry of each row, C[r][r], is the (r+1)-th Catalan number.

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

How it works

  1. Set C[r][0] = 1 for every row r
  2. For each interior cell, add the left neighbour and the cell directly above
  3. The diagonal C[r][r] gives Catalan number C_r
  4. Row sums grow as binomial coefficients

Pseudocode

1catalanTriangle(n):                 # O(n²)2  rows = []3  for r in 0..n-1:4    rows[r] = array of r+1 nulls5    for c in 0..r:6      if c == 0:7        rows[r][c] = 1              # left edge8      else:9        above = (c <= r-1) ? rows[r-1][c] : 010        rows[r][c] = rows[r][c-1] + above11  # diagonal rows[r][r] = Catalan number C_r