An algorithm for counting domino tilings of a rectangular chessboard

Authors

  • Abdulkarim M. Magomedov Department of Discrete Mathematics and Informatics, Dagestan State University,and Department of Mathematics and Informatics, Dagestan Federal Research Center of the Russian Academy ofSciences, 45 M. Gadzhiev, Makhachkala, 367032, Dagestan, Russia https://orcid.org/0009-0000-6482-8585
  • Serge A. Lawrence Department of Cryptology, Faculty of Mechanics and Math-ematics, L.N. Gumilyov Eurasian National University, 2 Satbaev, Astana, 10000, Kazakhstan, and Insti-tute of Service Technologies, Russian State University of Tourism and Service, Podolsk, Russia https://orcid.org/0000-0002-5198-1633

DOI:

https://doi.org/10.13069/jacodesmath.v13i1.335

Keywords:

Domino tiling, Tiling counting, Dimer problem, Recurrence relation, Algorithm, Fibonacci numbers

Abstract

A recursive method is developed for counting domino tilings of a rectangular chessboard (the dimer problem). Based on this method, a new and enhanced recursive algorithm is proposed for solving this problem. Close connections with Fibonacci numbers are traced out.

Accepted: 23 June 2025

Downloads

Download data is not yet available.

References

J. H. Ahrens, Paving the chessboard, Journal of Combinatorial Theory, Series A. 31(3) (1981) 277–288.

S. Butler, P. Horn, E. Tressler, Intersecting domino tilings, The Fibonacci Quarterly. 48(2) (2010) 114–120.

D. DeFord, Enumerating distinct chessboard tilings, The Fibonacci Quarterly. 52(5) (2014) 102–116.

R. L. Graham, D. E. Knuth, O. Patashnik, Concrete mathematics. A foundation for computer science, 2nd edition, Addison-Wesley Publishing Company, Reading, MA. (1994).

P. W. Kasteleyn, The statistics of dimers on a lattice: I. The number of dimer arrangements on quadratic lattice, Physica. 27 (1961) 1209–1225.

D. Klarner, J. Pollack, Domino tilings of rectangles with fixed width, Discrete Mathematics. 32(1) (1980) 45–52.

L. Lovász, M. D. Plummer, Matching theory, North-Holland Math. Stud. 121, Ann. Discrete Math. 29, North-Holland, Amsterdam (1986).

A. M. Magomedov, S. Lawrencenko, Number of domino tilings of a 16 X n rectangle, The On-Line Encyclopedia of Integer Sequences, A340532 - OEIS (10 Jan. 2021).

A. M. Magomedov, S. Lawrencenko, Number of domino tilings of a 32 X n rectangle, The On-Line Encyclopedia of Integer Sequences, A347054 - OEIS (14 Aug. 2021).

J. K. Percus, Combinatorial methods, Applied Mathematical Sciences. 4, Springer-Verlag, New York-Heidelberg (1971).

R. C. Read, A note on tiling rectangles with dominoes, The Fibonacci Quarterly. 18(1) (1980) 24–27.

A. Skopenkov, Mathematics via Problems: Part 1: Algebra, translated from the Russian original by P. Zeitz and S. G. Shubin, foreword by P. Zeitz, MSRI Math. Circ. Libr. 25, MSRI, Berkeley, CA; American Mathematical Society, Providence, RI. (2021).

H. N. V. Temperley, M. E. Fisher, Dimer problem in statistical mechanics—an exact result, The Philosophical Magazine: A Journal of Theoretical Experimental and Applied Physics. 6(68) (1961) 1061–1063.

L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science. 8(2) (1979) 189–201.

Downloads

Published

2025-12-22

How to Cite

Magomedov, A. M., & Lawrence, S. A. . . (2025). An algorithm for counting domino tilings of a rectangular chessboard. Journal of Algebra Combinatorics Discrete Structures and Applications, 13(1), 15–27. https://doi.org/10.13069/jacodesmath.v13i1.335

Issue

Vol. 13 Issue 1: January 2026

Section

Articles