A187596 -id:A187596 - cp's OEIS frontend

A004003 Number of domino tilings (or dimer coverings) of a 2n X 2n square.

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, 112202208776036178000000, 2444888770250892795802079170816, 548943583215388338077567813208427340288, 1269984011256235834242602753102293934298576249856

Offset: 0

N. J. A. Sloane, Greg Huber

A099390 is the main entry for domino tilings (or dimer tilings) of a rectangle.
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

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

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 569.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.
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.

Alois P. Heinz, Table of n, a(n) for n = 0..44 (first 26 terms from T. D. Noe)
M. Aanjaneya and S. P. Pal, Faultfree tromino tilings of rectangles, arXiv:math/0610925 [math.CO], 2006.
N. Allegra, Exact solution of the 2d dimer model: Corner free energy, correlation functions and combinatorics, arXiv:1410.4131 [cond-mat.stat-mech], 2014.
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.
H. Cohn, 2-adic behavior of numbers of domino tilings, arXiv:math/0008222 [math.CO], 2000.
Steven R. Finch, The Dimer Problem [From Steven Finch, Apr 20 2019]
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.
Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, and Tianyuan Xu, Illustration for a(2) = 36 [Fig. 9 from "Sandpiles and Dominos"]
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, Discrete Math. 216 (2000), no. 1-3, 211-219.
Adrien Kassel, Le modèle de dimères, Images des Mathématiques, CNRS, 2016. [In French]
P. W. Kasteleyn, The Statistics of Dimers on a Lattice, Physica, 27 (1961), 1209-1225.
P. W. Kasteleyn, Dimer statistics and phase transitions, J. Mathematical Phys. 4 1963 287-293. MR0153427 (27 #3394).
Viet-Ha Nguyen, Kévin Perrot, and Mathieu Vallet, NP-completeness of the game Kingdomino(TM), Theoretical Computer Science (2020) Vol. 822, 23-35. See also arXiv:1909.02849, [cs.CC], 2019.
Lior Pachter, Combinatorial approaches and conjectures ..., Elec. J. Comb. 4 (1997) #R29.
James Propp, Some 2-Adic Conjectures Concerning Polyomino Tilings of Aztec Diamonds, Integers (2023) Vol. 23, Art. A30.
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
N. J. A. Sloane, Illustration for a(2) = 36 [Slide from an old talk I gave]
R. P. Stanley, A combinatorial miscellany
Eric Weisstein's World of Mathematics, Domino Tiling
Eric Weisstein, Illustration for a(2) = 36, from Domino Tilings web page (see previous link) [Included with permission]
Index entries for sequences related to dominoes

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

Main diagonal of array A099390 or A187596.

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;

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}] (* Jean-François Alcover, Jan 04 2012, after Maple *)
Table[Sqrt[Resultant[ChebyshevU[2*n, x/2], ChebyshevU[2*n, I*x/2], x]], {n, 0, 12}] (* Vaclav Kotesovec, Dec 30 2020 *)

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

from math import isqrt
from sympy.abc import x
from sympy import I, resultant, chebyshevu
def A004003(n): return isqrt(resultant(chebyshevu(n<<1,x/2),chebyshevu(n<<1,I*x/2))) if n else 1 # Chai Wah Wu, Nov 07 2023

a(n) = A099390(2n,2n).
a(n) = Product_{j=1..n} Product_{k=1..n} (4*cos(j*Pi/(2*n+1))^2 + 4*cos(k*Pi/(2*n+1))^2). - N. J. A. Sloane, Mar 16 2015
a(n) = 2^n * A065072(n)^2. - Alois P. Heinz, Nov 22 2018
a(n)^2 = Resultant(U(2*n,x/2), U(2*n,i*x/2)), where U(n,x) is a Chebyshev polynomial of the second kind and i = sqrt(-1). - Seiichi Manyama, Apr 13 2020
a(n) ~ 2 * (sqrt(2)-1)^(2*n+1) * exp(G*(2*n+1)^2/Pi), where G is Catalan's constant A006752. - Vaclav Kotesovec, Dec 30 2020

Corrected and extended by David Radcliffe

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.

Original entry on oeis.org

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

Ralf Stephan, Oct 16 2004

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

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

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.

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

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.

(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

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

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

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

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

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

A239264 Number A(n,k) of domicule tilings of a k X n grid; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 3, 0, 1, 1, 1, 5, 5, 1, 1, 1, 0, 11, 0, 11, 0, 1, 1, 1, 21, 43, 43, 21, 1, 1, 1, 0, 43, 0, 280, 0, 43, 0, 1, 1, 1, 85, 451, 1563, 1563, 451, 85, 1, 1, 1, 0, 171, 0, 9415, 0, 9415, 0, 171, 0, 1, 1, 1, 341, 4945, 55553, 162409, 162409, 55553, 4945, 341, 1, 1

Offset: 0

Alois P. Heinz, Mar 13 2014

A domicule is either a domino or it is formed by the union of two neighboring unit squares connected via their corners. In a tiling the connections of two domicules are allowed to cross each other.

			A(3,2) = 5:
  +-----+ +-----+ +-----+ +-----+ +-----+
  |o o-o| |o o o| |o o o| |o o o| |o-o o|
  ||    | ||  X | || | || | X  || |    ||
  |o o-o| |o o o| |o o o| |o o o| |o-o o|
  +-----+ +-----+ +-----+ +-----+ +-----+
A(4,3) = 43:
  +-------+ +-------+ +-------+ +-------+ +-------+
  |o o o o| |o o o-o| |o o-o o| |o o-o o| |o o-o o|
  ||  X  || | X     | | \   / | ||     || | \    ||
  |o o o o| |o o o o| |o o o o| |o o o o| |o o o o|
  |       | |     X | ||     || |   \ \ | ||    \ |
  |o-o o-o| |o-o o o| |o o-o o| |o-o o o| |o o-o o|
  +-------+ +-------+ +-------+ +-------+ +-------+ ...
Square array A(n,k) begins:
  1, 1,  1,   1,    1,      1,       1, ...
  1, 0,  1,   0,    1,      0,       1, ...
  1, 1,  3,   5,   11,     21,      43, ...
  1, 0,  5,   0,   43,      0,     451, ...
  1, 1, 11,  43,  280,   1563,    9415, ...
  1, 0, 21,   0, 1563,      0,  162409, ...
  1, 1, 43, 451, 9415, 162409, 3037561, ...

Alois P. Heinz, Antidiagonals n = 0..36, flattened

Columns (or rows) k=0-10 give: A000012, A059841, A001045(n+1), A239265, A239266, A239267, A239268, A239269, A239270, A239271, A239272.
Bisection of main diagonal gives: A239273.
Cf. A099390, A187616, A187617, A187596, A220644.

b:= proc(n, l) option remember; local d, f, k;
      d:= nops(l)/2; f:=false;
      if n=0 then 1
    elif l[1..d]=[f$d] then b(n-1, [l[d+1..2*d][], true$d])
    else for k to d while not l[k] do od;
         `if`(k1 and l[k+d+1],
                              b(n, subsop(k=f, k+d+1=f, l)), 0)+
         `if`(k>1 and n>1 and l[k+d-1],
                              b(n, subsop(k=f, k+d-1=f, l)), 0)+
         `if`(n>1 and l[k+d], b(n, subsop(k=f, k+d=f, l)), 0)+
         `if`(k `if`(irem(n*k, 2)>0, 0,
    `if`(k>n, A(k, n), b(n, [true$(k*2)]))):
seq(seq(A(n, d-n), n=0..d), d=0..14);

b[n_, l_List] := b[n, l] = Module[{d = Length[l]/2, f = False, k}, Which [n == 0, 1, l[[1 ;; d]] == Array[f&, d], b[n-1, Join[l[[d+1 ;; 2*d]], Array[True&, d]]], True, For[k=1, !l[[k]], k++]; If[k1 && l[[k+d+1]], b[n, ReplacePart[l, {k -> f, k+d+1 -> f}]], 0] + If[k>1 && n>1 && l[[k+d-1]], b[n, ReplacePart[l, {k -> f, k+d-1 -> f}]], 0] + If[n>1 && l[[k+d]], b[n, ReplacePart[l, {k -> f, k+d -> f}]], 0] + If[k f, k+1 -> f}]], 0]]]; A[n_, k_] := If[Mod[n*k, 2]>0, 0, If[k>n, A[k, n], b[n, Array[True&, k*2]]]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Feb 02 2015, after Alois P. Heinz *)

A187617 Array T(m,n) read by antidiagonals: number of domino tilings of the 2m X 2n grid (m>=0, n>=0).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 5, 5, 1, 1, 13, 36, 13, 1, 1, 34, 281, 281, 34, 1, 1, 89, 2245, 6728, 2245, 89, 1, 1, 233, 18061, 167089, 167089, 18061, 233, 1, 1, 610, 145601, 4213133, 12988816, 4213133, 145601, 610, 1

Offset: 0

N. J. A. Sloane, Mar 11 2011

A099390 is the main entry for this problem.
The even-indexed rows and columns of the square array in A187596.
Row (and column) 2 is given by A122367. - Nathaniel Johnston, Mar 22 2011

			The array begins:
  1,  1,     1,       1,          1,            1, ...
  1,  2,     5,      13,         34,           89, ...
  1,  5,    36,     281,       2245,        18061, ...
  1, 13,   281,    6728,     167089,      4213133, ...
  1, 34,  2245,  167089,   12988816,   1031151241, ...
  1, 89, 18061, 4213133, 1031151241, 258584046368, ...

Alois P. Heinz, Antidiagonals n = 0..26, flattened
N. Allegra, Exact solution of the 2d dimer model: Corner free energy, correlation functions and combinatorics, arXiv:1410.4131 [cond-mat.stat-mech], 2014. See Table 1.
Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter and Tianyuan Xu, Sandpiles and Dominos, El. J. Comb., 22 (2015), P1.66. See Theorem 15.
Index entries for sequences related to dominoes

A187618 is the triangle version.
Cf. A187596, A099390, A348566.
Main diagonal is A004003. Second and third rows give A001519, A188899.

ft:=(m,n)->
2^(m*n/2)*mul( mul(
(cos(Pi*i/(n+1))^2+cos(Pi*j/(m+1))^2), j=1..m/2), i=1..n/2);
T:=(m,n)->round(evalf(ft(m,n),300));

T[m_, n_] := Product[2(2 + Cos[(2j Pi)/(2m+1)] + Cos[(2k Pi)/(2n+1)]), {j, 1, m}, {k, 1, n}];
Table[T[m-n, n] // Round, {m, 0, 8}, {n, 0, m}] // Flatten (* Jean-François Alcover, Aug 05 2018 *)

default(realprecision, 120);
{T(n, k) = round(prod(a=1, n, prod(b=1, k, 4*cos(a*Pi/(2*n+1))^2+4*cos(b*Pi/(2*k+1))^2)))} \\ Seiichi Manyama, Jan 09 2021

More terms from Nathaniel Johnston, Mar 22 2011

A187616 Triangle T(m,n) read by rows: number of domino tilings of the m X n grid (0 <= m <= n).

Original entry on oeis.org

1, 1, 0, 1, 1, 2, 1, 0, 3, 0, 1, 1, 5, 11, 36, 1, 0, 8, 0, 95, 0, 1, 1, 13, 41, 281, 1183, 6728, 1, 0, 21, 0, 781, 0, 31529, 0, 1, 1, 34, 153, 2245, 14824, 167089, 1292697, 12988816, 1, 0, 55, 0, 6336, 0, 817991, 0, 108435745, 0, 1, 1, 89, 571, 18061, 185921, 4213133, 53175517, 1031151241, 14479521761, 258584046368

Offset: 0

N. J. A. Sloane, Mar 11 2011

A099390 is the main entry for this problem.

Triangle read by rows: the square array in A187596 with entries above main diagonal deleted.

			Triangle begins:
1
1 0
1 1  2
1 0  3   0
1 1  5  11   36
1 0  8   0   95     0
1 1 13  41  281  1183   6728
1 0 21   0  781     0  31529       0
1 1 34 153 2245 14824 167089 1292697 12988816
...

Alois P. Heinz, Rows n = 1..32, flattened
Index entries for sequences related to dominoes

Cf. A099390, A187596. See A099390 for sequences appearing in the rows and columns. See also A187617, A187618.

with(LinearAlgebra):
T:= proc(m,n) option remember; local i, j, t, M;
      if m<=1 or n<=1 then 1 -irem(n*m, 2)
    elif irem(n*m, 2)=1 then 0
    else M:= Matrix(n*m, shape =skewsymmetric);
         for i to n do
           for j to m do
             t:= (i-1)*m+j;
             if jAlois P. Heinz, Apr 11 2011

T[m_, n_] := T[m, n] = Module[{i, j, t, M}, Which[m <= 1 || n <= 1, 1 - Mod[n*m, 2], Mod[n*m, 2] == 1, 0, True, M[i_, j_] /; j < i := -M[j, i]; M[, ] = 0; For[i = 1, i <= n, i++, For[j = 1, j <= m, j++, t = (i-1)*m+j; If[j < m, M[t, t+1] = 1]; If[i < n, M[t, t+m] = 1 - 2*Mod[j, 2]]]]; Sqrt[Det[Table[M[i, j], {i, 1, n*m}, {j, 1, n*m}]]]]]; Table[Table[T[m, n], {n, 0, m}], {m, 0, 10}] // Flatten (* Jean-François Alcover, Jan 07 2014, translated from Maple *)

A189006 Array A(m,n) read by antidiagonals: number of domino tilings of the m X n grid with upper left corner removed iff m*n is odd, (m>=0, n>=0).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 5, 4, 5, 1, 1, 1, 1, 8, 11, 11, 8, 1, 1, 1, 1, 13, 15, 36, 15, 13, 1, 1, 1, 1, 21, 41, 95, 95, 41, 21, 1, 1, 1, 1, 34, 56, 281, 192, 281, 56, 34, 1, 1, 1, 1, 55, 153, 781, 1183, 1183, 781, 153, 55, 1, 1, 1, 1, 89, 209, 2245, 2415, 6728, 2415, 2245, 209, 89, 1, 1

Offset: 0

Alois P. Heinz, Apr 15 2011

			A(3,3) = 4, because there are 4 domino tilings of the 3 X 3 grid with upper left corner removed:
  . .___. . .___. . .___. . .___.
  ._|___| ._|___| ._| | | ._|___|
  | |___| | | | | | |_|_| |___| |
  |_|___| |_|_|_| |_|___| |___|_|
Array begins:
  1, 1,  1,  1,   1,    1,    1, ...
  1, 1,  1,  1,   1,    1,    1, ...
  1, 1,  2,  3,   5,    8,   13, ...
  1, 1,  3,  4,  11,   15,   41, ...
  1, 1,  5, 11,  36,   95,  281, ...
  1, 1,  8, 15,  95,  192, 1183, ...
  1, 1, 13, 41, 281, 1183, 6728, ...

Alois P. Heinz, Antidiagonals n = 0..75, flattened
Eric Weisstein's World of Mathematics, Perfect Matching
Wikipedia, FKT algorithm
Wikipedia, Matching (graph theory)
Index entries for sequences related to dominoes

Rows m=0+1, 2-12 give: A000012, A000045(n+1), A002530(n+1), A005178(n+1), A189003, A028468, A189004, A028470, A189005, A028472, A210724, A028474.
Main diagonal gives: A189002.
Cf. A099390, A187596, A187616, A187617, A187618, A004003.

with(LinearAlgebra):
A:= proc(m, n) option remember; local i, j, s, t, M;
      if m=0 or n=0 then 1
    elif m1 or j>1 or s=0 then
               if j

A[1, 1] = 1; A[m_, n_] := A[m, n] = Module[{i, j, s, t, M}, Which[m == 0 || n == 0, 1, m < n, A[n, m], True, s = Mod[n*m, 2];M[i_, j_] /; j < i := -M[j, i]; M[, ] = 0; For[i = 1, i <= n, i++, For[j = 1, j <= m, j++, t = (i-1)*m+j-s; If[i > 1 || j > 1 || s == 0, If[j < m, M[t, t+1] = 1]; If[i < n, M[t, t+m] = 1-2*Mod[j, 2]]]]]; Sqrt[Det[Array[M, {n*m-s, n*m-s}]]]]]; Table[Table[A[m, d-m], {m, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 26 2013, translated from Maple *)

A187618 Triangle T(m,n) read by rows: number of domino tilings of the 2m X 2n grid (0 <= m <= n).

Original entry on oeis.org

1, 1, 2, 1, 5, 36, 1, 13, 281, 6728, 1, 34, 2245, 167089, 12988816, 1, 89, 18061, 4213133, 1031151241, 258584046368, 1, 233, 145601, 106912793, 82741005829, 65743732590821, 53060477521960000, 1, 610, 1174500, 2720246633, 6675498237130, 16848161392724969, 43242613716069407953, 112202208776036178000000

Offset: 0

N. J. A. Sloane, Mar 12 2011

A099390 is the main entry for this problem.

			Triangle begins:
1
1       2
1       5       36
1       13      281     6728
1       34      2245    167089  12988816
1       89      ...

Alois P. Heinz, Rows n = 0..14, flattened
Index entries for sequences related to dominoes

Cf. A099390, A187596, A187616, A187617.

More terms from Nathaniel Johnston, Mar 22 2011

A340532 Number of domino tilings of a 16 X n rectangle.

Original entry on oeis.org

1, 1, 1597, 29681, 9475901, 366944287, 69289288909, 3710708201969, 540061286536921, 34741645659770711, 4337452956682508609, 313196612952258199679, 35457442115448212075033, 2764079753958605286860951, 293251198441417290172509377, 24080184063411167042923575793

Offset: 0

A. M. Magomedov and Serge Lawrencenko, Jan 10 2021

nonn

Basically, for n = 1, 2, ..., 513, the terms a(n) are calculated by the double product formula in the program below, with the help of the authors' C# program using the BigInteger and BigFloat classes. (The computer calculations took 44 hours to complete.)

Alternatively, the value of a(513) is calculated by the homogeneous linear recurrence relation of order 256; the thus calculated value coincides with the one obtained by the classical double product formula. Furthermore, using the recurrence relation, the values of a(514), a(515), ..., a(10240) are also calculated. (The computer calculations took 4 minutes to complete.)

			a(1) = 1, since there is only one domino tiling of the 16 X n rectangle, which consists entirely of horizontal tiles.
a(2) = 1597 = F(17), since the number of domino tilings of the m X 2 rectangle is the Fibonacci number F(m+1).
Note that the terms a(16) and a(33) are even. More generally, for m even, the numbers of domino tilings of the m X m square and of the m X (2m+1) rectangle are even.

A. M. Magomedov, T. A. Magomedov, S. A. Lawrencenko, Mutually-recursive formulas for enumerating partitions of the rectangle (Russian, English summary), Prikl. Diskr. Mat., 46 (2019), 108-121.

Alois P. Heinz, Table of n, a(n) for n = 0..514
M. E. Fisher, Statistical mechanics of dimers on a plane lattice, Phys. Rev. 124 (1961) 1664-1672.
P. W. Kasteleyn, The statistics of dimers on a lattice, Physica 27 (1961), 1209-1225.
P. W. Kasteleyn, Dimer statistics and phase transitions, J. Math. Phys., 4 (1963), 287-293.
Viet-Ha Nguyen, Kévin Perrot, Mathieu Vallet, NP-completeness of the game Kingdomino(TM), Theoretical Computer Science (2020) Vol. 822, 23-35. See also arXiv:1909.02849, [cs.CC], 2019.

Subsequence of A099390.

Cf. A000045, A187596.

b:= proc(n, l) option remember; local k;
      if n=0 then 1
    elif min(l)>0 then (t-> b(n-t, map(h->h-t, l)))(min(l))
    else for k while l[k]>0 do od; `if`(n>1, b(n, subsop(k=2, l)), 0)+
         `if`(k b(n, [0$16]):
seq(a(n), n=0..15);  # Alois P. Heinz, Jan 12 2021

Do[
P = 1; m = 16;
Do[
  P = N[P*(4*Cos[Pi*i/(n + 1)]^2 + 4*Cos[Pi*j/(m + 1)]^2), 1020],
  {i, 1, n/2}, {j, 1, m/2}];
Print["P=", N[P, 1020], " n=", n, " m=", m],
{n, 1, 20}
]

The sequence is completely defined by the following formula, which is a special case of a classical double product formula (A099390): a(n) = Product_{j=1..8} (Product_{k=1..floor(n/2)} (4*(cos(j*Pi/17))^2 + 4*(cos(k*Pi/(n+1)))^2)). In addition, a homogeneous linear recurrence relation of order 256 with constant coefficients is obtained to generate the sequence.

a(n) = A187596(16,n) = A187596(n,16). - Alois P. Heinz, Jan 10 2021

A241908 Number of perfect matchings in graph P_{13} X P_{2n}.

Original entry on oeis.org

1, 377, 413351, 536948224, 731164253833, 1012747193318519, 1412218550274852671, 1974622635952709613247, 2764079753958605286860951, 3870940598132705729413670953, 5422065916132126528319352874496, 7595338059193606161156363370300487, 10640045682768766172108553992086690201

Offset: 0

Sergey Perepechko, May 01 2014

In Karavaev and Perepechko generating functions G_m(x) for P_m X P_n graphs were found for all values of m up to 27.

A. M. Karavaev and S. N. Perepechko, Generating functions for dimer problem on rectangular lattices (in Russian), Information Processes, 13(2013), No4, 374-400.

Sergey Perepechko, Generating function for A241908

Row 13 of array A099390.

Cf. A028470, A028471, A028472, A028473, A028474, A187596.

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

A256044 6th row of array in A099390.

Original entry on oeis.org

1, 13, 281, 6728, 167089, 4213133, 106912793, 2720246633, 69289288909, 1765722581057, 45005025662792, 1147185247901449, 29242880940226381, 745439797095329713, 19002353776441540177, 484398978524471931341, 12348080425980866090537, 314771823879840325570888

Offset: 0

N. J. A. Sloane, Mar 14 2015

Alois P. Heinz, Table of n, a(n) for n = 0..700
Index entries for linear recurrences with constant coefficients, signature (40,-416,1224,-1224,416,-40,1).

Cf. A099390.

Bisection (even part) of A028468 and 6th row of A187596. - Alois P. Heinz, Mar 16 2015

I:=[1,13,281,6728,167089,4213133,106912793]; [n le 7 select I[n] else 40*Self(n-1)-416*Self(n-2)+1224*Self(n-3)-1224*Self(n-4)+416*Self(n-5)-40*Self(n-6)+Self(n-7): n in [1..30]]; // Vincenzo Librandi, Aug 20 2018

a[n_] := Product[2(2+Cos[2j Pi/7]+Cos[2k Pi/(2n+1)]), {k, 1, n}, {j, 1, 3}] // Round;
Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Aug 20 2018 *)
LinearRecurrence[{40, -416, 1224, -1224, 416, -40, 1}, {1, 13, 281, 6728, 167089, 4213133, 106912793}, 20] (* Vincenzo Librandi, Aug 20 2018 *)

x='x+O('x^100); Vec(-(x^6-27*x^5+177*x^4-328*x^3+177*x^2-27*x+1)/((x-1)*(x^3-26*x^2+13*x-1)*(x^3-13*x^2+26*x-1))) \\ Altug Alkan, Mar 23 2016

G.f.: -(x^6 - 27*x^5 + 177*x^4 - 328*x^3 + 177*x^2 - 27*x + 1) / ((x - 1)*(x^3 - 26*x^2 + 13*x - 1)*(x^3 - 13*x^2 + 26*x - 1)). - Alois P. Heinz, Mar 16 2015

a(n) = 40*a(n-1) - 416*a(n-2) + 1224*a(n-3) - 1224*a(n-4) + 416*a(n-5) - 40*a(n-6) + a(n-7). - Vincenzo Librandi, Aug 20 2018

a(8)-a(17) from Alois P. Heinz, Mar 16 2015

cp's OEIS Frontend

A004003 Number of domino tilings (or dimer coverings) of a 2n X 2n square.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A239264 Number A(n,k) of domicule tilings of a k X n grid; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A187617 Array T(m,n) read by antidiagonals: number of domino tilings of the 2m X 2n grid (m>=0, n>=0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A187616 Triangle T(m,n) read by rows: number of domino tilings of the m X n grid (0 <= m <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A189006 Array A(m,n) read by antidiagonals: number of domino tilings of the m X n grid with upper left corner removed iff m*n is odd, (m>=0, n>=0).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A187618 Triangle T(m,n) read by rows: number of domino tilings of the 2m X 2n grid (0 <= m <= n).

Views

Author