Stirlingova čísla (2. druhu)

O(n²)

Stirlingova čísla druhého druhu tvoří trojúhelník, kde S(0,0)=1, S(n,0)=0 pro n > 0, S(n,n)=1 (n prvků lze do n jednoprvkových bloků uspořádat jediným způsobem) a platí rekurence S(n,k) = k·S(n-1,k) + S(n-1,k-1). Člen k·S(n-1,k) počítá vložení nového prvku do některého z k existujících bloků; S(n-1,k-1) počítá vytvoření nového jednoprvkového bloku. Součty řádků jsou Bellova čísla.

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

Jak to funguje

  1. Počáteční hodnoty: S(0,0)=1; S(n,0)=0 pro n > 0
  2. Diagonála S(n,n)=1 pro všechna n
  3. Vnitřek: S(n,k) = k·S(n-1,k) + S(n-1,k-1)
  4. Součty řádků dávají Bellova čísla

Pseudokód

1stirling2(n):                       # O(n²)2  rows = []3  for r in 0..n-1:4    rows[r] = array of r+1 nulls5    rows[r][0] = (r == 0) ? 1 : 0  # S(0,0)=1; S(n,0)=06    rows[r][r] = 1                  # S(n,n)=17    for c in 1..r-1:8      rows[r][c] = c * rows[r-1][c] + rows[r-1][c-1]9  # row sums = Bell numbers