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
Examples
a(3)=2 because of the configurations |= and |||.
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).
Crossrefs
Programs
-
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
-
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 *)
Formula
If F(n) is the n-th Fibonacci number, then a(2n) = (F(2n+1) + F(n+2))/2 for n > 1 and a(2n-1) = (F(2n) + F(n))/2. [Corrected by Manfred Boergens, Aug 25 2025]
a(n) = (F(n+1)+F(floor((n+3+(-1)^n)/2)))/2 for n!=2. - Manfred Boergens, Aug 25 2025
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
Extensions
Edited by N. J. A. Sloane, Mar 30 2015
Comments