login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006253 Number of perfect matchings (or domino tilings) in C_4 X P_n.
(Formerly M1926)
18
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

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

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 Hamilton cycles in product graphs

F. Faase, Results from the counting program

W. Jockusch, Perfect matchings and perfect squares J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.

Valcho Milchev and Tsvetelina Karamfilova, Domino tiling in grid - new dependence, arXiv:1707.09741 [math.HO], 2017.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

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

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.

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

MATHEMATICA

CoefficientList[Series[(1 - x)/(1 - 3 x - 3 x^2 + x^3), {x, 0, 30}], x] (* Vincenzo Librandi, Oct 15 2012 *)

PROG

(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

CROSSREFS

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

Column k=2 of A181206, A189650, A233308.

Cf. A100047.

Sequence in context: A053369 A076959 A003697 * A045630 A075364 A026526

Adjacent sequences:  A006250 A006251 A006252 * A006254 A006255 A006256

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

Typo corrected in the g.f. by Vincenzo Librandi, Oct 15 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 13 19:25 EST 2018. Contains 317149 sequences. (Running on oeis4.)