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

 

Logo


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

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*(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.

License Agreements, Terms of Use, Privacy Policy. .

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