A060312 Number of distinct ways to tile a 2 X n rectangle with dominoes (solutions are identified if they are rotations or reflections of each other).

1, 1, 2, 4, 5, 9, 12, 21, 30, 51, 76, 127, 195, 322, 504, 826, 1309, 2135, 3410, 5545, 8900, 14445, 23256, 37701, 60813, 98514, 159094, 257608, 416325, 673933, 1089648, 1763581, 2852242, 4615823, 7466468, 12082291, 19546175, 31628466

Offset

1,3

Comments

Same as A001224 except that there a(2)=2 not 1. - N. J. A. Sloane, Mar 30 2015

Links

G. C. Greubel, Table of n, a(n) for n = 1..1001

A. R. Ashrafi, J. Azarija, K. Fathalikhani, S. Klavzar, et al., Orbits of Fibonacci and Lucas cubes, dihedral transformations, and asymmetric strings, 2014.

R. J. Mathar, Paving rectangular regions with rectangular tiles, ..., arXiv:1311.6135 [math.CO], Table 9.

W. E. Patten (proposer) and S. W. Golomb (solver), Problem E1470, "Covering a 2Xn rectangle with dominoes", Amer. Math. Monthly, 69 (1962), 61-62.

N. J. A. Sloane, Annotated scan of Monthly problem E1470 with illustration of a(4)=4 (Page 1)

N. J. A. Sloane, Annotated scan of Monthly problem E1470 with illustration of a(4)=4 (Page 2)

Index entries for sequences related to dominoes

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

Formula

If F(n) is the n-th Fibonacci number, then a(2n) = (F(2n) + F(n+1))/2 and a(2n+1) = (F(2n+1) + F(n))/2 for n > 1.

G.f.: -x*(x^7 + x^6 + x^5 + 2*x^4 - x^3 + x^2 - 1) / ((x^2 + x - 1)*(x^4 + x^2 - 1)). - Colin Barker, Dec 15 2012

Example

a(3)=2 because of the configurations |= and |||.

Maple

# Maple code for A060312 and A001224 from N. J. A. Sloane, Mar 30 2015
with(combinat); F:=fibonacci;
f:=proc(n) option remember;
if n=2 then 1 # change this to 2 to get A001224
elif (n mod 2) = 0 then (F(n+1)+F(n/2+2))/2;
else (F(n+1)+F((n+1)/2))/2; fi; end;
[seq(f(n), n=1..50)];

Mathematica

CoefficientList[Series[-(x^7 + x^6 + x^5 + 2 x^4 - x^3 + x^2 - 1) / ((x^2 + x - 1) (x^4 + x^2 - 1)), {x, 0, 40}], x] (* Vincenzo Librandi, Nov 22 2014 *)
LinearRecurrence[{1, 2, -1, 0, -1, -1}, {1, 1, 2, 4, 5, 9, 12, 21}, 40] (* Harvey P. Dale, Mar 13 2024 *)

Prog

(Magma) [n eq 1 select 1 else (1/2)*(Fibonacci(n+2)+Fibonacci(Floor((n-(-1)^n)/2)+2)): n in [0..40]]; // Vincenzo Librandi, Nov 22 2014

Crossrefs

Essentially the same as A001224, which is the main entry for this sequence. Other versions of the sequence can be found in A068928 and A102526.

Sequence in context: A241824 A144121 A240576 * A218934 A348176 A325716

Adjacent sequences: A060309 A060310 A060311 * A060313 A060314 A060315

Keyword

easy,nonn

Author

Thomas Ward, Mar 27 2001

Extensions

Edited by N. J. A. Sloane, Mar 30 2015

Status

approved