OFFSET
1,1
COMMENTS
Linear recurrence used to extrapolate to a(1), a(2), a(3).
LINKS
Colin Barker, Table of n, a(n) for n = 1..1000
Tomislav Doslic, I. Zubac, Counting maximal matchings in linear polymers, Ars Mathematica Contemporanea 11 (2016) 255-276. See Prop. 7.2.
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
Eric Weisstein's World of Mathematics, Wheel Graph
Index entries for linear recurrences with constant coefficients, signature (0,3,2,-3,-4,0,2,1).
FORMULA
a(n) = 3*a(n-2) + 2*a(n-3) - 3*a(n-4) - 4*a(n-5) + 2*a(n-7) + a(n-8).
G.f.: (x*(-2 - x + 2*x^2 + 4*x^3 - 2*x^4 - 4*x^5 + x^7))/((-1 + x^2)*(-1 + x^2 + x^3)^2).
a(n) = (n-1)*Padovan(n+3)+1-(-1)^n, where Padovan(k) = A000931(k). (Eee Doslic et al.) - N. J. A. Sloane, Apr 24 2017
MAPLE
A000931 := proc(n) option remember; if n = 0 then 1 elif n <= 2 then 0 else procname(n-2)+procname(n-3); fi; end;
psi:=n->A000931(n+6);
f:=n->n*psi(n-2)+1+(-1)^n;
[seq(f(n), n=0..40)]; # Produces the sequence with an offset of 0 - N. J. A. Sloane, Apr 24 2017
MATHEMATICA
LinearRecurrence[{0, 3, 2, -3, -4, 0, 2, 1}, {2, 1, 4, 3, 10, 10, 20, 28, 42, 63, 92}, 37] (* Eric W. Weisstein, Apr 01 2017 *)
Padovan[n_] := RootSum[-1 - # + #^3 &, 5 #^n - 6 #^(n + 1) + 4 #^(n + 2) &]/23; Table[(n - 1) Padovan[n + 3] - (-1)^n + 1, {n, 20}] (* Eric W. Weisstein, Dec 30 2017 *)
CoefficientList[Series[(-2 - x + 2 x^2 + 4 x^3 - 2 x^4 - 4 x^5 + x^7)/((-1 + x^2) (-1 + x^2 + x^3)^2), {x, 0, 20}], x] (* Eric W. Weisstein, Dec 30 2017 *)
PROG
(PARI) Vec(x*(2 + x - 2*x^2 - 4*x^3 + 2*x^4 + 4*x^5 - x^7) / ((1 - x)*(1 + x)*(1 - x^2 - x^3)^2) + O(x^50)) \\ Colin Barker, Apr 25 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Eric W. Weisstein, Apr 01 2017
STATUS
approved