Number of Decreasing Steps in a Permutation

Question

Represent a permutation P of the first N integers in the usual way so, for example, P = {3 6 8 5 1 2 7 4} means 1 becomes 3, 2 becomes 6, and so on. One can then define a sequence Q of (N-1) binary numbers based on the ordering:

P = {3<6<8>5>1<2<7>4}   =>   Q = {0 0 1 1 0 0 1}

I'm actually only interested in the sum of Q (3 in this example, which is simply the total number of decreasing steps in the permutation) and its distribution for a random P.

Has this been studied?

For N=64, what is the probability that this sum is less than 16?

Answer 1

These are called Eulerian numbers, sometimes denoted using langle and rangle $\genfrac\langle\rangle{0pt}{}{n}{k}$, or just $A(n,k)$, where for given $n$, the number of "sum of $Q$" is denoted as $k = 0,1,2,\ldots, n-1$.

Besides many in-site posts (I'm not going to link them), there are numerous expository materials: OEIS A008292, OEIS wiki, some college course stuff, Wolfram Mathworld, and as always wikipedia.^{Some sources follow the convention of $k$ shifted by one, $k = 1$ to $n$.}

The recurrence is well-known: $$A(n, k) = (k+1) \cdot A(n-1, k) + (n-k) \cdot A(n-1, k-1) ~,$$

and here's one of the equivalent ways of expressing the general formula: $$A(n,k)=\sum_{j=0}^k (-1)^j \binom{n+1}{j} (k+1-j)^n$$ This is essentially your desired probability mass function, off by a multiplicative factor of $n!$.

Below is the table for the first few terms, followed by the "density" plot (probability mass function, PMF) for $n = 10 \sim 20$ on the left and $n = 50 \sim 60$ on the right. $$k\\n\begin{array}{c|ccccccc} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & 1 & & & & & \\ {2} & 1 & 1 & & & & \\ {3} & 1 & {4} & 1 & & & &\\ {4} & 1 & {11} & {11} & 1 & & \\ 5 & 1 & {26} & {66} & {26} & 1 & \\ 6 & 1 & {57} & {302} & {302} & {57} & 1 \\ 7 & 1 & 120 & 1191 & 2416 & 1191 & 120 & 1 \end{array}$$ It can be shown that the "main chunk" is symmetrically centered at $\lceil (n+1)/2 \rceil$ , with quickly diminishing width as $n$ grows.

The cumulative distribution function (CDF) is $1/n!$ times the partial row sum, listed in OEIS as $A179457$. The general formula is

$$F(n,k) \equiv \sum_{j=0}^k A(n,j)\\ F(n, k) = \sum_{j = 0}^k (-1)^j (k+1-j)^n {n \choose j} ~,\quad k = 0,1,\ldots, n-1$$

As for the probability of $n = 64$ and $k \leq 15$ "less than $16$", it can be calculated (with some help from the computer) in exact. It's very small anyway. At $n = 64$ the PMF is even more concentrated than the "rightmost" (red) curve in the plot above with $n = 60$.

\begin{align} \Pr &\equiv F(64, 15) / n! \\ \Pr &=\frac{\scriptsize 3456424774730275582087132747360250797321249625498606659869067546638886\ 9017600}{64!} \\ &\approx 2.724 \cdot 10^{-13}\end{align}