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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A099390 Array T(m,n) read by antidiagonals: number of domino tilings (or dimer tilings) of the m X n grid (or m X n rectangle), for m>=1, n>=1. 29
0, 1, 1, 0, 2, 0, 1, 3, 3, 1, 0, 5, 0, 5, 0, 1, 8, 11, 11, 8, 1, 0, 13, 0, 36, 0, 13, 0, 1, 21, 41, 95, 95, 41, 21, 1, 0, 34, 0, 281, 0, 281, 0, 34, 0, 1, 55, 153, 781, 1183, 1183, 781, 153, 55, 1, 0, 89, 0, 2245, 0, 6728, 0, 2245, 0, 89, 0, 1, 144, 571, 6336, 14824, 31529, 31529, 14824, 6336, 571, 144, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

There are many versions of this array (or triangle) in the OEIS. This is the main entry, which ideally collects together all the references to the literature and to other versions in the OEIS. But see A004003 for further information. - N. J. A. Sloane, Mar 14 2015

REFERENCES

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

Henry Cohn, 2-adic behavior of numbers of domino tilings, Electronic Journal of Combinatorics, 6 (1999), #R14.

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.

Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, Tianyuan Xu, Sandpiles and Dominos, Electronic Journal of Combinatorics, Volume 22(1), 2015.

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.

P. E. John, H. Sachs, and H. Zernitz, Problem 5. Domino covers in square chessboards, Zastosowania Matematyki (Applicationes Mathematicae) XIX 3{4 (1987), 635{641.

P. W. Kasteleyn, The statistics of dimers on a lattice, I. the number of dimer arrangements on a quadratic lattice, Physica 27 (1961), 1209-1225.

L. Pachter, Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes, Electronic Journal of Combinatorics 4 (1997), #R29.

Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.

R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 2nd ed., pp. 547 and 570.

H. N. V. Temperley and Michael E. Fisher, Dimer problem in statistical mechanics — an exact result, Philos. Mag. (8) 6 (1961), 1061-1063.

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 = 1..1035

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

F. Ardila and R. P. Stanley, Tilings

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

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

F. Faase, Counting Hamilton cycles in product graphs

F. Faase, Results from the counting program

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

P. E. John and H. Sachs, On a strange observation in the theory of the dimer problem

Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.

J. Propp, Dimers and Dominoes

J. Propp, Enumeration of Matchings: Problems and Progress, arXiv:math/9904150v2 [math.CO]

R. C. Read, A Note on Tiling Rectangles with Dominoes, The Fibonacci Quarterly, 18.1 (1980), 24-27.

R. P. Stanley, A combinatorial miscellany

Eric Weisstein's World of Mathematics, Domino Tiling

Eric Weisstein, Illustration for T(4,4) = 36, from Domino Tilings web page (see previous link) [Included with permission]

Index entries for sequences related to dominoes

FORMULA

If m, n even then T(m, n) = Prod(j=1..m/2, Prod(k=1..n/2, 4*cos(j*Pi/(m+1))^2 + 4*cos(k*Pi/(n+1))^2)).

EXAMPLE

0,  1,  0,   1,    0,    1, ...

1,  2,  3,   5,    8,   13, ...

0,  3,  0,  11,    0,   41, ...

1,  5, 11,  36,   95,  281, ...

0,  8,  0,  95,    0, 1183, ...

1, 13, 41, 281, 1183, 6728, ...

MAPLE

(Maple code for the even-numbered rows from N. J. A. Sloane, Mar 15 2015. This is not totally satisfactory since it uses floating point. However, it is useful for getting the initial values quickly.)

Digits:=100;

p:=evalf(Pi);

z:=proc(h, d) global p; evalf(cos( h*p/(2*d+1) )); end;

T:=proc(m, n) global z; round(mul( mul( 4*z(h, m)^2+4*z(k, n)^2, k=1..n), h=1..m)); end;

[seq(T(1, n), n=0..10)]; # A001519

[seq(T(2, n), n=0..10)]; # A188899

[seq(T(3, n), n=0..10)]; # A256044

[seq(T(n, n), n=0..10)]; # A004003

MATHEMATICA

t[m_, n_] := Product[2*(2 + Cos[2j*Pi/(m+1)] + Cos[2k*Pi/(n+1)]), {k, 1, n/2}, {j, 1, m/2}]; t[_?OddQ, _?OddQ] = 0; Flatten[ Table[ FullSimplify[ t[m-n+1, n]], {m, 1, 12}, {n, 1, m}]](* Jean-François Alcover, Nov 25 2011 *)

CROSSREFS

See A187596 for another version (with m >= 0, n >= 0). See A187616 for a triangular version. See also A187617, A187618.

See also A004003 for more literature on the dimer problem.

Rows 2-12 (without zeros) are A000045, A001835, A005178, A003775, A028468, A028469, A028470, A028471, A028472, A028473, A028474.

Main diagonal is A004003.

Cf. A103997, A103999, A233320, A230031, A233427.

Sequence in context: A103438 A167279 A068920 * A124031 A263097 A241954

Adjacent sequences:  A099387 A099388 A099389 * A099391 A099392 A099393

KEYWORD

tabl,nonn

AUTHOR

Ralf Stephan, Oct 16 2004

EXTENSIONS

Corrected broken URL's. - R. J. Mathar, Jan 06 2009

Fixed old link and added link to results page. - Frans J. Faase, Feb 04 2009

Entry edited by N. J. A. Sloane, Mar 15 2015

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 March 27 22:02 EDT 2017. Contains 284182 sequences.