|
|
A007382
|
|
Number of strict (-1)st-order 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, K-th order maximal independent sets in path and cycle graphs, J. Graph Theory, submitted, 1994.
|
|
LINKS
|
|
|
FORMULA
|
John W. Layman observes that if b(n) = 1+A007382(n) then b(n) = b(n-1) + 3b(n-2) - 2b(n-3) - 3b(n-4) + b(n-5) + b(n-6) for all 27 terms shown.
G.f.: x^3*(x^3+2x^2-x-3)/((1-x-x^2)*(1-x^2)^2).
|
|
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
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|