A355327 Number of ways to tile a 2 X n board with squares and dominoes where vertical dominoes are only allowed in even-numbered locations.

1, 1, 5, 10, 39, 83, 317, 678, 2585, 5531, 21085, 45116, 171987, 368005, 1402873, 3001764, 11443033, 24484957, 93339173, 199720270, 761354199, 1629089495, 6210256613, 13288248522, 50656169297, 108390330503

Offset

0,3

Comments

Similar in spirit to A030186, which counts all tilings of a 2 X n board without any restrictions on locations of vertical dominoes.

Links

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

Index entries for linear recurrences with constant coefficients, signature (0,9,0,-7,0,1).

Formula

a(2*n-1) = Sum_{k=1..2*n-1} k*a(2*n-1-k).

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

a(2*n) = 2*a(2*n-1) + 4*a(2n-2) - a(2*n-4).

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

a(n) = 9*a(n-2) - 7*a(n-4) + a(n-6).

Example

This is one of the a(4)=39 possible tilings of a 2 X 4 board. Note that vertical dominoes can only occur in the second or fourth location (we have one vertical domino in the second location in this picture).
    _______
   |_| |___|
   |_|_|_|_|

Mathematica

LinearRecurrence[{0, 9, 0, -7, 0, 1}, {1, 1, 5, 10, 39, 83}, 20]

Crossrefs

Cf. A030186.

Sequence in context: A365690 A277816 A359021 * A279764 A191580 A179306

Adjacent sequences: A355324 A355325 A355326 * A355328 A355329 A355330

Keyword

nonn,easy

Author

Greg Dresden and Zijie He, Jun 28 2022

Status

approved