login
Maximum sum of all products of absolute differences and distances between element pairs among the integer partitions of n.
3

%I #34 Mar 08 2020 23:23:02

%S 0,0,0,1,3,6,12,20,30,45,63,84,112,144,180,225,275,330,396,468,546,

%T 637,735,840,960,1088,1224,1377,1539,1710,1900,2100,2310,2541,2783,

%U 3036,3312,3600,3900,4225,4563,4914,5292,5684,6090,6525,6975,7440,7936,8448

%N Maximum sum of all products of absolute differences and distances between element pairs among the integer partitions of n.

%C Also the maximum sum of weighted inversions among the compositions of n where weights are products of absolute differences and distances between the element pairs which are not in sorted order.

%C a(n) is divisible by at least one triangular number >1 for n>=4. Thus 3 is the only prime in this sequence.

%H Alois P. Heinz, <a href="/A200067/b200067.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,2,-4,2,-1,2,-1).

%F G.f.: x^3*(1+x)*(1+x^2)/((1+x+x^2)^2*(x-1)^4).

%F a(n) = max_{k=0..n} (n-k-1)*k*(k+1)/2.

%F a(n) = (n-k-1)*k*(k+1)/2 with k = max(0, floor((2*n-1)/3)), or k = A004396(n-1) for n>0.

%e a(2) = 0: [1,1]-> 0, [2]-> 0; the maximum is 0.

%e a(3) = 1: [1,1,1]-> 0, [2,1]-> 1, [3]-> 0; the maximum is 1.

%e a(4) = 3: [1,1,1,1]-> 0, [2,1,1]-> 1+2 = 3, [2,2]->0, [3,1]->2, [4]->0.

%e a(5) = 6: [2,1,1,1]-> 1+2+3 = 6, [3,1,1]-> 2 + 2*2 = 2*(1+2) = 6.

%e a(6) = 12: [3,1,1,1]-> 2 + 2*2 + 2*3 = 2*(1+2+3) = 12.

%e a(7) = 20: [3,1,1,1,1]-> 2 + 2*2 + 2*3 + 2*4 = 2*(1+2+3+4) = 20.

%e a(8) = 30: [3,1,1,1,1,1]-> 2*(1+2+3+4+5) = 30, [4,1,1,1,1]-> 3*(1+2+3+4) = 30.

%p a:= n-> (k-> (n-k-1)*k*(k+1)/2)(max(0, floor((2*n-1)/3))):

%p seq(a(n), n=0..50);

%t a[n_] := Max[Table[(n-k-1)*k*(k+1)/2, {k, 0, n}]]; Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Nov 22 2013, after _Alois P. Heinz_ *)

%Y Cf. A000217, A004396, A200068.

%K nonn,easy

%O 0,5

%A _Alois P. Heinz_, Nov 13 2011