

A007382


Number of strict (1)storder maximal independent sets in path graph.
(Formerly M2365)


2



0, 0, 3, 4, 11, 16, 32, 49, 87, 137, 231, 369, 608, 978, 1595, 2574, 4179, 6754, 10944, 17699, 28655, 46355, 75023, 121379, 196416, 317796, 514227, 832024, 1346267
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. Yanco and A. Bagchi, Kth order maximal independent sets in path and cycle graphs, J. Graph Theory, submitted, 1994.


LINKS

Table of n, a(n) for n=1..29.
R. Yanco, Letter and Email to N. J. A. Sloane, 1994


FORMULA

John W. Layman observes that if b(n) = 1+A007382(n) then b(n) = b(n1) + 3b(n2)  2b(n3)  3b(n4) + b(n5) + b(n6) for all 27 terms shown.
G.f.: x^3*(x^3+2x^2x3)/((1xx^2)*(1x^2)^2).
a(n) = Sum_{i=1..floor((n1)/2)} C(ni+1, i).  Wesley Ivan Hurt, Sep 19 2017


MATHEMATICA

Table[Sum[Binomial[n  i + 1, i], {i, Floor[(n  1)/2]}], {n, 30}] (* or *)
Rest@ Abs@ CoefficientList[Series[x^3*(x^3 + 2 x^2  x  3)/((1  x  x^2) (1  x^2)^2), {x, 0, 30}], x] (* Michael De Vlieger, Sep 19 2017 *)


CROSSREFS

Equals A054451(n+1)  1.
Sequence in context: A266384 A248825 A001641 * A127804 A027306 A239024
Adjacent sequences: A007379 A007380 A007381 * A007383 A007384 A007385


KEYWORD

nonn,easy


AUTHOR

N. J. A. Sloane, Mira Bernstein


STATUS

approved



