Eulerian numbers

O(n²)

The Eulerian numbers satisfy A(n,0)=1 for all n and the recurrence A(n,k) = (k+1)·A(n-1,k) + (n-k)·A(n-1,k-1). The first term counts permutations where inserting the new element does not create a new ascent; the second term counts those where it does. Row n has n entries and its sum is n!, since every permutation is counted once. Eulerian numbers appear in combinatorics, probability theory, and the analysis of sorting algorithms.

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

How it works

  1. Set A(n,0) = 1 for every row (no permutation starts with a descent)
  2. Use recurrence A(n,k) = (k+1)·A(n-1,k) + (n-k)·A(n-1,k-1)
  3. Each row sum equals n! (all permutations of n elements)
  4. Symmetric rows: A(n,k) = A(n, n-1-k)

Pseudocode

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)!