A162484 a(1) = 2, a(2) = 8; a(n) = 2 a(n - 1) + a(n - 2) - 4*(n mod 2).

2, 8, 14, 36, 82, 200, 478, 1156, 2786, 6728, 16238, 39204, 94642, 228488, 551614, 1331716, 3215042, 7761800, 18738638, 45239076, 109216786, 263672648, 636562078, 1536796804, 3710155682, 8957108168, 21624372014, 52205852196, 126036076402, 304278005000

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

Cf. A000129.

Sequence in context: A086177 A299337 A332611 * A333575 A259119 A039660

Adjacent sequences: A162481 A162482 A162483 * A162485 A162486 A162487

Keyword

easy,nonn

Author

Sarah-Marie Belcastro, Jul 04 2009

Status

approved