# 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:

• 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.