|
%I #56 Mar 05 2022 00:21:00
%S 1,1,5,11,35,93,269,747,2115,5933,16717,47003,132291,372157,1047181,
%T 2946251,8289731,23323853,65624397,184640891,519507267,1461688413,
%U 4112616845,11571284395,32557042499,91602704493,257733967693,725161963867
%N Number of ways to tile a 4 X n region with 1 X 1 and 2 X 2 tiles.
%H Alois P. Heinz, <a href="/A054854/b054854.txt">Table of n, a(n) for n = 0..1000</a>
%H D. Abadie, J. Andreoli, S. Egan, T. Reddy, D. Xiong, Y. Zhao, and A. Zhu, <a href="http://girlsangle.org/page/bulletin-archive/GABv15n02E.pdf">On the Number of Tilings of a 4-By-N Rectangle with 1-By-1 and 2-By-2 Squares</a>, Girls' Angle Bulletin, Vol. 15, No. 2 (2021), 8-12.
%H S. Heubach, <a href="https://www.calstatela.edu/sites/default/files/users/u1231/Papers/cgtc30.pdf">Tiling an m-by-n area with squares of size up to k-by-k (m<=5)</a>, Congressus Numerantium 140 (1999), 43-64.
%H Richard M. Low and Ardak Kapbasov, <a href="https://www.emis.de/journals/JIS/VOL20/Low/low2.html">Non-Attacking Bishop and King Positions on Regular and Cylindrical Chessboards</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.6.1, Table 7.
%H R. J. Mathar, <a href="http://arxiv.org/abs/1609.03964">Tiling n x m rectangles with 1 x 1 and s x s squares</a>, arXiv:1609.03964 [math.CO], 2016, Section 4.1.
%H A. Ugolnikova, <a href="https://tel.archives-ouvertes.fr/tel-01889871/">Pavages Aleatories</a>, Phd Thesis (2016) Section 2.2.3
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,3,-2).
%F G.f.: (1-x)/(1-2*x-3*x^2+2*x^3). - _N. J. A. Sloane_, Nov 17 2002
%F a(n) = a(n-1)+4*a(n-2)+2*( a(n-3)+a(n-4)+...+a(0) ).
%F a(n) = 2*a(n-1)+3*a(n-2)-2*a(n-3). [See proofs in Mathar (a transfer matrix approach) and in Abadie et al.(direct proof).] - Keith Schneider (kschneid(AT)bulldog.unca.edu), Apr 02 2006
%F a(n) = Term (2,2) of matrix [5,1,1; 1,1,0; 1,0,1/2]*[2,1,0; 3,0,1; -2,0,0]^n. - _Alois P. Heinz_, May 18 2008
%F a(n) = F(n+1)^2 + Sum_{k=1..n-1} F(k)^2 * a(n-k-1), for n >= 0, where F(k) = A000045(k) (Fibonacci numbers), see Abadie, et al. - _Richard S. Chang_, Jan 21 2022
%e a(2) = 5 as there is one tiling of a 4x2 region with only 1 X 1 tiles, 3 tilings with exactly one 2 X 2 tile and one tiling consisting of two 2 X 2 tiles.
%p A:= Matrix([[5,1,1],[1,1,0],[1,0,1/2]]); M:= Matrix([[2,1,0],[3,0,1],[ -2,0,0]]): a:= n->(A.M^n)[2,2]: seq(a(n), n=0..50); # _Alois P. Heinz_, May 18 2008
%t f[{A_, B_}] := Module[{til = A, basic = B}, {Flatten[Append[til, ListConvolve[A, B]]], AppendTo[basic, 2]}]; NumOfTilings[n_] := Nest[f, {{1, 1}, {1, 4}}, n - 2][[1]] NumOfTilings[30]
%t (* Second program: *)
%t LinearRecurrence[{2, 3, -2}, {1, 1, 5}, 30] (* _Jean-François Alcover_, Jul 28 2018 *)
%Y Cf. A054855.
%Y Column k=4 of A245013. First differences of A046672.
%K easy,nonn
%O 0,3
%A Silvia Heubach (silvi(AT)cine.net), Apr 21 2000
|
