login
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
OFFSET
0,3
LINKS
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.
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
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Sep 02 2013
STATUS
approved