login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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
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.
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).
a(n) = Sum_{i=1..floor((n-1)/2)} C(n-i+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: A248825 A001641 A374712 * A127804 A027306 A239024
KEYWORD
nonn,easy
STATUS
approved