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

1, 2, 9, 32, 121, 450, 1681, 6272, 23409, 87362, 326041, 1216800, 4541161, 16947842, 63250209, 236052992, 880961761, 3287794050, 12270214441, 45793063712, 170902040409, 637815097922, 2380358351281, 8883618307200, 33154114877521, 123732841202882

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• changed

Comments

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

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

Also stacking bricks.

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

Partial sums of A217233. - Bruno Berselli, Oct 01 2012

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

Examples

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

References

• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 360.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• S. Butler and S. Osborne, Counting tilings by taking walks, preprint, 2012; J. Combin. Math. Combin. Comput. 88 2014 17-25. - From _N. J. A. Sloane_, Dec 27 2012
• M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97
• D. Deford, Seating rearrangements on arbitrary graphs, preprint 2013; involve, Vol. 7 (2014), No. 6, 787-805.
• F. Faase, Counting Hamiltonian cycles in product graphs
• F. Faase, Results from the counting program
• F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
• Charles H. Jepsen, Packing a box with bricks, Math. Mag. 64 (2) (1991) 92-97, Table 1
• W. Jockusch, Perfect matchings and perfect squares J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.
• R. J. Mathar, Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices, arXiv:1406.7788 (2014), eq. (36).
• Valcho Milchev and Tsvetelina Karamfilova, Domino tiling in grid - new dependence, arXiv:1707.09741 [math.HO], 2017.
• László Németh, Tilings of (2 X 2 X n)-board with colored cubes and bricks, arXiv:1909.11729 [math.CO], 2019.
• 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.
• Radovan Potůček, The number of fillings a 2 X 2 X n prism with 1 X 1 X 2 prisms, Equations (2024) Vol. 3, 104-114.
• H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
• H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences Integers, Volume 12A (2012) The John Selfridge Memorial Volume
• Index entries for sequences related to dominoes
• Index entries for sequences related to bricks
• Index entries for linear recurrences with constant coefficients, signature (3,3,-1).

Crossrefs

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

Column k=2 of A181206, A189650, A233308.

Cf. A100047.

Programs

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

Magma

m:=30; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x)/(1-3*x-3*x^2+x^3))); // G. C. Greubel, Nov 16 2018

Mathematica

CoefficientList[Series[(1 - x)/(1 - 3 x - 3 x^2 + x^3), {x, 0, 30}], x] (* Vincenzo Librandi, Oct 15 2012 *)
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 *)
LinearRecurrence[{3,3,-1}, {1,2,9}, 30] (* G. C. Greubel, Nov 16 2018 *)
a[ n_] := (-1)^n * ChebyshevU[n, Sqrt[-1/2]]^2; (* Michael Somos, Mar 17 2022 *)

PARI

a(n)=(sqrt(3)+2)^(n+1) \/ 6 \\ Charles R Greathouse IV, Aug 18 2016

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

PARI

Vec((1 - x) / ((1 + x)*(1 - 4*x + x^2)) + O(x^40)) \\ Colin Barker, Dec 16 2017

PARI

{a(n) = simplify((-1)^n * polchebyshev(n, 2, quadgen(-8)/2)^2)}; /* Michael Somos, Mar 17 2022 */

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

Formula

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

Nearest integer to (1/6)*(2+sqrt(3))^(n+1). - Don Knuth, Jul 15 1995

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

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

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).

a(n) + a(n+1) = A001835(n+2). - R. J. Mathar, Dec 06 2013

From Peter Bala, Apr 03 2014: (Start)

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

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.

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

a(n) = (2*(-1)^n + (2-sqrt(3))^(1+n) + (2+sqrt(3))^(1+n)) / 6. - Colin Barker, Dec 16 2017

a(n) = (1 XOR a(n-1))^2/a(n-2). - Jon Maiga, Nov 16 2018

a(n) = a(-2-n) for all n in Z. - Michael Somos, Mar 17 2022

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