1.2 Eulerian numbers
For \(n, k \in \mathbb {N}\), the Eulerian number is the count
\[ A_{n+1,k+1} \; =\; \# \{ \sigma \in \mathfrak {S}_{n+1} : \operatorname {des}(\sigma ) = k\} . \]
We write eulerian n k in the formalization, indexed so that \(n\) is “permutation size minus one” and \(k\) ranges over \(0, \dots , n\).
\(\sum _{k=0}^{n} A_{n+1,k+1} = (n+1)!\).
\(A_{n+1,1} = A_{n+1,n+1} = 1\), and for \(0 \leq k \leq n\), \(A_{n+1,k+1} = A_{n+1,(n-k)+1}\).
For all \(n, k \in \mathbb {N}\),
\[ A_{n+2,k+2} \; =\; (k+2) \cdot A_{n+1,k+2} \, +\, (n+1-k) \cdot A_{n+1,k+1}. \]
Proof is by the value-based “insert max” bijection \(\mathfrak {S}_{n+2} \simeq \mathfrak {S}_{n+1} \times \{ 0, \dots , n+1\} \).
For all \(n, x \in \mathbb {N}\),
\[ x^{\, n+1} \; =\; \sum _{k=0}^{n} A_{n+1,k+1} \cdot \binom {x+k}{n+1}. \]
In \(\mathbb {Z}\),
\[ A_{n+1,k+1} \; =\; \sum _{j=0}^{k} (-1)^{j} \binom {n+2}{j} (k+1-j)^{\, n+1}. \]
Proved by Worpitzky inversion using an alternating-binomial Kronecker identity.