5
$\begingroup$

Eulerian numbers, denoted $e_{n,k}$, are defined as the number of permutations of $[n]$={1,2,...,n} such that there are k "ascents". (For example, the permutation 23541 of [5] would have 3 ascents, 235, 4, and 1)

How can the principle of inclusion exclusion be used so that:

$e_{n,k}=\sum_{i=0}^k(-1)^i {n+1 \choose i}(k-i)^n$

I will update this as I make progress.

We can think of the permutation as containing k groups of ascents.

So, say for $e_{n,2}$, the first value of the alternating sum is ${n+1 \choose 0}(2-0)^n=2^n$ This makes sense since we are placing n objects into 2 groups. Now we need to make up for the fact that each group must be an ascent.

$\endgroup$
1

0

You must log in to answer this question.

Browse other questions tagged .