OFFSET
0,2
COMMENTS
For n >= 3, also the number of maximum independent vertex sets in the n-prism graph. - Eric W. Weisstein, Mar 30 2017
For n >= 3, also the number of maximum independent edge sets in the n-web graph. - Eric W. Weisstein, Dec 31 2017
For n >= 10, also the number of minimum dominating sets in the n-gear graph. - Eric W. Weisstein, Sep 09 2021
LINKS
Robert Price, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
Eric Weisstein's World of Mathematics, Gear Graph
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set
Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimum Dominating Set
Eric Weisstein's World of Mathematics, Prism Graph
Eric Weisstein's World of Mathematics, Web Graph
Stephen Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.
Index entries for linear recurrences with constant coefficients, signature (0,2,0,-1).
FORMULA
From Colin Barker, Jan 05 2016 and Apr 17 2019: (Start)
a(n) = 1+(-1)^n+n-(-1)^n*n for n>0.
a(n) = 2*a(n-2)-a(n-4) for n>4.
G.f.: (1+2*x-x^2)*(1+x^2) / ((1-x)^2*(1+x)^2). (End)
MATHEMATICA
rule=59; rows=20; ca=CellularAutomaton[rule, {{1}, 0}, rows-1, {All, All}]; (* Start with single black cell *) catri=Table[Take[ca[[k]], {rows-k+1, rows+k-1}], {k, 1, rows}]; (* Truncated list of each row *) Table[Total[catri[[k]]], {k, 1, rows}] (* Number of Black cells in stage n *)
Join[{1}, Table[Piecewise[{{2, Mod[n, 2] == 0}, {2 n, Mod[n, 2] == 1}}], {n, 20}]] (* Eric W. Weisstein, Sep 09 2021 *)
Join[{1}, LinearRecurrence[{0, 2, 0, -1}, {2, 2, 6, 2}, 20]] (* Eric W. Weisstein, Sep 09 2021 *)
CoefficientList[Series[(1 + 2 x + 2 x^3 - x^4)/(-1 + x^2)^2, {x, 0, 20}], x] (* Eric W. Weisstein, Sep 09 2021 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Robert Price, Jan 03 2016
STATUS
approved