A002478 Bisection of A000930.
1, 1, 3, 6, 13, 28, 60, 129, 277, 595, 1278, 2745, 5896, 12664, 27201, 58425, 125491, 269542, 578949, 1243524, 2670964, 5736961, 12322413, 26467299, 56849086, 122106097, 262271568, 563332848, 1209982081, 2598919345, 5582216355, 11990037126, 25753389181
Offset: 0
Examples
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.
References
- Kenneth Edwards, Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
- L. Euler, (E388) Vollstaendige Anleitung zur Algebra, Zweiter Theil, reprinted in: Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 1, p. 322.
- 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.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- T. D. Noe, Table of n, a(n) for n = 0..300
- Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
- Emeric Deutsch, Counting tilings with L-tiles and squares, Problem 10877, Amer. Math. Monthly, 110 (March 2003), 245-246.
- Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, arXiv:1907.06517 [math.CO], 2019.
- Leonhard Euler, Vollstaendige Anleitung zur Algebra, Zweiter Teil.
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 412
- Milan Janjić, Pascal Triangle and Restricted Words, arXiv:1705.02497 [math.CO], 2017.
- Milan Janjić, Pascal Matrices and Restricted Words, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.
- Richard J. Mathar, Paving Rectangular Regions with Rectangular Tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 19 (halved...).
- Richard J. Mathar, Bivariate Generating Functions Enumerating Non-Bonding Dominoes on Rectangular Boards, arXiv:2404.18806 [math.CO], 2024. See p. 5.
- Sam Northshield, Some generalizations of a formula of Reznick, SUNY Plattsburgh (2022).
- Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
- Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
- Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.
- Index entries for linear recurrences with constant coefficients, signature (1,2,1).
Crossrefs
Programs
-
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
-
Mathematica
f[A_]:= Module[{til = A}, AppendTo[til, A[[-1]] + 2A[[-2]] + A[[-3]]]]; NumOfTilings[ n_ ]:= Nest[ f, {1,1,3}, n-2]; NumOfTilings[30] LinearRecurrence[{1,2,1},{1,1,3},40] (* Vladimir Joseph Stephan Orlovsky, Jan 28 2012 *) CoefficientList[Series[1/(1-x-2x^2-x^3),{x,0,40}],x] (* Harvey P. Dale, Oct 17 2024 *)
-
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
-
SageMath
@CachedFunction def a(n): # A002478 if (n<3): return (1,1,3)[n] else: return sum(binomial(2,j)*a(n-j) for j in range(1,4)) [a(n) for n in (0..40)] # G. C. Greubel, Apr 14 2023
Formula
G.f.: 1 / (1-x-2*x^2-x^3). [Simon Plouffe in his 1992 dissertation.]
a(n) = a(n-1) + 2*a(n-2) + a(n-3).
a(n) = Sum_{k=0..n} binomial(2*n-2*k, k). - Paul Barry, Nov 13 2004
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
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
Extensions
Additional comments from Silvia Heubach (silvi(AT)cine.net), Apr 21 2000
Comments