Eulerova čísla

O(n²)

Eulerova čísla splňují A(n,0)=1 pro všechna n a rekurenci A(n,k) = (k+1)·A(n-1,k) + (n-k)·A(n-1,k-1). První člen počítá permutace, kde vložení nového prvku nevytvoří nový vzestup; druhý člen počítá ty, kde vzestup vznikne. Řádek n má n prvků a jeho součet je n!, protože každá permutace je započítána právě jednou. Eulerova čísla se objevují v kombinatorice, teorii pravděpodobnosti a analýze třídicích algoritmů.

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

Jak to funguje

  1. Nastav A(n,0) = 1 pro každý řádek (žádná permutace nezačíná sestupem)
  2. Použij rekurenci A(n,k) = (k+1)·A(n-1,k) + (n-k)·A(n-1,k-1)
  3. Součet každého řádku se rovná n! (všechny permutace n prvků)
  4. Řádky jsou symetrické: A(n,k) = A(n, n-1-k)

Pseudokód

1eulerian(n):                        # O(n²)2  prev = [1]                        # seed A(0,0)=13  for r in 0..n-1:4    row = array of r+1 nulls5    row[0] = 1                      # A(n,0) = 16    for c in 1..r:7      above = (c < prev.length) ? prev[c] : 08      row[c] = (c+1)*above + (r+1-c)*prev[c-1]9    prev = row.copy()10  # row sums = (r+1)!