# Does anybody spot anything familiar in this integer sequence?

$0,3,9,21,40,67,106,154,220,298,395,510,644,\dots$

These are the maxima of the distances between permutations of length $n$ up to $n=13$ according to a modified version of Spearman's footrule number calculated by

$\sum_{i=1}^{n} |i-p_i| (n-i+1)$

I cannot find any formula for the above sequence. I've looked up the sequence at OEIS but nothing came up. I'm not a mathematician and don't even know where to start for finding a formula, so any help would be greatly appreciated. For reference, here is the output of my program:

 n=2 max=3 at (2 1) n=3 max=9 at (3 1 2) n=4 max=21 at (4 3 1 2) n=5 max=40 at (5 4 1 2 3) n=6 max=67 at (6 5 4 1 2 3) n=7 max=106 at (7 6 5 1 2 3 4) n=8 max=154 at (8 7 6 1 2 3 4 5) (8 7 6 5 1 2 3 4) n=9 max=220 at (9 8 7 6 1 2 3 4 5) n=10 max=298 at (10 9 8 7 1 2 3 4 5 6) n=11 max=395 at (11 10 9 8 7 1 2 3 4 5 6) n=12 max=510 at (12 11 10 9 8 1 2 3 4 5 6 7) n=13 max=644 at (13 12 11 10 9 8 1 2 3 4 5 6 7) 

Strange thing at $n=8$ as well.

• What is the $p_i$ and how do you measure distance between permutations? I know it is sort of an aside to the question, but I just want to verify that the sequence is correct first. – TravisJ Apr 8 '15 at 16:34
• Yes, this question is missing information. – Thomas Andrews Apr 8 '15 at 16:37
• Apparently, $~\dfrac{a_k+a_{k-1}}2\simeq k^2\sqrt k~,~$with $a_0=0$. – Lucian Apr 8 '15 at 17:57

Here's a partial solution, assuming for now that the permutation exhibiting the maximum distance looks like $(n, n-1, \ldots, n-a+1, 1, 2, \ldots, n-a)$. (You can probably prove that a local maximum must have this form.) The score can be computed in closed form for such a permutation; you get $$S(n,a)=\frac{1}{6} \left(4 a^3-9 a^2 n-3 a^2+6 a n^2+3 a n-a\right)+\frac{1}{2} a (a-n-1) (a-n).$$
To find the optimal $a$, let $a=\alpha n$, and assume first that $\alpha\le1/2$. Define $$f(x)=\begin{cases} (1-2x)(1-x),& 0\le x\le \alpha\\ \alpha(1-x),& \alpha < x \le 1 \end{cases}$$ Then the score is the Riemann sum for $f$, up to scaling. But $$\int_0^1 f(x)\,dx = \frac{7 \alpha^3}{6}-\frac{5 \alpha^2}{2}+\frac{3 \alpha}{2};$$ it's easy to see that the integral is maximized at $\alpha=3/7$. (A similar argument shows that you don't do as well for $\alpha>1/2$.) Accordingly, we expect the score to be maximized at $a=\langle \frac{3n}7\rangle$ (the closest integer to $3n/7$. Indeed, the expression $S(n, \langle \frac{3n}7\rangle)$ produces the correct sequence of values: $$0,3,9,21,40,67,106,154,220,298,395,510,644,803,980,1190,1421,1684,1976,\ldots$$