OFFSET
0,3
COMMENTS
This sequence comes up in the analysis of exact algorithms for maximum independent sets.
LINKS
Index entries for linear recurrences with constant coefficients, signature (1,0,3,-3).
FORMULA
a(0) = 0, a(n) = max{k + k*a(n - k) | 1 <= k <= n}.
For n >= 8 the solution becomes cyclic: a(3n + k) = 3 + 3a(3n - 3 + k).
G.f.: -x*(x^2+x+1)*(x^5-2*x^4+2*x^3-x^2-1) / ((x-1)*(3*x^3-1)). - Joerg Arndt
EXAMPLE
For n = 4 there are three solutions, all summing to 6: 3+3*1, 2+2*1+2*1*1, 2+2*2.
For n = 7 there is only one solution: 2 + 2*2 + 2*2*2 + 2*2*2*1.
MAPLE
mulprod := proc(L)
local i, k ;
add(mul(op(k, L), k=1..i), i=1..nops(L)) ;
end proc:
A239288 := proc(n)
a := 0 ;
for pa in combinat[partition](n) do
for pe in combinat[permute](pa) do
f := mulprod(pe) ;
a := max(a, f) ;
end do:
end do:
return a;
end proc: # R. J. Mathar, Jul 03 2014
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Thomas Dybdahl Ahle, Jun 13 2014
STATUS
approved