Bellův trojúhelník

O(n²)

Bellův trojúhelník se staví řádek po řádku: řádek 0 je [1]. Každý nový řádek začíná posledním prvkem předchozího řádku a každý další prvek se rovná součtu levého souseda a prvku diagonálně vlevo nahoře (předchozí řádek, stejný index sloupce). Hodnoty na levém okraji 1, 1, 2, 5, 15, 52, 203, … jsou Bellova čísla B_n, která počítají celkový počet rozkladů n-prvkové množiny.

Číselný trojúhelník
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Začni řádek 0 jedinou hodnotou 1
  2. Každý nový řádek začni posledním prvkem předchozího řádku
  3. Každý další prvek = levý soused + diagonála vlevo nahoře
  4. Bellova čísla čti z levého okraje

Pseudokód

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