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

Author

Alois P. Heinz, Nov 13 2011

Keywords

• nonn
• easy

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.

Examples

			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.
		

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

Crossrefs

Cf. A000217, A004396, A200068.

Programs

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

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.

27*a(n) = (2*n-1)*(n^2-n-1) - A132677(n) - 3*(-1)^n*A099254(n-1). - R. J. Mathar, Mar 14 2025