A062870 Number of permutations of degree n with greatest sum of distances.

1, 1, 1, 3, 4, 20, 36, 252, 576, 5184, 14400, 158400, 518400, 6739200, 25401600, 381024000, 1625702400, 27636940800, 131681894400, 2501955993600, 13168189440000, 276531978240000, 1593350922240000, 36647071211520000, 229442532802560000, 5736063320064000000

Offset: 0

Author

Olivier Gérard, Jun 26 2001

Keywords

• nonn

Comments

Number of possible values is 1,2,3,5,7,10,13,17,21,... which I conjecture to be A033638. Maximum distance divided by 2 is the same minus one, i.e., 0,1,2,4,6,9,12,16,20,... which seems to be A002620.

Examples

			(4,3,1,2) has distances (3,1,2,2), sum is 8 and there are 3 other permutations of degree 4 {3, 4, 1, 2}, {3, 4, 2, 1}, {4, 3, 2, 1} with this sum which is the maximum possible.
		

Links

• Georg Fischer, Table of n, a(n) for n = 0..506 (first 301 terms from _Alois P. Heinz_)
• Max Alekseyev, Proof of conjecture
• T. Kyle Petersen and Bridget Eileen Tenner, The depth of a permutation, arXiv:1202.4765 [math.CO], 2012.
• T. Kyle Petersen and Bridget Eileen Tenner, The depth of a permutation, Journal of Combinatorics 6 (2015), pp. 145--178.

Crossrefs

Cf. A002620, A062866, A062867, A062869.

A007590(n) is the greatest sum of distances for a permutation of degree n. - Dmitry Kamenetsky, Nov 14 2017

Programs

Maple

a:= proc(n) option remember; `if`(n<2, 1+n*(n-1),
      (n*((n-1)^2*(3*n-4)*a(n-2)-4*a(n-1)))/(4*(n-1)*(3*n-7)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 16 2014

Mathematica

a[n_?EvenQ] := (n/2)!^2; a[n_?OddQ] := n*((n-1)/2)!^2; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Apr 15 2015 *)

PARI

for(k=0,20,print1((2*k+1)*k!^2","(k+1)!^2",")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Dec 27 2007

Formula

a(n) = (n/2)!^2 if n is even else n*((n-1)/2)!^2, cf. A092186. - Conjectured by Vladeta Jovovic, Aug 21 2007; proved (see the link) by Max Alekseyev, Aug 21 2007

a(n) = A062869(n,floor(n^2/4)) for n>=1. - Alois P. Heinz, Oct 02 2022

Extensions

a(10)-a(14) from Hugo Pfoertner, Sep 23 2004

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Dec 27 2007