A228693 Largest number of maximal independent sets of nodes in any tree on n nodes.

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

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