login
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).
6

%I #33 Mar 13 2024 19:50:14

%S 1,1,2,4,5,9,12,21,30,51,76,127,195,322,504,826,1309,2135,3410,5545,

%T 8900,14445,23256,37701,60813,98514,159094,257608,416325,673933,

%U 1089648,1763581,2852242,4615823,7466468,12082291,19546175,31628466

%N 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).

%C Same as A001224 except that there a(2)=2 not 1. - _N. J. A. Sloane_, Mar 30 2015

%H G. C. Greubel, <a href="/A060312/b060312.txt">Table of n, a(n) for n = 1..1001</a>

%H A. R. Ashrafi, J. Azarija, K. Fathalikhani, S. Klavzar, et al., <a href="http://www.fmf.uni-lj.si/~klavzar/preprints/Fib-Luc-orbits-August-11-2014.pdf">Orbits of Fibonacci and Lucas cubes, dihedral transformations, and asymmetric strings</a>, 2014.

%H R. J. Mathar, <a href="http://arxiv.org/abs/1311.6135">Paving rectangular regions with rectangular tiles, ...</a>, arXiv:1311.6135 [math.CO], Table 9.

%H W. E. Patten (proposer) and S. W. Golomb (solver), <a href="http://www.jstor.org/stable/2312751">Problem E1470</a>, "Covering a 2Xn rectangle with dominoes", Amer. Math. Monthly, 69 (1962), 61-62.

%H N. J. A. Sloane, <a href="/A001224/a001224.png">Annotated scan of Monthly problem E1470 with illustration of a(4)=4 (Page 1)</a>

%H N. J. A. Sloane, <a href="/A001224/a001224_1.png">Annotated scan of Monthly problem E1470 with illustration of a(4)=4 (Page 2)</a>

%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-1,0,-1,-1).

%F 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.

%F 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

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

%p # Maple code for A060312 and A001224 from _N. J. A. Sloane_, Mar 30 2015

%p with(combinat); F:=fibonacci;

%p f:=proc(n) option remember;

%p if n=2 then 1 # change this to 2 to get A001224

%p elif (n mod 2) = 0 then (F(n+1)+F(n/2+2))/2;

%p else (F(n+1)+F((n+1)/2))/2; fi; end;

%p [seq(f(n),n=1..50)];

%t 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 *)

%t LinearRecurrence[{1,2,-1,0,-1,-1},{1,1,2,4,5,9,12,21},40] (* _Harvey P. Dale_, Mar 13 2024 *)

%o (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

%Y 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.

%K easy,nonn

%O 1,3

%A _Thomas Ward_, Mar 27 2001

%E Edited by _N. J. A. Sloane_, Mar 30 2015