

A328378


Number of permutations of length n that possess the maximal sum of distances between contiguous elements.


0



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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_{n2} + p_n)  2*(p_2 + p_4 + ... p_{n1}). 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)


LINKS

Table of n, a(n) for n=0..27.
Tomás Roca Sánchez, Github Python program along with explanations


FORMULA

a(2*n) = 2*(n1)!^2 for n > 0; a(2*n+1) = 4*n!*(n1)! for n > 0.  Andrew Howroyd, Oct 16 2019


EXAMPLE

(1,3,2) is a permutation of length 3 with distance sum 13 + 32 = 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).


PROG

(Python) See Github link
(PARI) a(n)={if(n<2, n>=0, 2*(n\21)!^2*if(n%2, n1, 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
Adjacent sequences: A328375 A328376 A328377 * A328379 A328380 A328381


KEYWORD

nonn


AUTHOR

Tomás Roca Sánchez, Oct 14 2019


EXTENSIONS

Terms a(12) and beyond from Andrew Howroyd, Oct 16 2019


STATUS

approved



