A006253 - OEIS

%I M1926 #122 Jul 19 2024 19:30:37

%S 1,2,9,32,121,450,1681,6272,23409,87362,326041,1216800,4541161,

%T 16947842,63250209,236052992,880961761,3287794050,12270214441,

%U 45793063712,170902040409,637815097922,2380358351281,8883618307200,33154114877521,123732841202882

%N Number of perfect matchings (or domino tilings) in C_4 X P_n.

%C Number of tilings of a box with sides 2 X 2 X n in R^3 by boxes of sides 2 X 1 X 1 (3-dimensional dominoes). - _Frans J. Faase_

%C The number of domino tilings in A006253, A004003, A006125 is the number of perfect matchings in the relevant graphs. There are results of Jockusch and Ciucu that if a planar graph has a rotational symmetry then the number of perfect matchings is a square or twice a square - this applies to these 3 sequences. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001

%C Also stacking bricks.

%C a(n)*(-1)^n = (1-T(n+1,-2))/3, n>=0, with Chebyshev's polynomials T(n,x) of the first kind, is the r=-2 member of the r-family of sequences S_r(n) defined in A092184 where more information can be found. - _Wolfdieter Lang_, Oct 18 2004

%C Partial sums of A217233. - _Bruno Berselli_, Oct 01 2012

%C The sequence is the case P1 = 2, P2 = -8, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - _Peter Bala_, Apr 03 2014

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 360.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A006253/b006253.txt">Table of n, a(n) for n = 0..1000</a>

%H S. Butler and S. Osborne, <a href="http://orion.math.iastate.edu/butler/papers/14_02_walks.pdf">Counting tilings by taking walks</a>, preprint, 2012; J. Combin. Math. Combin. Comput. 88 2014 17-25. - From _N. J. A. Sloane_, Dec 27 2012

%H M. Ciucu, <a href="http://dx.doi.org/10.1006/jcta.1996.2725">Enumeration of perfect matchings in graphs with reflective symmetry</a>, J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97

%H D. Deford, <a href="http://www.math.dartmouth.edu/~ddeford/graphs.pdf">Seating rearrangements on arbitrary graphs</a>, preprint 2013; involve, Vol. 7 (2014), No. 6, 787-805.

%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>

%H W. Jockusch, <a href="http://dx.doi.org/10.1016/0097-3165(94)90006-X">Perfect matchings and perfect squares</a> J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.

%H R. J. Mathar, <a href="https://arxiv.org/abs/1406.7788">Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices</a>, arXiv:1406.7788 (2014), eq. (36).

%H Valcho Milchev and Tsvetelina Karamfilova, <a href="https://arxiv.org/abs/1707.09741">Domino tiling in grid - new dependence</a>, arXiv:1707.09741 [math.HO], 2017.

%H László Németh, <a href="https://arxiv.org/abs/1909.11729">Tilings of (2 X 2 X n)-board with colored cubes and bricks</a>, arXiv:1909.11729 [math.CO], 2019.

%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 Radovan Potůček, <a href="https://doi.org/10.37394/232021.2023.3.12">The number of fillings a 2 X 2 X n prism with 1 X 1 X 2 prisms</a>, Equations (2024) Vol. 3, 104-114.

%H H. C. Williams and R. K. Guy, <a href="http://dx.doi.org/10.1142/S1793042111004587">Some fourth-order linear divisibility sequences</a>, Intl. J. Number Theory 7 (5) (2011) 1255-1277.

%H H. C. Williams and R. K. Guy, <a href="https://www.emis.de/journals/INTEGERS/papers/a17self/a17self.Abstract.html">Some Monoapparitic Fourth Order Linear Divisibility Sequences</a> Integers, Volume 12A (2012) The John Selfridge Memorial Volume

%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>

%H <a href="/index/Br#bricks">Index entries for sequences related to bricks</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,3,-1).

%F G.f.: (1-x)/((1+x)*(1-4*x+x^2)) = (1-x)/(1-3*x-3*x^2+x^3). - _Simon Plouffe_ in his 1992 dissertation; typo corrected by _Vincenzo Librandi_, Oct 15 2012

%F Nearest integer to (1/6)*(2+sqrt(3))^(n+1). - _Don Knuth_, Jul 15 1995

%F For n >= 4, a(n) = 3a(n-1) + 3a(n-2) - a(n-3). - Avi Peretz (njk(AT)netvision.net.il), Mar 30 2001

%F For n >= 3, a(n) = 4a(n-1) - a(n-2) + 2*(-1)^n. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 14 2001

%F From Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 11 2001: The values are a(1) = 2 * 1^2, a(2) = 3^2, a(3) = 2 * 4^2, a(4) = 11^2, a(5) = 2 * 15^2, ... and in general for odd n a(n) is twice a square, for even n a(n) is a square. If we define b(n) by b(n) = sqrt(a(n)) for even n, b(n) = sqrt(a(n)/2) for odd n then apart from the first 2 elements b(n) is A002530(n+1).

%F a(n) + a(n+1) = A001835(n+2). - _R. J. Mathar_, Dec 06 2013

%F From _Peter Bala_, Apr 03 2014: (Start)

%F a(n) = |U(n,i/sqrt(2))|^2 where U(n,x) denotes the Chebyshev polynomial of the second kind.

%F a(n-1) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, 2; 1, 1] and T(n,x) denotes the Chebyshev polynomial of the first kind.

%F See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences. (End)

%F a(n) = (2*(-1)^n + (2-sqrt(3))^(1+n) + (2+sqrt(3))^(1+n)) / 6. - _Colin Barker_, Dec 16 2017

%F a(n) = (1 XOR a(n-1))^2/a(n-2). - _Jon Maiga_, Nov 16 2018

%F a(n) = a(-2-n) for all n in Z. - _Michael Somos_, Mar 17 2022

%F INVERT transform of sequence p(n), n > 0, where p is the number of nonreducible tilings by height of 2 X 2 X n using dicubes; p is (2, 5, 4, 4, 4, 4...). - _Nicolas Bělohoubek_, Jun 04 2024

%e G.f. = 1 + 2*x + 9*x^2 + 32*x^3 + 121*x^4 + 450*x^5 + ... - _Michael Somos_, Mar 17 2022

%t CoefficientList[Series[(1 - x)/(1 - 3 x - 3 x^2 + x^3), {x, 0, 30}], x] (* _Vincenzo Librandi_, Oct 15 2012 *)

%t RecurrenceTable[{a[1] == 1, a[2] == 2, a[n] == BitXor[1, a[n - 1]]^2/a[n - 2]}, a, {n, 30}] (* _Jon Maiga_, Nov 16 2018 *)

%t LinearRecurrence[{3,3,-1}, {1,2,9}, 30] (* _G. C. Greubel_, Nov 16 2018 *)

%t a[ n_] := (-1)^n * ChebyshevU[n, Sqrt[-1/2]]^2; (* _Michael Somos_, Mar 17 2022 *)

%o (PARI) a(n)=(sqrt(3)+2)^(n+1) \/ 6 \\ _Charles R Greathouse IV_, Aug 18 2016

%o (PARI) a(n)=([0,1,0; 0,0,1; -1,3,3]^n*[1;2;9])[1,1] \\ _Charles R Greathouse IV_, Aug 18 2016

%o (PARI) Vec((1 - x) / ((1 + x)*(1 - 4*x + x^2)) + O(x^40)) \\ _Colin Barker_, Dec 16 2017

%o (PARI) {a(n) = simplify((-1)^n * polchebyshev(n, 2, quadgen(-8)/2)^2)}; /* _Michael Somos_, Mar 17 2022 */

%o (Magma) m:=30; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x)/(1-3*x-3*x^2+x^3))); // _G. C. Greubel_, Nov 16 2018

%o (Sage) s=((1-x)/(1-3*x-3*x^2+x^3)).series(x,30); s.coefficients(x, sparse=False) # _G. C. Greubel_, Nov 16 2018

%o (GAP) a:=[1,2,9];; for n in [4..30] do a[n]:=3*a[n-1]+3*a[n-2]-a[n-3]; od; a; # _G. C. Greubel_, Nov 16 2018

%Y Cf. A002530, A004003, A006125, A217233 (first differences), A109437 (partial sums).

%Y Column k=2 of A181206, A189650, A233308.

%Y Cf. A100047.

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_