TOPICS
Search

Domino Tiling

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
FibonacciChecker3
FibonacciChecker4
FibonacciChecker5

The Fibonacci number F_(n+1) gives the number of ways for 2×1 dominoes to cover a 2×n checkerboard, as illustrated in the diagrams above (Dickau).

DominoTilings

The numbers of domino tilings, also known as dimer coverings, of a 2n×2n square for n=1, 2, ... are given by 2, 36, 6728, 12988816, ... (OEIS A004003). The 36 tilings on the 4×4 square are illustrated above. A formula for these numbers is given by

A_n=2^(2n^2)product_(i=1)^nproduct_(j=1)^n[cos^2((ipi)/(2n+1))+cos^2((jpi)/(2n+1))].
(1)

Writing

B_n^2=2^(-n)A_n,
(2)

gives the surprising result

A_n (mod 32)={n+1 (mod 32) for n even; (-1)^((n-1)/2)n (mod 32) for n odd
(3)

(John and Sachs 2000). For n=1, 2, ..., the first few terms are 1, 3, 29, 5, 5, 7, 25, 9, 9, 11, 21, ... (OEIS A143234).

Writing

B=lim_(n->infty)(lnA_n)/((2n)^2)
(4)
=1/(16pi^2)int_(-pi)^piint_(-pi)^piln[4+2costheta+2cosphi]dthetadphi
(5)
=K/pi
(6)
=0.291560904...
(7)

(OEIS A143233; Finch 2003, p. 407), where K is Catalan's constant and B is termed the dimer constant in OEIS A143233.

However, Finch (2003, p. 232) uses the term "dimer constant" to refer to the related constant

delta=e^(2B)
(8)
=e^(2K/pi)
(9)
=1.791622812...
(10)

(OEIS A130834).

See also

Domino, Fibonacci Number

Explore with Wolfram|Alpha

References

Cohn, H. "2-adic Behavior of Numbers of Domino Tilings." Elec. J. Combin. 6, No. 1, R14, 1-7, 1999. https://doi.org/10.37236/1446.Dickau, R. M. "Fibonacci Numbers." https://www.robertdickau.com/fibboard.html.Finch, S. R. "Monomer-Dimer Constants." §5.23 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 406-407, 2003.Fisher, M. E. "Statistical Mechanics of Dimers on a Plane Lattice." Phys. Rev. 124, 1664-1672, 1961.Jockusch, W. "Perfect Matchings and Perfect Squares." J. Combin. Theory Ser. A 67, 100-115, 1994.John, P. E. and Sachs, H. "On a Strange Observation in the Theory of the Dimer Problem." Disc. Math. 216, 211-219, 2000.Propp, J. "A Reciprocity Theorem for Domino Tilings." Elec. J. Combin. 8, No. 1, R18, 1-9, 2001. https://doi.org/10.37236/1562.Schroeppel, R. Item 111 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 48, Feb. 1972. https://www.inwap.com/pdp10/hbaker/hakmem/polyominos.html#item111.Sloane, N. J. A. Sequence A004003/M2160, A130834, A143233, and A143234 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Domino Tiling

Cite this as:

Weisstein, Eric W. "Domino Tiling." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DominoTiling.html

Subject classifications