cp's OEIS Frontend

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

%I A006253 M1926 #125 Aug 31 2025 08:35:42
%S A006253 1,2,9,32,121,450,1681,6272,23409,87362,326041,1216800,4541161,
%T A006253 16947842,63250209,236052992,880961761,3287794050,12270214441,
%U A006253 45793063712,170902040409,637815097922,2380358351281,8883618307200,33154114877521,123732841202882
%N A006253 Number of perfect matchings (or domino tilings) in C_4 X P_n.
%C A006253 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 A006253 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 A006253 Also stacking bricks.
%C A006253 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 A006253 Partial sums of A217233. - _Bruno Berselli_, Oct 01 2012
%C A006253 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 A006253 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 360.
%D A006253 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006253 Vincenzo Librandi, <a href="/A006253/b006253.txt">Table of n, a(n) for n = 0..1000</a>
%H A006253 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 A006253 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 A006253 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 A006253 F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>
%H A006253 F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H A006253 F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
%H A006253 Charles H. Jepsen, <a href="https://doi.org/10.2307/2690755">Packing a box with bricks</a>, Math. Mag. 64 (2) (1991) 92-97, Table 1
%H A006253 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 A006253 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 A006253 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 A006253 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 A006253 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 A006253 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H A006253 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 A006253 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 A006253 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 A006253 <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>
%H A006253 <a href="/index/Br#bricks">Index entries for sequences related to bricks</a>
%H A006253 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,3,-1).
%F A006253 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 A006253 Nearest integer to (1/6)*(2+sqrt(3))^(n+1). - _Don Knuth_, Jul 15 1995
%F A006253 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 A006253 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 A006253 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 A006253 a(n) + a(n+1) = A001835(n+2). - _R. J. Mathar_, Dec 06 2013
%F A006253 From _Peter Bala_, Apr 03 2014: (Start)
%F A006253 a(n) = |U(n,i/sqrt(2))|^2 where U(n,x) denotes the Chebyshev polynomial of the second kind.
%F A006253 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 A006253 See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences. (End)
%F A006253 a(n) = (2*(-1)^n + (2-sqrt(3))^(1+n) + (2+sqrt(3))^(1+n)) / 6. - _Colin Barker_, Dec 16 2017
%F A006253 a(n) = (1 XOR a(n-1))^2/a(n-2). - _Jon Maiga_, Nov 16 2018
%F A006253 a(n) = a(-2-n) for all n in Z. - _Michael Somos_, Mar 17 2022
%F A006253 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 A006253 G.f. = 1 + 2*x + 9*x^2 + 32*x^3 + 121*x^4 + 450*x^5 + ... - _Michael Somos_, Mar 17 2022
%t A006253 CoefficientList[Series[(1 - x)/(1 - 3 x - 3 x^2 + x^3), {x, 0, 30}], x] (* _Vincenzo Librandi_, Oct 15 2012 *)
%t A006253 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 A006253 LinearRecurrence[{3,3,-1}, {1,2,9}, 30] (* _G. C. Greubel_, Nov 16 2018 *)
%t A006253 a[ n_] := (-1)^n * ChebyshevU[n, Sqrt[-1/2]]^2; (* _Michael Somos_, Mar 17 2022 *)
%o A006253 (PARI) a(n)=(sqrt(3)+2)^(n+1) \/ 6 \\ _Charles R Greathouse IV_, Aug 18 2016
%o A006253 (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 A006253 (PARI) Vec((1 - x) / ((1 + x)*(1 - 4*x + x^2)) + O(x^40)) \\ _Colin Barker_, Dec 16 2017
%o A006253 (PARI) {a(n) = simplify((-1)^n * polchebyshev(n, 2, quadgen(-8)/2)^2)}; /* _Michael Somos_, Mar 17 2022 */
%o A006253 (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 A006253 (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 A006253 (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 A006253 Cf. A002530, A004003, A006125, A217233 (first differences), A109437 (partial sums).
%Y A006253 Column k=2 of A181206, A189650, A233308.
%Y A006253 Cf. A100047.
%K A006253 nonn,easy,changed
%O A006253 0,2
%A A006253 _N. J. A. Sloane_