An algorithm for counting domino tilings  of a rectangular chessboard

Abdulkarim M. Magomedov; Serge A.   Lawrence

doi:10.13069/jacodesmath.v13i1.335

Abdulkarim M. Magomedov Dagestan State University
Serge A. Lawrence Russian State University of Tourism and Service

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.