Catalanův trojúhelník

O(n²)

Catalanův trojúhelník (známý také jako trojúhelník hlasovacích čísel) má jedničky v nejlevějším sloupci a splňuje C[r][k] = C[r][k-1] + C[r-1][k] pro k ≥ 1, přičemž buňky mimo rozsah bere jako 0. Prvek C[r][k] počítá počet posloupností r+1 hlasů, v nichž kandidát A neustále vede nad kandidátem B s konečným výsledkem k+1 ku r-k. Nejpravější prvek každého řádku, C[r][r], je (r+1)-té Catalanovo číslo.

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

Jak to funguje

  1. Nastav C[r][0] = 1 pro každý řádek r
  2. Pro každou vnitřní buňku přičti levého souseda a buňku přímo nad ní
  3. Diagonála C[r][r] dává Catalanovo číslo C_r
  4. Součty řádků rostou jako binomické koeficienty

Pseudokód

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