%I M2365 #24 Nov 17 2017 00:58:45
%S 0,0,3,4,11,16,32,49,87,137,231,369,608,978,1595,2574,4179,6754,10944,
%T 17699,28655,46355,75023,121379,196416,317796,514227,832024,1346267
%N Number of strict (-1)st-order maximal independent sets in path graph.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. Yanco and A. Bagchi, K-th order maximal independent sets in path and cycle graphs, J. Graph Theory, submitted, 1994.
%H R. Yanco, <a href="/A007380/a007380.pdf">Letter and Email to N. J. A. Sloane, 1994</a>
%F _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.
%F G.f.: x^3*(x^3+2x^2-x-3)/((1-x-x^2)*(1-x^2)^2).
%F a(n) = Sum_{i=1..floor((n-1)/2)} C(n-i+1, i). - _Wesley Ivan Hurt_, Sep 19 2017
%t Table[Sum[Binomial[n - i + 1, i], {i, Floor[(n - 1)/2]}], {n, 30}] (* or *)
%t 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 *)
%Y Equals A054451(n+1) - 1.
%K nonn,easy
%O 1,3
%A _N. J. A. Sloane_, _Mira Bernstein_