The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A004003 Number of domino tilings (or dimer coverings) of a 2n X 2n square. (Formerly M2160) 37
 1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, 112202208776036178000000, 2444888770250892795802079170816, 548943583215388338077567813208427340288, 1269984011256235834242602753102293934298576249856 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS A099390 is the main entry for domino tilings (or dimer tilings) of a rectangle. The numbers of domino tilings in A006253, A004003, A006125 give 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 Christine Bessenrodt points out that Pachter (1997) shows that a(n) is divisible by 2^n (cf. A065072). a(n) is the number of different ways to cover a 2n X 2n lattice with 2n^2 dominoes. John and Sachs show that a(n) = 2^n*B(n)^2, where B(n) == n+1 (mod 32) when n is even and B(n) == (-1)^((n-1)/2)*n (mod 32) when n is odd. - Yong Kong (ykong(AT)curagen.com), May 07 2000 REFERENCES Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 569. S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412. N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). Darko Veljan, Kombinatorika s teorijom grafova (Croatian) (Combinatorics with Graph Theory) mentions the value 12988816 = 2^4*901^2 for the 8 X 8 case on page 4. LINKS Alois P. Heinz, Table of n, a(n) for n = 0..44 (first 26 terms from T. D. Noe) M. Aanjaneya and S. P. Pal, Faultfree tromino tilings of rectangles, arXiv:math/0610925 [math.CO], 2006. N. Allegra, Exact solution of the 2d dimer model: Corner free energy, correlation functions and combinatorics, arXiv:1410.4131 [cond-mat.stat-mech], 2014. M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, Journal of Combinatorial Theory, Series A, Volume 77, Issue 1, January 1997, Pages 67-97. H. Cohn, 2-adic behavior of numbers of domino tilings, arXiv:math/0008222 [math.CO], 2000. Steven R. Finch, The Dimer Problem [From Steven Finch, Apr 20 2019] M. E. Fisher, Statistical mechanics of dimers on a plane lattice, Physical Review, 124 (1961), 1664-1672. P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 363 Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, Tianyuan Xu, Sandpiles and Dominos, Electronic Journal of Combinatorics, Volume 22(1), 2015. Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, Tianyuan Xu, Illustration for a(2) = 36 [Fig. 9 from "Sandpiles and Dominos"] W. Jockusch, Perfect matchings and perfect squares J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115. Peter E. John and Horst Sachs, On a strange observation in the theory of the dimer problem, Discrete Math. 216 (2000), no. 1-3, 211-219. Adrien Kassel, Le modèle de dimères, Images des Mathématiques, CNRS, 2016. [In French] P. W. Kasteleyn, The Statistics of Dimers on a Lattice, Physica, 27 (1961), 1209-1225. P. W. Kasteleyn, Dimer statistics and phase transitions, J. Mathematical Phys. 4 1963 287-293.  MR0153427 (27 #3394). Lior Pachter, Combinatorial approaches and conjectures ..., Elec. J. Comb. 4 (1997) #R29. Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640. R. P. Stanley, A combinatorial miscellany Eric Weisstein's World of Mathematics, Domino Tiling Eric Weisstein, Illustration for a(2) = 36, from Domino Tilings web page (see previous link) [Included with permission] FORMULA a(n) = A099390(2n,2n). a(n) = Prod_{j=1..n} Prod_{k=1..n} [4*cos(j*Pi/(2*n+1))^2 + 4*cos(k*Pi/(2*n+1))^2]. - N. J. A. Sloane, Mar 16 2015 a(n) = 2^n * A065072(n)^2. - Alois P. Heinz, Nov 22 2018 a(n)^2 = Resultant(U(2*n,x/2), U(2*n,i*x/2)), where U(n,x) is a Chebyshev polynomial of the second kind and i = sqrt(-1). - Seiichi Manyama, Apr 13 2020 EXAMPLE The 36 solutions for the 4 X 4 board, from Neven Juric, May 14 2008: A01 = {(1,2), (3,4), (5,6), (7,8), (9,10), (11,12), (13,14), (15,16)} A02 = {(1,2), (3,4), (5,6), (7,11), (9,10), (8,12), (13,14), (15,16)} A03 = {(1,2), (3,4), (5,9), (6,7), (10,11), (8,12), (13,14), (15,16)} A04 = {(1,2), (3,4), (5,9), (6,10), (7,8), (11,12), (13,14), (15,16)} A05 = {(1,2), (3,4), (5,9), (6,10), (7,11), (8,12), (13,14), (15,16)} A06 = {(1,2), (3,4), (5,6), (7,8), (9,10), (13,14), (11,15), (12,16)} A07 = {(1,2), (3,4), (5,9), (6,10), (7,8), (11,15), (13,14), (12,16)} A08 = {(1,2), (3,4), (5,6), (7,8), (9,13), (10,14), (11,12), (15,16)} A09 = {(1,2), (3,4), (5,6), (7,11), (8,12), (9,13), (10,14), (15,16)} A10 = {(1,2), (3,4), (5,6), (7,8), (9,13), (10,11), (14,15), (12,16)} A11 = {(1,2), (3,4), (5,6), (7,8), (9,13), (10,14), (11,15), (12,16)} A12 = {(1,2), (5,6), (3,7), (4,8), (9,10), (11,12), (13,14), (15,16)} A13 = {(1,2), (3,7), (4,8), (5,9), (6,10), (11,12), (13,14), (15,16)} A14 = {(1,2), (5,6), (3,7), (4,8), (9,10), (13,14), (11,15), (12,16)} A15 = {(1,2), (3,7), (4,8), (6,10), (5,9), (11,15), (12,16), (13,14)} A16 = {(1,2), (3,7), (4,8), (5,6), (9,13), (10,14), (11,12), (15,16)} A17 = {(1,2), (3,7), (4,8), (5,6), (9,13), (10,11), (14,15), (12,16)} A18 = {(1,2), (5,6), (3,7), (4,8), (9,13), (10,14), (11,15), (12,16)} A19 = {(1,5), (2,6), (3,4), (7,8), (9,10), (11,12), (13,14), (15,16)} A20 = {(1,5), (2,6), (3,4), (7,11), (8,12), (9,10), (13,14), (15,16)} A21 = {(1,5), (3,4), (2,6), (9,10), (7,8), (11,15), (13,14), (12,16)} A22 = {(1,5), (2,6), (3,4), (7,8), (9,13), (10,14), (11,12), (15,16)} A23 = {(1,5), (2,6), (3,4), (7,11), (8,12), (9,13), (10,14), (15,16)} A24 = {(1,5), (2,6), (3,4), (7,8), (9,13), (10,11), (14,15), (12,16)} A25 = {(1,5), (2,6), (3,4), (7,8), (9,13), (10,14), (11,15), (12,16)} A26 = {(1,5), (2,3), (6,7), (4,8), (9,10), (11,12), (13,14), (15,16)} A27 = {(1,5), (2,6), (3,7), (4,8), (9,10), (11,12), (13,14), (15,16)} A28 = {(1,5), (2,3), (6,7), (4,8), (9,10), (11,15), (13,14), (12,16)} A29 = {(1,5), (2,6), (3,7), (4,8), (9,10), (13,14), (11,15), (12,16)} A30 = {(1,5), (2,3), (6,7), (4,8), (9,13), (10,14), (11,12), (15,16)} A31 = {(1,5), (2,6), (3,7), (4,8), (9,13), (10,14), (11,12), (15,16)} A32 = {(1,5), (2,6), (3,7), (4,8), (9,13), (10,14), (11,15), (12,16)} A33 = {(1,5), (2,6), (3,7), (4,8), (9,13), (10,11), (14,15), (12,16)} A34 = {(1,5), (2,3), (4,8), (6,10), (7,11), (9,13), (14,15), (12,16)} A35 = {(1,5), (2,3), (6,7), (4,8), (9,13), (10,14), (11,15), (12,16)} A36 = {(1,5), (2,3), (6,7), (4,8), (9,13), (10,11), (14,15), (12,16)} MAPLE f := n->2^(2*n^2)*product(product(cos(i*Pi/(2*n+1))^2+cos(j*Pi/(2*n+1))^2, j=1..n), i=1..n); for k from 0 to 12 do round(evalf(f(k), 300)) od; MATHEMATICA a[n_] := Round[ N[ Product[ 2*Cos[(2i*Pi)/(2n+1)] + 2*Cos[(2j*Pi)/(2n+1)] + 4,  {i, 1, n}, {j, 1, n}], 300] ]; Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Jan 04 2012, after Maple *) PROG (PARI) {a(n) = sqrtint(polresultant(polchebyshev(2*n, 2, x/2), polchebyshev(2*n, 2, I*x/2)))} \\ Seiichi Manyama, Apr 13 2020 CROSSREFS Cf. A028420, A006253, A006125, A065072, A124997, A239273, A256043. Main diagonal of array A099390 or A187596. Sequence in context: A001070 A095229 A047832 * A060739 A333209 A224733 Adjacent sequences:  A004000 A004001 A004002 * A004004 A004005 A004006 KEYWORD nonn,easy,nice AUTHOR EXTENSIONS Corrected and extended by David Radcliffe 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 26 09:37 EDT 2020. Contains 334620 sequences. (Running on oeis4.)