OFFSET
0,2
COMMENTS
a(n) = element(1,3) in A^(n+1), where A is the 5 X 5 matrix:
[1, 1, 1, 1, 1]
[1, 1, 0, 1, 1]
[1, 0, 0, 0, 1]
[1, 1, 0, 1, 1]
[1, 1, 1, 1, 1]. - Lechoslaw Ratajczak, May 03 2017
Also the number of matchings in the 2 X n king graph for n >= 1. - Eric W. Weisstein, Oct 03 2017
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1050
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Index entries for linear recurrences with constant coefficients, signature (4,2,-4).
FORMULA
G.f.: (1-2*x)/(1-4*x-2*x^2+4*x^3).
Recurrence: {a(0)=1, a(1)=2, a(2)=10, 4*a(n)-2*a(n+1)-4*a(n+2)+a(n+3)=0.}
a(n) = Sum(-1/158*(-11-42*r+24*r^2)*r^(-1-n) where r=RootOf(1-4*_Z-2*_Z^2+4*_Z^3))
MAPLE
spec := [S, {S=Sequence(Prod(Union(Sequence(Union(Z, Z)), Z), Union(Z, Z)))}, unlabeled ]: seq(combstruct[count ](spec, size=n), n=0..20);
MATHEMATICA
LinearRecurrence[{4, 2, -4}, {1, 2, 10}, 40] (* Vincenzo Librandi, Jun 23 2012 *)
Table[RootSum[4 - 2 # - 4 #^2 + #^3 &, 30 #^n - 13 #^(n + 1) + 6 #^(n + 2) &]/158, {n, 0, 20}] (* Eric W. Weisstein, Oct 03 2017 *)
Table[RootSum[1 - 4 # - 2 #^2 + 4 #^3 &, (11 + 42 # - 24 #^2)/#^(n + 1) &]/158, {n, 0, 20}] (* Eric W. Weisstein, Oct 03 2017 *)
CoefficientList[Series[(1 - 2 x)/(1 - 4 x - 2 x^2 + 4 x^3), {x, 0, 20}], x] (* Eric W. Weisstein, Oct 03 2017 *)
PROG
(Magma) I:=[1, 2, 10]; [n le 3 select I[n] else 4*Self(n-1)+2*Self(n-2)-4*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jun 23 2012
(PARI) Vec((1-2*x)/(1-4*x-2*x^2+4*x^3) + O(x^30)) \\ Michel Marcus, May 06 2017
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
STATUS
approved