The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A228693 Largest number of maximal independent sets of nodes in any tree on n nodes. 3
 1, 1, 2, 2, 3, 4, 5, 8, 9, 16, 17, 32, 33, 64, 65, 128, 129, 256, 257, 512, 513, 1024, 1025, 2048, 2049, 4096, 4097, 8192, 8193, 16384, 16385, 32768, 32769, 65536, 65537, 131072, 131073, 262144, 262145, 524288, 524289, 1048576, 1048577, 2097152, 2097153, 4194304, 4194305, 8388608, 8388609, 16777216, 16777217 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 LINKS Vincenzo Librandi, Table of n, a(n) for n = 0..1000 Herbert S. Wilf, The number of maximal independent sets in a tree, SIAM Journal on Algebraic and Discrete Methods, volume 7, number 1, January 1986, pages 125-130.  Also author's copy. Index entries for linear recurrences with constant coefficients, signature (0,3,0,-2). FORMULA From Colin Barker, Sep 08 2013: (Start) G.f.: -(x^4+x^3+x^2-x-1) / ((x-1)*(x+1)*(2*x^2-1)). a(n) = 3*a(n-2)-2*a(n-4) for n > 4. (End) MAPLE f:=proc(n) if n=0 then 1 elif (n mod 2) = 0 then 2^((n/2)-1)+1 else 2^((n-1)/2); fi; end; MATHEMATICA CoefficientList[Series[-(x^4 + x^3 + x^2 - x - 1) / ((x - 1) (x + 1) (2 x^2 - 1)), {x, 0, 60}], x] (* Vincenzo Librandi, Sep 09 2013 *) PROG (PARI) Vec(-(x^4+x^3+x^2-x-1)/((x-1)*(x+1)*(2*x^2-1)) + O(x^100)) \\ Colin Barker, Sep 08 2013 (Magma) I:=[1, 1, 2, 2, 3]; [n le 5 select I[n] else 3*Self(n-2)-2*Self(n-4): n in [1..55]]; // Vincenzo Librandi, Sep 09 2013 CROSSREFS Cf. A000051, A000079 (bisections). Sequence in context: A211228 A338463 A186505 * A116676 A240575 A176538 Adjacent sequences: A228690 A228691 A228692 * A228694 A228695 A228696 KEYWORD nonn,easy AUTHOR N. J. A. Sloane, Sep 02 2013 STATUS approved

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

Last modified November 30 23:40 EST 2023. Contains 367464 sequences. (Running on oeis4.)