cp's OEIS Frontend

A239288 Maximal sum of x0 + x0*x1 + ... + x0*x1*...*xk over all compositions x0 + ... + xk = n.

%I A239288 #24 Jun 13 2015 00:54:59
%S A239288 0,1,2,4,6,10,15,22,33,48,69,102,147,210,309,444,633,930,1335,1902,
%T A239288 2793,4008,5709,8382,12027,17130,25149,36084,51393,75450,108255,
%U A239288 154182,226353,324768,462549,679062,974307,1387650,2037189,2922924,4162953,6111570
%N A239288 Maximal sum of x0 + x0*x1 + ... + x0*x1*...*xk over all compositions x0 + ... + xk = n.
%C A239288 This sequence comes up in the analysis of exact algorithms for maximum independent sets.
%H A239288 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,3,-3).
%F A239288 a(0) = 0, a(n) = max{k + k*a(n - k) | 1 <= k <= n}.
%F A239288 For n >= 8 the solution becomes cyclic: a(3n + k) = 3 + 3a(3n - 3 + k).
%F A239288 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_
%e A239288 For n = 4 there are three solutions, all summing to 6: 3+3*1, 2+2*1+2*1*1, 2+2*2.
%e A239288 For n = 7 there is only one solution: 2 + 2*2 + 2*2*2 + 2*2*2*1.
%p A239288 mulprod := proc(L)
%p A239288     local i,k ;
%p A239288     add(mul(op(k,L),k=1..i),i=1..nops(L)) ;
%p A239288 end proc:
%p A239288 A239288 := proc(n)
%p A239288     a := 0 ;
%p A239288     for pa in combinat[partition](n) do
%p A239288         for pe in combinat[permute](pa) do
%p A239288             f := mulprod(pe) ;
%p A239288             a := max(a,f) ;
%p A239288         end do:
%p A239288     end do:
%p A239288     return a;
%p A239288 end proc: # _R. J. Mathar_, Jul 03 2014
%K A239288 nonn,easy
%O A239288 0,3
%A A239288 _Thomas Dybdahl Ahle_, Jun 13 2014