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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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)
23
1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, 112202208776036178000000, 2444888770250892795802079170816, 548943583215388338077567813208427340288, 1269984011256235834242602753102293934298576249856 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry. J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.

M. E. Fisher, Statistical mechanics of dimers on a plane lattice, Physical Review, 124 (1961), 1664-1672.

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

P. E. John and H. Sachs, "On a strange observation in the theory of the dimer problem", Discrete Mathematics, 216 (2000), 211-219.

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.

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

T. D. Noe, Table of n, a(n) for n=0..25

M. Aanjaneya and S. P. Pal, Faultfree tromino tilings of rectangles

M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry

H. Cohn, 2-adic behavior of numbers of domino tilings

S. R. Finch, The Dimer Problem

S. R. Finch, Two Dimensional Monomer Dimer Constant

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 363

R. P. Stanley, A combinatorial miscellany

Eric Weisstein's World of Mathematics, Domino Tiling

Index entries for sequences related to dominoes

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}] (* From Jean-Fran├žois Alcover, Jan 04 2012, after Maple *)

CROSSREFS

Cf. A028420, A006253, A006125, A065072, A124997.

Main diagonal of array A099390.

Sequence in context: A001070 A095229 A047832 * A060739 A224733 A134366

Adjacent sequences:  A004000 A004001 A004002 * A004004 A004005 A004006

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane, Greg Huber

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified July 23 03:59 EDT 2014. Contains 244850 sequences.