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.

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

Offset: 1

Author

Ralf Stephan, Oct 16 2004

Keywords

• tabl
• nonn

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

Examples

			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, ...
		

References

• S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.
• 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.
• R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 2nd ed., pp. 547 and 570.
• 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, arXiv:math/0610925 [math.CO], 2006.
• Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
• F. Ardila and R. P. Stanley, Tilings, arXiv:math/0501170 [math.CO], 2005.
• 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.
• Henry Cohn, 2-adic behavior of numbers of domino tilings, arXiv:math/0008222 [math.CO], 2000.
• Henry Cohn, 2-adic behavior of numbers of domino tilings, Electronic Journal of Combinatorics, 6 (1999), #R14.
• F. Faase, Counting Hamiltonian cycles in product graphs
• F. Faase, Results from the counting program
• Steven R. Finch, The Dimer Problem [From Steven Finch, Apr 20 2019]
• Steven R. Finch, Two Dimensional Monomer Dimer Constant [Broken link]
• 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, and 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.
• Peter E. John and Horst Sachs, On a strange observation in the theory of the dimer problem, arXiv:math/9801094 [math.CO], 1998.
• 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.
• Yuhi Kamio, Junnosuke Koizumi, and Toshihiko Nakazawa, Quadratic residues and domino tilings, arXiv:2311.13597 [math.NT], 2023.
• David Klarner and Jordan Pollack, Domino tilings of rectangles with fixed width, Disc. Math. 32 (1980) 45-52, Table 1.
• Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
• 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.
• Douglas M. McKenna, The Art of Space-Filling Domino Curves, Bridges Conference Proceedings, 2024, pp. 319-326.
• L. Pachter, Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes, Electronic Journal of Combinatorics 4 (1997), #R29.
• J. Propp, Dimers and Dominoes
• J. Propp, Enumeration of Matchings: Problems and Progress, arXiv:math/9904150v2 [math.CO], 1999.
• Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
• R. C. Read, A Note on Tiling Rectangles with Dominoes, The Fibonacci Quarterly, 18.1 (1980), 24-27.
• R. P. Stanley, A combinatorial miscellany
• H. N. V. Temperley and Michael E. Fisher, Dimer problem in statistical mechanics -- an exact result, Philos. Mag. (8) 6 (1961), 1061-1063.
• Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).
• 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

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-13, 16 (without zeros) are A000045, A001835, A005178, A003775, A028468, A028469, A028470, A028471, A028472, A028473, A028474, A241908, A340532.

Main diagonal is A004003.

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

Programs

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[?OddQ, ?OddQ] = 0;
T[m_, n_] := Product[2*(2+Cos[2j*Pi/(m+1)]+Cos[2k*Pi/(n+1)]), {k, 1, n/2}, {j, 1, m/2}];
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 *)

PARI

{T(n, k) = sqrtint(abs(polresultant(polchebyshev(n, 2, x/2), polchebyshev(k, 2, I*x/2))))} \\ Seiichi Manyama, Apr 13 2020

Formula

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

Extensions

Old link fixed and new link added by Frans J. Faase, Feb 04 2009

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