The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60, we have over 367,000 sequences, and we’ve crossed 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A054854 Number of ways to tile a 4 X n region with 1 X 1 and 2 X 2 tiles. 16
 1, 1, 5, 11, 35, 93, 269, 747, 2115, 5933, 16717, 47003, 132291, 372157, 1047181, 2946251, 8289731, 23323853, 65624397, 184640891, 519507267, 1461688413, 4112616845, 11571284395, 32557042499, 91602704493, 257733967693, 725161963867 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 LINKS Alois P. Heinz, Table of n, a(n) for n = 0..1000 D. Abadie, J. Andreoli, S. Egan, T. Reddy, D. Xiong, Y. Zhao, and A. Zhu, On the Number of Tilings of a 4-By-N Rectangle with 1-By-1 and 2-By-2 Squares, Girls' Angle Bulletin, Vol. 15, No. 2 (2021), 8-12. S. Heubach, Tiling an m-by-n area with squares of size up to k-by-k (m<=5), Congressus Numerantium 140 (1999), 43-64. Richard M. Low and Ardak Kapbasov, Non-Attacking Bishop and King Positions on Regular and Cylindrical Chessboards, Journal of Integer Sequences, Vol. 20 (2017), Article 17.6.1, Table 7. R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO], 2016, Section 4.1. A. Ugolnikova, Pavages Aleatories, Phd Thesis (2016) Section 2.2.3 Index entries for linear recurrences with constant coefficients, signature (2,3,-2). FORMULA G.f.: (1-x)/(1-2*x-3*x^2+2*x^3). - N. J. A. Sloane, Nov 17 2002 a(n) = a(n-1)+4*a(n-2)+2*( a(n-3)+a(n-4)+...+a(0) ). 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 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 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 EXAMPLE 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. MAPLE 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 MATHEMATICA 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] (* Second program: *) LinearRecurrence[{2, 3, -2}, {1, 1, 5}, 30] (* Jean-François Alcover, Jul 28 2018 *) CROSSREFS Cf. A054855. Column k=4 of A245013. First differences of A046672. Sequence in context: A189918 A318415 A164560 * A188161 A323352 A005178 Adjacent sequences: A054851 A054852 A054853 * A054855 A054856 A054857 KEYWORD easy,nonn AUTHOR Silvia Heubach (silvi(AT)cine.net), Apr 21 2000 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 2 07:49 EST 2023. Contains 367510 sequences. (Running on oeis4.)