A320947 a(n) is the number of dominoes, among all domino tilings of the 2 X n rectangle, sharing a length-2 side with the boundary of the rectangle.

1, 4, 8, 16, 30, 56, 102, 184, 328, 580, 1018, 1776, 3082, 5324, 9160, 15704, 26838, 45736, 77742, 131840, 223112, 376844, 635378, 1069536, 1797650, 3017236, 5057672, 8467744, 14161038, 23657240, 39482358, 65832136, 109671112, 182552404, 303629290

Offset

1,2

Comments

a(n) is also the number of dominoes, among all domino tilings of the 2 x n rectangle, sharing a contiguous path of length at least 2 with the boundary of the rectangle.

Links

Colin Barker, Table of n, a(n) for n = 1..1000

B. E. Tenner, Tiling-based models of perimeter and area, arXiv:1811.00082 [math.CO], 2018.

Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Formula

a(n) = a(n-1) + a(n-2) + 2*Fibonacci(n-1) for n > 3.

From Colin Barker, Nov 02 2018: (Start)

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

a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4) for n>5.

a(n) = 2^(1-n)*(-4*sqrt(5)*((1-sqrt(5))^n - (1+sqrt(5))^n) + 5*((1-sqrt(5))^n + (1+sqrt(5))^n)*n) / 25 for n>1.

(End)

Example

a(4) = 16 because among the five domino tilings of the 2 X 4 rectangle, 16 dominoes share a length 2 side with the boundary.

Mathematica

Rest@ CoefficientList[Series[x (1 + 2 x - x^2 - 2 x^3 - x^4)/(1 - x - x^2)^2, {x, 0, 35}], x] (* Michael De Vlieger, Nov 05 2018 *)

Prog

(PARI) Vec(x*(1 + 2*x - x^2 - 2*x^3 - x^4) / (1 - x - x^2)^2 + O(x^40)) \\ Colin Barker, Nov 02 2018

Crossrefs

Cf. A000045.

Sequence in context: A215348 A301144 A298803 * A329778 A355391 A053163

Adjacent sequences: A320944 A320945 A320946 * A320948 A320949 A320950

Keyword

nonn,easy

Author

Bridget Tenner, Oct 24 2018

Status

approved