A162485 a(1)=4, a(2)=6; for n > 2, a(n) = 2*a(n-1) + a(n-2) - 4*((n-1) mod 2).

4, 6, 16, 34, 84, 198, 480, 1154, 2788, 6726, 16240, 39202, 94644, 228486, 551616, 1331714, 3215044, 7761798, 18738640, 45239074, 109216788, 263672646, 636562080, 1536796802, 3710155684

Offset

1,1

Comments

a(n) is the number of perfect matchings of an edge-labeled 2 X n Klein bottle grid graph, or equivalently the number of domino tilings of a 2 X n Klein bottle grid. (The twist is on the length-2 side.)

Links

Table of n, a(n) for n=1..25.

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 > 1, a(n) = (1/2)*((1 + sqrt(2))^n*(2 + (-1 + sqrt(2))^(2*floor((1/2)*(-1 + n)))*(-4 + 3*sqrt(2))) + (1 - sqrt(2))^n*(2 - (-1 - sqrt(2))^(2*floor((1/2)*(-1 + n)))*(4 + 3*sqrt(2)))).

From Colin Barker, May 01 2012: (Start)

a(n) = 1 - (-1)^n + (1-sqrt(2))^n + (1+sqrt(2))^n.

G.f.: 2*x*(2-x-2*x^2-x^3)/(1-x)/(1+x)/(1-2*x-x^2). (End)

a(n) = A002203(n) + 1 - (-1)^n. - R. J. Mathar, Oct 08 2016

Example

a(3) = 2*a(2) + a(1) - 4*(2 mod 2) = 2*6 + 4 - 0 = 16.

Crossrefs

Sequence in context: A183370 A113883 A036748 * A188466 A076066 A227178

Adjacent sequences: A162482 A162483 A162484 * A162486 A162487 A162488

Keyword

easy,nonn

Author

Sarah-Marie Belcastro, Jul 04 2009

Status

approved