OFFSET
1,1
COMMENTS
a(n) is the number of perfect matchings of an edge-labeled 2 X n toroidal grid graph, or equivalently the number of domino tilings of a 2 X n toroidal grid.
LINKS
Colin Barker, Table of n, a(n) for n = 1..1000
Sarah-Marie Belcastro, Domino Tilings of 2 X n Grids (or Perfect Matchings of Grid Graphs) on Surfaces, J. Integer Seq. 26 (2023), Article 23.5.6.
Index entries for linear recurrences with constant coefficients, signature (2,2,-2,-1).
FORMULA
for n > 2, (1/2) ((1 + sqrt(2))^n (2 - (-2 + sqrt(2)) (-1 + sqrt(2))^(2 floor(n/2))) + (1 - sqrt(2))^n (2 + (1 + sqrt(2))^(2 floor(n/2)) (2 + sqrt(2)))) (from Mathematica's solution to the recurrence).
Pell(n) + Pell(n-2) + 2*((n-1) mod 2).
From R. J. Mathar, Jul 26 2009: (Start)
a(n)= 2*a(n-1) + 2*a(n-2) - 2*a(n-3) - a(n-4) = 2*A100828(n-1).
G.f.: -2*x*(-1-2*x+3*x^2+2*x^3)/((x-1)*(1+x)*(x^2+2*x-1)).
(End)
a(n) = 1 + (-1)^n + (1-sqrt(2))^n + (1+sqrt(2))^n. - Colin Barker, Dec 16 2017
EXAMPLE
a(3) = 2 a(2) + a(1) - 4*(3 mod 2) = 2*8 + 2 - 4 = 14.
MATHEMATICA
Fold[Append[#1, 2 #1[[#2 - 1]] + #1[[#2 - 2]] - 4 Mod[#2, 2]] &, {2, 8}, Range[3, 30]] (* or *)
Rest@ CoefficientList[Series[-2 x (-1 - 2 x + 3 x^2 + 2 x^3)/((x - 1) (1 + x) (x^2 + 2 x - 1)), {x, 0, 30}], x] (* Michael De Vlieger, Dec 16 2017 *)
LinearRecurrence[{2, 2, -2, -1}, {2, 8, 14, 36}, 30] (* Harvey P. Dale, Aug 24 2018 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Sarah-Marie Belcastro, Jul 04 2009
STATUS
approved