A328378 - OEIS

%I #70 Oct 03 2023 13:14:21

%S 1,1,2,4,2,8,8,48,72,576,1152,11520,28800,345600,1036800,14515200,

%T 50803200,812851200,3251404800,58525286400,263363788800,5267275776000,

%U 26336378880000,579400335360000,3186701844480000,76480844267520000,458885065605120000,11931011705733120000

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

%C From _Andrew Howroyd_, Oct 16 2019: (Start)

%C 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.

%C 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.

%C The above considerations lead to a formula for this sequence with the maximum sum being given by A047838(n). (End)

%H Alois P. Heinz, <a href="/A328378/b328378.txt">Table of n, a(n) for n = 0..508</a>

%H Tomás Roca Sánchez, <a href="https://github.com/greenlucid/oeis/blob/master/b01.py">Github Python program along with explanations</a>.

%F 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

%F 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

%F 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

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

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

%o (Python) # See Github link

%o (PARI) a(n)={if(n<2, n>=0, 2*(n\2-1)!^2*if(n%2, n-1, 1))} \\ _Andrew Howroyd_, Oct 16 2019

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

%Y Cf. A070910, A096789.

%K nonn

%O 0,3

%A _Tomás Roca Sánchez_, Oct 14 2019

%E Terms a(12) and beyond from _Andrew Howroyd_, Oct 16 2019