A124997 -id:A124997 - 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

A334396 Number of fault-free tilings of a 3 X n rectangle with squares and dominoes.

Original entry on oeis.org

0, 0, 2, 2, 10, 16, 52, 104, 286, 634, 1622, 3768, 9336, 22152, 54106, 129610, 314546, 756728, 1831196, 4413952, 10667462, 25735346, 62160046, 150020016, 362257392, 874442064, 2111291570, 5096782418, 12305249242, 29706645280, 71719568260

Offset: 1

Greg Dresden and Oluwatobi Jemima Alabi, Jul 06 2020

A fault-free tiling has no horizontal or vertical faults (that is to say, the tiling does not split along any interior horizontal or vertical line).

			a(4) = 2 because these are the only fault-free tilings of the 3 X 4 rectangle with squares and dominoes:
._ _ _ _     _ _ _ _
|_ _|_| |   | |_|_ _|
| |_ _|_|   |_|_ _| |
|_|_|_ _|   |_ _|_|_|

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,4,-1,-1).

Cf. A084477, A084479, A084481, A112577, A124997, A335747.

[n le 4 select 2*Floor((n-1)/2) else Self(n-1) +4*Self(n-2) -Self(n-3) -Self(n-4): n in [1..40]]; // G. C. Greubel, Jan 15 2022

a[n_]:= (2/3)*(Fibonacci[n-1, 2] - (-1)^n*Fibonacci[n-1]);
Table[a[n], {n, 40}] (* G. C. Greubel, Jan 15 2022 *)

concat([0,0] , Vec(2*x^3/((1+x-x^2)*(1-2*x-x^2)) + O(x^30))) \\ Colin Barker, Aug 06 2020

[(2/3)*(lucas_number1(n-1,2,-1) - (-1)^n*lucas_number1(n-1,1,-1)) for n in (1..40)] # G. C. Greubel, Jan 15 2022

a(n) = a(n-1) + 4*a(n-2) - a(n-3) - a(n-4) for n >= 5.
a(n) = 2*A112577(n-2) for n >= 2.
G.f.: 2*x^3 / ((1 + x - x^2)*(1 - 2*x - x^2)). - Colin Barker, Aug 06 2020

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