|
%I #59 Oct 02 2022 12:49:05
%S 1,1,1,3,4,20,36,252,576,5184,14400,158400,518400,6739200,25401600,
%T 381024000,1625702400,27636940800,131681894400,2501955993600,
%U 13168189440000,276531978240000,1593350922240000,36647071211520000,229442532802560000,5736063320064000000
%N Number of permutations of degree n with greatest sum of distances.
%C 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.
%H Georg Fischer, <a href="/A062870/b062870.txt">Table of n, a(n) for n = 0..506</a> (first 301 terms from _Alois P. Heinz_)
%H Max Alekseyev, <a href="/A062870/a062870.txt">Proof of conjecture</a>
%H T. Kyle Petersen and Bridget Eileen Tenner, <a href="http://arxiv.org/abs/1202.4765">The depth of a permutation</a>, arXiv:1202.4765 [math.CO], 2012.
%H T. Kyle Petersen and Bridget Eileen Tenner, <a href="http://dx.doi.org/10.4310/JOC.2015.v6.n1.a9">The depth of a permutation</a>, Journal of Combinatorics 6 (2015), pp. 145--178.
%F 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
%F a(n) = A062869(n,floor(n^2/4)) for n>=1. - _Alois P. Heinz_, Oct 02 2022
%e (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.
%p a:= proc(n) option remember; `if`(n<2, 1+n*(n-1),
%p (n*((n-1)^2*(3*n-4)*a(n-2)-4*a(n-1)))/(4*(n-1)*(3*n-7)))
%p end:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jan 16 2014
%t 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 *)
%o (PARI) for(k=0,20,print1((2*k+1)*k!^2","(k+1)!^2",")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Dec 27 2007
%Y Cf. A002620, A062866, A062867, A062869.
%Y A007590(n) is the greatest sum of distances for a permutation of degree n. - _Dmitry Kamenetsky_, Nov 14 2017
%K nonn
%O 0,4
%A _Olivier Gérard_, Jun 26 2001
%E a(10)-a(14) from _Hugo Pfoertner_, Sep 23 2004
%E More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Dec 27 2007
|
