# User:Richard Pinch/sandbox

A combinatorial counting function for the number of descents in a permutation. Here we take a permutation $(a_1,\ldots,a_n)$ of $(1,\ldots,n)$ and count as a descent any $i$ such that $a_i > a_{i+1}$. We let $$\left\langle{ n \atop k }\right\rangle$$ denote the number of permutations on $n$ elements with $k$ descents. It satisfies the recurrence relation $$\left\langle{ n \atop k }\right\rangle = (n-k) \left\langle{ n-1 \atop k-1 }\right\rangle + (k+1) \left\langle{ n-1 \atop k }\right\rangle$$
The Eulerian polynomial is the generating function $$S_n(t) = \sum_{k=0}^n \left\langle{ n \atop k }\right\rangle t^k \ .$$ The recurrence relation may be written as $$S_{n+1}(t) = (1+nt) S_n(t) + t(1-t)S'_n(t) \ .$$
The Eulerian numbers appear in a related context. We define an excedance of a permutation to be the number of $i$ such that $a(i) > i$ (weak if $a_i \ge i$). Then the number of permutations with $k$ excendances is equal to the number with $k+1$ weak excedances, and is in turn equal to $\left\langle{ n \atop k }\right\rangle$.