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



(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. 42


%S 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,

%T 95,95,41,21,1,0,34,0,281,0,281,0,34,0,1,55,153,781,1183,1183,781,153,

%U 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

%N 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.

%C 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

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

%D 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.

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

%D 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.

%H Alois P. Heinz, <a href="/A099390/b099390.txt">Table of n, a(n) for n = 1..1035</a>

%H M. Aanjaneya and S. P. Pal, <a href="https://arxiv.org/abs/math/0610925">Faultfree tromino tilings of rectangles</a>, arXiv:math/0610925 [math.CO], 2006.

%H F. Ardila and R. P. Stanley, <a href="https://arxiv.org/abs/math/0501170">Tilings</a>, arXiv:math/0501170 [math.CO], 2005.

%H M. Ciucu, <a href="https://doi.org/10.1006/jcta.1996.2725">Enumeration of perfect matchings in graphs with reflective symmetry</a>, Journal of Combinatorial Theory, Series A, Volume 77, Issue 1, January 1997, Pages 67-97.

%H H. Cohn, <a href="https://arxiv.org/abs/math/0008222">2-adic behavior of numbers of domino tilings</a>, arXiv:math/0008222 [math.CO], 2000.

%H Henry Cohn, <a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v6i1r14">2-adic behavior of numbers of domino tilings</a>, Electronic Journal of Combinatorics, 6 (1999), #R14.

%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>

%H Steven R. Finch, <a href="/FinchDimer.html">The Dimer Problem</a> [From Steven Finch, Apr 20 2019]

%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/md/md.html">Two Dimensional Monomer Dimer Constant</a> [Broken link]

%H M. E. Fisher, <a href="http://dx.doi.org/10.1103/PhysRev.124.1664">Statistical mechanics of dimers on a plane lattice</a>, Physical Review, 124 (1961), 1664-1672.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 363.

%H Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, Tianyuan Xu, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p66">Sandpiles and Dominos</a>, Electronic Journal of Combinatorics, Volume 22(1), 2015.

%H W. Jockusch, <a href="https://dx.doi.org/10.1016/0097-3165(94)90006-X">Perfect matchings and perfect squares</a> J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.

%H P. E. John and H. Sachs, <a href="https://arxiv.org/abs/math/9801094">On a strange observation in the theory of the dimer problem</a>, arXiv:math/9801094 [math.CO], 1998.

%H Peter E. John and Horst Sachs, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00301-5">On a strange observation in the theory of the dimer problem</a>, Discrete Math. 216 (2000), no. 1-3, 211-219.

%H Per Hakan Lundow, <a href="https://www.semanticscholar.org/paper/Enumeration-of-matchings-in-polygraphs-Lundow/95fa86b055ef5705dc58443c7b595ba3ff3b95b1">Enumeration of matchings in polygraphs</a>, 1998.

%H P. W. Kasteleyn, <a href="https://doi.org/10.1016/0031-8914(61)90063-5">The statistics of dimers on a lattice, I. the number of dimer arrangements on a quadratic lattice</a>, Physica 27 (1961), 1209-1225.

%H L. Pachter, <a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v4i1r29">Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes</a>, Electronic Journal of Combinatorics 4 (1997), #R29.

%H J. Propp, <a href="http://jamespropp.org/domino.ps.gz">Dimers and Dominoes</a>

%H J. Propp, <a href="http://arxiv.org/abs/math/9904150">Enumeration of Matchings: Problems and Progress</a>, arXiv:math/9904150v2 [math.CO], 1999.

%H Jaime Rangel-Mondragon, <a href="https://web.archive.org/web/20190411024906/http://www.mathematica-journal.com/issue/v9i3/polyominoes.html">Polyominoes and Related Families</a>, The Mathematica Journal, 9:3 (2005), 609-640.

%H R. C. Read, <a href="http://www.fq.math.ca/Scanned/18-1/read.pdf">A Note on Tiling Rectangles with Dominoes</a>, The Fibonacci Quarterly, 18.1 (1980), 24-27.

%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/comb.pdf">A combinatorial miscellany</a>

%H H. N. V. Temperley and Michael E. Fisher, <a href="https://doi.org/10.1080/14786436108243366">Dimer problem in statistical mechanics — an exact result</a>, Philos. Mag. (8) 6 (1961), 1061-1063.

%H Herman Tulleken, <a href="https://www.researchgate.net/publication/333296614_Polyominoes">Polyominoes 2.2: How they fit together</a>, (2019).

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DominoTiling.html">Domino Tiling</a>

%H Eric Weisstein, <a href="/A004003/a004003.gif">Illustration for T(4,4) = 36</a>, from Domino Tilings web page (see previous link) [Included with permission]

%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>

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

%e 0, 1, 0, 1, 0, 1, ...

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

%e 0, 3, 0, 11, 0, 41, ...

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

%e 0, 8, 0, 95, 0, 1183, ...

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

%p (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.)

%p Digits:=100;

%p p:=evalf(Pi);

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

%p 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;

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

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

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

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

%t 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 *)

%o (PARI) {T(n, k) = sqrtint(abs(polresultant(polchebyshev(n, 2, x/2), polchebyshev(k, 2, I*x/2))))} \\ _Seiichi Manyama_, Apr 13 2020

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

%Y See also A004003 for more literature on the dimer problem.

%Y Rows 2-13, 16 (without zeros) are A000045, A001835, A005178, A003775, A028468, A028469, A028470, A028471, A028472, A028473, A028474, A241908, A340532.

%Y Main diagonal is A004003.

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

%K tabl,nonn

%O 1,5

%A _Ralf Stephan_, Oct 16 2004

%E Corrected broken URL's. - _R. J. Mathar_, Jan 06 2009

%E Fixed old link and added link to results page. - _Frans J. Faase_, Feb 04 2009

%E Entry edited by _N. J. A. Sloane_, Mar 15 2015

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 4 20:58 EST 2021. Contains 341811 sequences. (Running on oeis4.)