cp's OEIS Frontend

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.

%I A099390 #141 Feb 16 2025 08:32:55
%S A099390 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 A099390 95,95,41,21,1,0,34,0,281,0,281,0,34,0,1,55,153,781,1183,1183,781,153,
%U A099390 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 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.
%C A099390 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 A099390 S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.
%D A099390 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 A099390 R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 2nd ed., pp. 547 and 570.
%D A099390 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 A099390 Alois P. Heinz, <a href="/A099390/b099390.txt">Table of n, a(n) for n = 1..1035</a>
%H A099390 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 A099390 Mudit Aggarwal and Samrith Ram, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Ram/ram3.html">Generating Functions for Straight Polyomino Tilings of Narrow Rectangles</a>, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
%H A099390 F. Ardila and R. P. Stanley, <a href="https://arxiv.org/abs/math/0501170">Tilings</a>, arXiv:math/0501170 [math.CO], 2005.
%H A099390 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 A099390 Henry 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 A099390 Henry Cohn, <a href="https://doi.org/10.37236/1446">2-adic behavior of numbers of domino tilings</a>, Electronic Journal of Combinatorics, 6 (1999), #R14.
%H A099390 F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>
%H A099390 F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H A099390 Steven R. Finch, <a href="/FinchDimer.html">The Dimer Problem</a> [From Steven Finch, Apr 20 2019]
%H A099390 Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/md/md.html">Two Dimensional Monomer Dimer Constant</a> [Broken link]
%H A099390 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 A099390 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 363.
%H A099390 Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, and Tianyuan Xu, <a href="https://doi.org/10.37236/4472">Sandpiles and Dominos</a>, Electronic Journal of Combinatorics, Volume 22(1), 2015.
%H A099390 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 A099390 Peter E. John and Horst 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 A099390 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 A099390 Yuhi Kamio, Junnosuke Koizumi, and Toshihiko Nakazawa, <a href="https://arxiv.org/abs/2311.13597">Quadratic residues and domino tilings</a>, arXiv:2311.13597 [math.NT], 2023.
%H A099390 David Klarner and Jordan Pollack, <a href="https://doi.org/10.1016/0012-365X(80)90098-9">Domino tilings of rectangles with fixed width</a>, Disc. Math. 32 (1980) 45-52, Table 1.
%H A099390 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 A099390 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 A099390 Douglas M. McKenna, <a href="https://archive.bridgesmathart.org/2024/bridges2024-319.html">The Art of Space-Filling Domino Curves</a>, Bridges Conference Proceedings, 2024, pp. 319-326.
%H A099390 L. Pachter, <a href="https://doi.org/10.37236/1314">Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes</a>, Electronic Journal of Combinatorics 4 (1997), #R29.
%H A099390 J. Propp, <a href="http://jamespropp.org/domino.ps.gz">Dimers and Dominoes</a>
%H A099390 J. Propp, <a href="http://arxiv.org/abs/math/9904150">Enumeration of Matchings: Problems and Progress</a>, arXiv:math/9904150v2 [math.CO], 1999.
%H A099390 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 A099390 R. C. Read, <a href="https://web.archive.org/web/2024*/https://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 A099390 R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/comb.pdf">A combinatorial miscellany</a>
%H A099390 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 A099390 Herman Tulleken, <a href="https://www.researchgate.net/publication/333296614_Polyominoes">Polyominoes 2.2: How they fit together</a>, (2019).
%H A099390 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DominoTiling.html">Domino Tiling</a>
%H A099390 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 A099390 <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>
%F A099390 T(m, n) = Product_{j=1..ceiling(m/2)} Product_{k=1..ceiling(n/2)} (4*cos(j*Pi/(m+1))^2 + 4*cos(k*Pi/(n+1))^2).
%e A099390 0,  1,  0,   1,    0,    1, ...
%e A099390 1,  2,  3,   5,    8,   13, ...
%e A099390 0,  3,  0,  11,    0,   41, ...
%e A099390 1,  5, 11,  36,   95,  281, ...
%e A099390 0,  8,  0,  95,    0, 1183, ...
%e A099390 1, 13, 41, 281, 1183, 6728, ...
%p A099390 (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 A099390 Digits:=100;
%p A099390 p:=evalf(Pi);
%p A099390 z:=proc(h,d) global p; evalf(cos( h*p/(2*d+1) )); end;
%p A099390 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 A099390 [seq(T(1,n),n=0..10)]; # A001519
%p A099390 [seq(T(2,n),n=0..10)]; # A188899
%p A099390 [seq(T(3,n),n=0..10)]; # A256044
%p A099390 [seq(T(n,n),n=0..10)]; # A004003
%t A099390 T[_?OddQ, _?OddQ] = 0;
%t A099390 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 A099390 Flatten[Table[Round[T[m-n+1, n]], {m, 1, 12}, {n, 1, m}]] (* _Jean-François Alcover_, Nov 25 2011, updated May 28 2022 *)
%o A099390 (PARI) {T(n, k) = sqrtint(abs(polresultant(polchebyshev(n, 2, x/2), polchebyshev(k, 2, I*x/2))))} \\ _Seiichi Manyama_, Apr 13 2020
%Y A099390 See A187596 for another version (with m >= 0, n >= 0). See A187616 for a triangular version. See also A187617, A187618.
%Y A099390 See also A004003 for more literature on the dimer problem.
%Y A099390 Rows 2-13, 16 (without zeros) are A000045, A001835, A005178, A003775, A028468, A028469, A028470, A028471, A028472, A028473, A028474, A241908, A340532.
%Y A099390 Main diagonal is A004003.
%Y A099390 Cf. A103997, A103999, A233320, A230031, A233427.
%K A099390 tabl,nonn
%O A099390 1,5
%A A099390 _Ralf Stephan_, Oct 16 2004
%E A099390 Old link fixed and new link added by _Frans J. Faase_, Feb 04 2009
%E A099390 Entry edited by _N. J. A. Sloane_, Mar 15 2015