OFFSET
0,1
COMMENTS
An edge covering for a graph is a set of edges so that every vertex is adjacent to at least one edge of this set.
The number of edge coverings for the circle C_n for n>0 is the n-th Lucas number.
LINKS
R. Tauraso, Edge cover time for regular graphs, JIS 11 (2008) 08.4.4
Eric Weisstein's World of Mathematics, Edge Cover
Eric Weisstein's World of Mathematics, Prism Graph
Index entries for linear recurrences with constant coefficients, signature (5,9,1,-2).
FORMULA
a(n) = 5*a(n-1) +9*a(n-2) +a(n-3) -2*a(n-4).
G.f.: (4-15*x-18*x^2-x^3) / ((1+x)*(1-6*x-3*x^2+2*x^3)).
MATHEMATICA
a[0] = 4; a[1] = 5; a[2] = 43; a[3] = 263; a[n_] := a[n] = 5a[n - 1] + 9a[n - 2] + a[n - 3] - 2a[n - 4]; Table[a[n], {n, 0, 19}] (* Robert G. Wilson v, Sep 26 2006 *)
CoefficientList[ Series[(4 - 15x - 18x^2 - x^3)/((1 + x)*(1 - 6x - 3x^2 + 2x^3)), {x, 0, 19}], x] (* Robert G. Wilson v, Sep 26 2006 *)
Table[(-1)^n + RootSum[2 - 3 # - 6 #^2 + #^3 &, #^n &], {n, 0, 20}] (* Eric W. Weisstein, Mar 29 2017 *)
LinearRecurrence[{5, 9, 1, -2}, {5, 43, 263, 1699}, {0, 20}] (* Eric W. Weisstein, Aug 09 2017 *)
PROG
(PARI) x='x+O('x^99); Vec((4-15*x-18*x^2-x^3)/((1+x)*(1-6*x-3*x^2+2*x^3))) \\ Altug Alkan, Aug 10 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Roberto Tauraso, Sep 24 2006
STATUS
approved