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
KEYWORD
nonn,easy
AUTHOR
Alois P. Heinz, Nov 13 2011
STATUS
approved