The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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_{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) LINKS Tomás Roca Sánchez, Github Python program along with explanations 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 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). 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 7 00:22 EDT 2021. Contains 343609 sequences. (Running on oeis4.)