2
$\begingroup$

$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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – TravisJ Apr 8 '15 at 16:34
  • $\begingroup$ Yes, this question is missing information. $\endgroup$ – Thomas Andrews Apr 8 '15 at 16:37
  • $\begingroup$ Apparently, $~\dfrac{a_k+a_{k-1}}2\simeq k^2\sqrt k~,~$with $a_0=0$. $\endgroup$ – Lucian Apr 8 '15 at 17:57
2
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ This is awesome! Is there any way I can contact you? $\endgroup$ – Eric '3ToedSloth' Apr 9 '15 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.