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

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

Author

Tomás Roca Sánchez, Oct 14 2019

Keywords

• nonn

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)

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..508
• Tomás Roca Sánchez, Github Python program along with explanations.

Crossrefs

Cf. A047838 is the maximum distance for every length n, except for n = 0 and n = 1.

Cf. A070910, A096789.

Programs

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 *)

PARI

a(n)={if(n<2, n>=0, 2*(n\2-1)!^2*if(n%2, n-1, 1))} \\ Andrew Howroyd, Oct 16 2019

Python

# See Github link

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

Extensions

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