Number of Permutation with Pro = k equals the Eulerian Number A(n,k+1)

Question

The problem phrases as follows:

Let $\sigma = (\sigma_1, . . . , \sigma_n)$ be a permutation. We say that element $i$ is progressive if $\sigma_i > i$. We write $pro(\sigma)$ for the number of progressive elements in $\sigma$. Prove that the number of $\sigma ∈ S_n$ with $pro(\sigma) = k$ is equal to Eulerian number $A(n, k + 1)$, for all $0 ≤ k < n$.

I've tried to match up the inductive formula of both sides, but it seems that $P(n,k)$ does not only depend on $P(n-1,k)$ and $P(n-1,k-1)$. When you discard $n$ from your permutation, anything can happen. For example, when we have $(5 2 3 4 1)$ which has a $pro = 1$, if we discard the $5$ from the permutation, we are left with $(2 3 4 1)$ which has a $pro = 3$.

Answer 1

Let $\sigma=(\sigma_1,\ldots,\sigma_n)$ be a permutation of $[n]$ with $k$ progressive elements.

• If $\sigma_n=n$, let $\hat\sigma=(\sigma_1\ldots\sigma_{n-1})$.
• Otherwise, there is a unique $\ell\in[n-1]$ such that $\sigma_\ell=n$, and we define $\hat\sigma=(\hat\sigma_1\ldots\hat\sigma_{n-1})$ by $$\hat\sigma_i=\begin{cases}\sigma_i,&\text{if }i\ne\ell\\\sigma_n,&\text{if }i=\ell\end{cases}$$ for $i\in[n-1]$.

In the first case $\hat\sigma$ is a permutation of $[n-1]$ with $k$ progressive elements. In the second case, $\ell$ is a progressive element of $\sigma$ and $n$ is not, so $\hat\sigma$ is a permutation of $[n-1]$ with $k$ progressive elements if $\ell$ is a progressive element of $\sigma$, and with $k-1$ progressive elements if $\ell$ is not a progressive element of $\sigma$.

Reversing the process, we can start with any permutation $\pi=(\pi_1\ldots\pi_{n-1})$ of $[n-1]$ and extend it to a permutation $\sigma=(\sigma_1\ldots\sigma_n)$ of $[n]$ in such a way that $\pi=\hat\sigma$:

• We can simply let $\sigma=(\pi_1\ldots\pi_{n-1}n)$.
• We can pick an $\ell\in[n-1]$, set $\sigma_\ell=n$, let $\sigma_n=\pi_\ell$, and let $\sigma_i=\pi_i$ for $i\in[n-1]\setminus\{\ell\}$.

In the first case, $\sigma$ has the same progressive elements as $\pi$. In the second case, $\sigma$ has the same progressive elements as $\pi$ if $\ell$ is one of those elements; if not, then the progressive elements of $\sigma$ are those of $\pi$ together with $\ell$, so that $\operatorname{pro}(\sigma)=\operatorname{pro}(\pi)+1$.

Let $p(n,k)$ be the number of permutations of $[n]$ with $k$ progressive elements. We’ve just seen that we can start with any permutation of $[n-1]$ with $k$ progressive elements and extend it in $k+1$ ways to a permutation of $[n]$ with $k$ progressive elements, and that we can start with any permutation of $[n-1]$ with $k-1$ progressive elements and extend it in $$(n-1)-(k-1)=n-k$$ ways to a partition of $[n]$ with $k$ progressive elements. Each permutation $\sigma$ of $[n]$ with $k$ progressive elements arises in exactly one of these ways from $\hat\sigma$, so

$$p(n,k)=(k+1)p(n-1,k)+(n-k)p(n-1,k-1)\;.$$

This is the recurrence for the Eulerian numbers, so to complete the argument you need only verify that the initial conditions are the same.