A conjecture

[Max Alekseyev]

On 8/21/07, Vladeta Jovovic <vladeta at eunet.yu> wrote:
>
>
> > %I A062870
> > %S A062870 1, 1, 3, 4, 20, 36, 252, 576, 5184, 14400, 158400, 518400,
> > 6739200, 25401600
> > %N A062870 Number of permutations of degree n with greatest sum of
> > distances.
> > %F A062870 Conjecture: a(n) = (n/2)!^2 if n is even else n*((n-1)/2)!^2,
> > cf. A092186.
> > %O A062870 1
> > %K A062870 ,nonn,
> > %A A062870 Vladeta Jovovic (vladeta at Eunet.yu), Aug 21 2007

Here is my proof.

Let p=(p(1),...,p(n)) be a permutation on n elements.
The "sum of distances" of this permutation is simply
\sum_{i=1}^n |p(i)-i|.
Let us define pairs (a(i),b(i)) such that {a(i),b(i)}={p(i),i} and a(i)>=b(i).
Then for every i=1,...,n we have |p(i)-i| = a(i)-b(i) and
\sum_{i=1}^n |p(i)-i| = \sum_{i=1}^n a(i)-b(i) = \sum_{i=1}^n a(i) -
\sum_{i=1}^n b(i).

Define multisets A = { a(1), a(2), ..., a(n) } and B = { b(1), b(2),
..., b(n) }. It is clear that
A U B = { 1^2, 2^2, ..., n^2 }.

Let us consider two cases depending on the oddness of n:

1) If n=2m then in order to deliver the maximum of sum_{i=1}^n a(i) -
\sum_{i=1}^n b(i) (which is 2*m^2), it must hold that A = { (m+1)^2,
(m+2)^2, ..., (2m)^2 } and B = { 1^2, 2^2, ..., m^2 }. Therefore, the
permutation p has the maximum "sum of distances" if and only if for
every i from {1, 2, ..., m}, p(i) belongs to {m+1, m+2, ..., 2m}, and
vice versa. The number of such permutations is m!^2 = (n/2)!^2.

2) If n=2m+1 then in order to deliver the maximum of sum_{i=1}^n a(i)
- \sum_{i=1}^n b(i) (which is 2*m*(m+1)), it must hold that A = { m+1,
(m+2)^2, (m+3)^2, ..., (2m+1)^2 } and B = { 1^2, 2^2, ..., m^2, m+1 }.
There are three cases possible:
(i) p(m+1) = m+1. Then the permutation p has the maximum "sum of
distances" if and only if for every i from {1, 2, ..., m}, p(i)
belongs to {m+2, ..., 2m+1}, and vice versa. The number of such
permutations is m!^2.
(ii) p(m+1) = z < m+1. Then there exists t>m+1 such that p(t)=m+1. The
permutation p has the maximum "sum of distances" if and only if for
every i from {1, 2, ..., m}, p(i) belongs to {m+2, ..., 2m+1}, and for
every i from {m+2, ..., 2m+1} \ {t}, p(i) belongs to {1, 2, ..., m} \
{k}. Since there are m different values for each z and t, the number
of such permutations is m^2*m!*(m-1)! = m*m!^2.
(iii) p(m+1) = z > m+1. Similarly to (ii), the number of such
permutations is m*m!^2.
The total number of permutations is
m!^2 + m*(m)!^2 + m*(m)!^2 = (2m+1)*m!^2 = n*((n-1)/2)!^2.

Regards,
Max