Eulerian numbers

Posted on February 1, 2011 by phimuemue

Yesterday I came across the following question: How many permutations of \(n\) (different) numbers are there, that contain exactly \(m\) runs?

A "run" is an ascendins subsequence of the permutation. For example, the following permutation has three runs (seperated by a bar): \(3\ 6 \ | \ 2\ | \ 1\ 4\ 5\). We denote the number of permutations of \(n\) elements with exactly \(m\) runs by \(A_{n,m}\).

To solve this problem, we can do the following quite simple observations: There is always one possibility for permutations with one single run. This means \(A_{n,1}=1\).

If we want to generate a permutation of \(n\) elements with exactly \(m\) runs, we can do this the following ways:

The above considerations lead to the following:

\(A_{n,m}=m\cdot A_{n-1,m} + (n-m+1)\cdot A_{n-1,m-1}\)

The above numbers are called (first-kind) Eulerian numbers, which are seemingly well-known in combinatorics, but which were new to me. To be more precisely, we have that \(E_{n,m}=A_{n,m-1}\), because usually not the number of runs, but the number of borders between the runs (called "descents") is counted.