login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A239288 Maximal sum of x0 + x0*x1 + ... + x0*x1*...*xk over all compositions x0 + ... + xk = n. 1
0, 1, 2, 4, 6, 10, 15, 22, 33, 48, 69, 102, 147, 210, 309, 444, 633, 930, 1335, 1902, 2793, 4008, 5709, 8382, 12027, 17130, 25149, 36084, 51393, 75450, 108255, 154182, 226353, 324768, 462549, 679062, 974307, 1387650, 2037189, 2922924, 4162953, 6111570 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

This sequence comes up in the analysis of exact algorithms for maximum independent sets.

LINKS

Table of n, a(n) for n=0..41.

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

Sequence in context: A086182 A035294 A073818 * A306145 A143184 A309173

Adjacent sequences:  A239285 A239286 A239287 * A239289 A239290 A239291

KEYWORD

nonn,easy

AUTHOR

Thomas Dybdahl Ahle, Jun 13 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 6 08:44 EDT 2020. Contains 333268 sequences. (Running on oeis4.)