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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002478 Bisection of A000930.
(Formerly M2572 N1017)
53

%I M2572 N1017 #125 Apr 15 2023 15:56:25

%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 Janjic, <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 R. 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 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

%O 0,3

%A _N. J. A. Sloane_

%E Additional comments from Silvia Heubach (silvi(AT)cine.net), Apr 21 2000

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)