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
Examples
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).
_______
|_| |___|
|_|_|_|_|
Links
- Index entries for linear recurrences with constant coefficients, signature (0,9,0,-7,0,1).
Crossrefs
Cf. A030186.
Programs
-
Mathematica
LinearRecurrence[{0, 9, 0, -7, 0, 1}, {1, 1, 5, 10, 39, 83}, 20]
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).
Comments