login
A328378
Number of permutations of length n that possess the maximal sum of distances between contiguous elements.
1
1, 1, 2, 4, 2, 8, 8, 48, 72, 576, 1152, 11520, 28800, 345600, 1036800, 14515200, 50803200, 812851200, 3251404800, 58525286400, 263363788800, 5267275776000, 26336378880000, 579400335360000, 3186701844480000, 76480844267520000, 458885065605120000, 11931011705733120000
OFFSET
0,3
COMMENTS
From Andrew Howroyd, Oct 16 2019: (Start)
No permutation with maximal sum of distances between contiguous elements can contain three contiguous elements a, b, c such that a < b < c or a > b > c. Otherwise removing b will not alter the sum and then appending b to the end of the permutation will increase it so that the original permutation could not have been maximal. In this sense all solution permutations are alternating.
For odd n consider an alternating permutation of the form p_1 p_2 ... p_n with p_1 > p2, p_2 < p_3, etc. The sum of distances is given by (p_1 + 2*p_3 + 2*p_5 + ... 2*p_{n-2} + p_n) - 2*(p_2 + p_4 + ... p_{n-1}). This is maximized by choosing the central odd p_i to be as highest possible and the even p_i to be least possible but other than that the order does not alter the sum. Similar arguments can be made for p_1 < p_2 and for the case when n is even.
The above considerations lead to a formula for this sequence with the maximum sum being given by A047838(n). (End)
FORMULA
a(2*n) = 2*(n-1)!^2 for n > 0; a(2*n+1) = 4*n!*(n-1)! for n > 0. - Andrew Howroyd, Oct 16 2019
D-finite with recurrence: - (12*n-20)*a(n) + 4*a(n-1) + (3*n-2)*(n-3)*(n-2)*a(n-2) = 0. - Georg Fischer, Nov 25 2022
Sum_{n>=0} 1/a(n) = BesselI(0, 2)/2 + BesselI(1, 2)/4 + 2 = A070910/2 + A096789/4 + 2. - Amiram Eldar, Oct 03 2023
EXAMPLE
(1,3,2) is a permutation of length 3 with distance sum |1-3| + |3-2| = 2 + 1 = 3. For n = 3, the 4 permutations with maximum sum of distances are (1,3,2), (2,1,3), (2,3,1) and (3,1,2).
MATHEMATICA
A328378[n_]:=If[n<2, 1, 2(Floor[n/2]-1)!^2If[Divisible[n, 2], 1, n-1]]; Array[A328378, 30, 0] (* Paolo Xausa, Aug 13 2023 *)
PROG
(Python) # See Github link
(PARI) a(n)={if(n<2, n>=0, 2*(n\2-1)!^2*if(n%2, n-1, 1))} \\ Andrew Howroyd, Oct 16 2019
CROSSREFS
Cf. A047838 is the maximum distance for every length n, except for n = 0 and n = 1.
Sequence in context: A129178 A152874 A324716 * A296429 A065286 A068217
KEYWORD
nonn
AUTHOR
EXTENSIONS
Terms a(12) and beyond from Andrew Howroyd, Oct 16 2019
STATUS
approved