|
%I M2572 N1017 #129 May 03 2024 16:39:20
%S 1,1,3,6,13,28,60,129,277,595,1278,2745,5896,12664,27201,58425,125491,
%T 269542,578949,1243524,2670964,5736961,12322413,26467299,56849086,
%U 122106097,262271568,563332848,1209982081,2598919345,5582216355,11990037126,25753389181
%N Bisection of A000930.
%C Number of ways to tile a 3 X n region with 1 X 1, 2 X 2 and 3 X 3 tiles.
%C Number of ternary words with subwords (0,0), (0,1) and (1,1) not allowed. - _Olivier Gérard_, Aug 28 2012
%C Diagonal sums of A063967. - _Paul Barry_, Nov 09 2005
%C Row sums of number triangle A116088. - _Paul Barry_, Feb 04 2006
%C Sequence is identical to its second differences negated, minus the first 3 terms. - _Paul Curtz_, Feb 10 2008
%C a(n) = term (3,3) in the 3 X 3 matrix [0,1,0; 0,0,1; 1,2,1]^n. - _Gary W. Adamson_, May 30 2008
%C a(n)/a(n-1) tends to 2.147899035..., an eigenvalue of the matrix and a root to x^3 - x^2 - 2x - 1 = 0. - _Gary W. Adamson_, May 30 2008
%C INVERT transform of (1, 2, 1, 0, 0, 0, ...) = (1, 3, 6, 13, 28, ...); such that (1, 2, 1, 0, 0, 0, ...) convolved with (1, 1, 3, 6, 13, 28, 0, 0, 0, ...) shifts to the left. - _Gary W. Adamson_, Apr 18 2010
%C a(n) is the top left entry in the n-th power of the 3 X 3 matrix [1, 1, 1; 1, 0, 1; 1, 0, 0] or of the 3 X 3 matrix [1, 1, 1; 1, 0, 0; 1, 1, 0]. - _R. J. Mathar_, Feb 03 2014
%D Kenneth Edwards, Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
%D L. Euler, (E388) Vollstaendige Anleitung zur Algebra, Zweiter Theil, reprinted in: Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 1, p. 322.
%D S. Heubach, Tiling an m X n Area with Squares of Size up to k X k (m<=5), Congressus Numerantium 140 (1999), pp. 43-64.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A002478/b002478.txt">Table of n, a(n) for n = 0..300</a>
%H Paul Barry, <a href="https://arxiv.org/abs/2104.01644">Centered polygon numbers, heptagons and nonagons, and the Robbins numbers</a>, arXiv:2104.01644 [math.CO], 2021.
%H Emeric Deutsch, <a href="http://www.jstor.org/stable/3647950">Counting tilings with L-tiles and squares</a>, Problem 10877, Amer. Math. Monthly, 110 (March 2003), 245-246.
%H Kenneth Edwards and Michael A. Allen, <a href="https://arxiv.org/abs/1907.06517">A new combinatorial interpretation of the Fibonacci numbers squared</a>, arXiv:1907.06517 [math.CO], 2019.
%H Leonhard Euler, <a href="http://www.mathematik.uni-bielefeld.de/~sieben/euler/euler_2.djvu">Vollstaendige Anleitung zur Algebra, Zweiter Teil</a>.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=412">Encyclopedia of Combinatorial Structures 412</a>
%H Milan Janjić, <a href="https://arxiv.org/abs/1705.02497">Pascal Triangle and Restricted Words</a>, arXiv:1705.02497 [math.CO], 2017.
%H Milan Janjić, <a href="https://www.emis.de/journals/JIS/VOL21/Janjic2/janjic103.html">Pascal Matrices and Restricted Words</a>, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.
%H Richard J. Mathar, <a href="http://arxiv.org/abs/1311.6135">Paving Rectangular Regions with Rectangular Tiles: Tatami and Non-Tatami Tilings</a>, arXiv:1311.6135 [math.CO], 2013, Table 19 (halved...).
%H Richard J. Mathar, <a href="https://arxiv.org/abs/2404.18806">Bivariate Generating Functions Enumerating Non-Bonding Dominoes on Rectangular Boards</a>, arXiv:2404.18806 [math.CO], 2024. See p. 5.
%H Sam Northshield, <a href="https://www.researchgate.net/profile/Sam-Northshield/publication/366321658_SOME_GENERALIZATIONS_OF_A_FORMULA_OF_REZNICK/">Some generalizations of a formula of Reznick</a>, SUNY Plattsburgh (2022).
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,1).
%F G.f.: 1 / (1-x-2*x^2-x^3). [_Simon Plouffe_ in his 1992 dissertation.]
%F a(n) = a(n-1) + 2*a(n-2) + a(n-3).
%F a(n) = Sum_{k=0..n} binomial(2*n-2*k, k). - _Paul Barry_, Nov 13 2004
%F a(n) = Sum_{k=0..floor(n/2)} Sum_{j=0..n-k} C(j, n-k-j)*C(j, k). - _Paul Barry_, Nov 09 2005
%F a(n) = Sum_{k=0..n} C(2*k,n-k) = Sum_{k=0..n} C(n,k)*C(3*k,n)/C(3*k,k). - _Paul Barry_, Feb 04 2006
%F a(n) = A000930(n) + 2*Sum_{i=0..n-2} a(i)*A000930(n-2-i). - _Michael Tulskikh_, Jun 07 2020
%e a(3)=6 as there is one tiling of a 3 X 3 region with only 1 X 1 tiles, 4 tilings with exactly one 2 X 2 tile and 1 tiling consisting of the 3 X 3 tile.
%t f[A_]:= Module[{til = A}, AppendTo[til, A[[-1]] + 2A[[-2]] + A[[-3]]]]; NumOfTilings[ n_ ]:= Nest[ f, {1,1,3}, n-2]; NumOfTilings[30]
%t LinearRecurrence[{1,2,1},{1,1,3},40] (* _Vladimir Joseph Stephan Orlovsky_, Jan 28 2012 *)
%o (PARI) a(n)=([0,1,0; 0,0,1; 1,2,1]^n*[1;1;3])[1,1] \\ _Charles R Greathouse IV_, Apr 08 2016
%o (Magma) I:=[1,1,3]; [n le 3 select I[n] else Self(n-1) +2*Self(n-2) +Self(n-3): n in [1..41]]; // _G. C. Greubel_, Apr 14 2023
%o (SageMath)
%o @CachedFunction
%o def a(n): # A002478
%o if (n<3): return (1,1,3)[n]
%o else: return sum(binomial(2,j)*a(n-j) for j in range(1,4))
%o [a(n) for n in (0..40)] # _G. C. Greubel_, Apr 14 2023
%Y Cf. A000930, A054856, A054857, A025234, A078007, A078039, A226546, A077936 (INVERT transform), A008346 (inverse INVERT transform).
%K easy,nonn,nice,changed
%O 0,3
%A _N. J. A. Sloane_
%E Additional comments from Silvia Heubach (silvi(AT)cine.net), Apr 21 2000
|
