A329707 Number of placements of zero or more dominoes on a 2 X n grid where no two empty squares are horizontally adjacent.

1, 2, 4, 11, 25, 61, 146, 351, 844, 2028, 4875, 11717, 28163, 67692, 162703, 391070, 939968, 2259289, 5430383, 13052363, 31372406, 75406105, 181244648, 435636112, 1047086489, 2516756727, 6049227537, 14539805696, 34947594281, 83999358146, 201899224084, 485281049587, 1166412095721

Offset: 0

Author

Andrew Howroyd, Feb 28 2020

Keywords

• nonn

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (2,1,0,0,0,-1).

Crossrefs

Row 2 of A332862.

Programs

Mathematica

LinearRecurrence[{2, 1, 0, 0, 0, -1}, {1, 2, 4, 11, 25, 61}, 50] (* Paolo Xausa, Jun 19 2024 *)

PARI

Vec((1 - x)*(1 + x + x^3)/(1 - 2*x - x^2 + x^6) + O(x^30))

Formula

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

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