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

0, 0, 0, 1, 3, 6, 12, 20, 30, 45, 63, 84, 112, 144, 180, 225, 275, 330, 396, 468, 546, 637, 735, 840, 960, 1088, 1224, 1377, 1539, 1710, 1900, 2100, 2310, 2541, 2783, 3036, 3312, 3600, 3900, 4225, 4563, 4914, 5292, 5684, 6090, 6525, 6975, 7440, 7936, 8448

Offset

0,5

Comments

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.

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (2,-1,2,-4,2,-1,2,-1).

Formula

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

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

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.

Example

a(2) =  0: [1,1]-> 0, [2]-> 0; the maximum is 0.
a(3) =  1: [1,1,1]-> 0, [2,1]-> 1, [3]-> 0; the maximum is 1.
a(4) =  3: [1,1,1,1]-> 0, [2,1,1]-> 1+2 = 3, [2,2]->0, [3,1]->2, [4]->0.
a(5) =  6: [2,1,1,1]-> 1+2+3 = 6, [3,1,1]-> 2 + 2*2 = 2*(1+2) = 6.
a(6) = 12: [3,1,1,1]-> 2 + 2*2 + 2*3 = 2*(1+2+3) = 12.
a(7) = 20: [3,1,1,1,1]-> 2 + 2*2 + 2*3 + 2*4 = 2*(1+2+3+4) = 20.
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.

Maple

a:= n-> (k-> (n-k-1)*k*(k+1)/2)(max(0, floor((2*n-1)/3))):
seq(a(n), n=0..50);

Mathematica

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

Crossrefs

Cf. A000217, A004396, A200068.

Sequence in context: A320608 A246147 A066140 * A061061 A361272 A001975

Adjacent sequences: A200064 A200065 A200066 * A200068 A200069 A200070

Keyword

nonn,easy

Author

Alois P. Heinz, Nov 13 2011

Status

approved