# Eulerian numbers

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:

We take a permutation of \(n-1\) elements (namely 0 to \(n-1\)) with \(m\) runs and augment one of the runs by inserting a new element (namely \(n\), e.g. \(3\ 6 \ | \ 2\ | \ 1\ 4\ 5 \Rightarrow 3\ 6 \ | \ 2\ \mathbf{7}\ | \ 1\ 4\ 5\)). We can choose among \(m\) runs to augment. Wchich means we have \(m\) possibilities to augment.

We take a permutation of \(n-1\) elements (namely 0 to \(n-1\)) with \(m-1\) runs and introduce one additional run to get \(m\) runs in total. Therefore, we can either add the new element (namely \(n\)) at the beginning of the original permutation or we place it

*inside*an existing run. Since we have \(n-1\) positions and \(m-1\) runs in total in the original permutation and we can not place the new element at the end of an existing run, we can choose \((n-1)-(m-1)+1\) positions for the new element.

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.