= Eulerian number
{c}
{title2=$A(n,k)$}
With the descent convention, the <Eulerian number> $A(n,k)$ counts <permutations> of $1,\ldots,n$ with exactly $k$ positions $i$ satisfying $a_i>a_{i+1}$. These positions are <permutation descents>. For $n=3$, the row is $(1,4,1)$: only `123` has no descent and only `321` has two. Inserting the largest label gives
$$
A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1),
$$
with $A(0,0)=1$ and out-of-range entries zero. Of the $n$ insertion gaps, $k+1$ preserve $k$ descents, while the remaining gaps increase the descent count. Some sources shift the second index by one, so the convention must accompany the symbol.<Enumerative Combinatorics, Volume 1 (second-edition draft) by Richard Stanley>[§1.4, Descents]{ref}
Back to article page