Number of permutations with a Spearman's distance below a threshold

65 Views Asked by At

Let $[n] = \{1, . . . , n\}$ be a universe of elements. Let $S_n$ be the set of permutations on $[n]$ and for $\pi\in S_n$, let $\pi (i)$ denote the rank of the element $i$. The Spearman’s footrule distance is defined as

$$F(\pi) = \sum_{i=1}^n |i − \pi(i)|.$$

I would like to find the number of permutations that satisfy $F(\pi) \leqslant n^2/4$ for $n=4, 6, 8, \ldots$ or at least a tight upper bound.

ACHIEVED SO FAR

Property: for $i=1,\ldots,n/2$ the rank $\pi(i)$ is less than or equal to $n/2$, and for $i=n/2+1,\ldots,n$ the rank $\pi(i)$ is greater than or equal to $n/2+1$.

I know that the permutations that meet the property above satisfy $F(\pi) \leqslant n^2/4$. This is because the maximum value of $F(\pi)$ over all $\pi$ is $n^2/2$ (for even $n$).

However, for large $n$, the number of such permutations meeting this property is very small ($n/2!·n/2!$) compared to the total number of permutations ($n!$).