Journal of Integer Sequences, Vol. 26 (2023), Article 23.5.6

Domino Tilings of 2 × n Grids (or Perfect Matchings of Grid Graphs) on Surfaces

sarah-marie belcastro
Mathematical Staircase, Inc.
Holyoke, MA 01040
Department of Mathematical Sciences
Smith College
Northampton, MA 01063


It is well known that the number of edge-labeled perfect matchings of a 2 × n planar grid graph is the (n + 1)st Fibonacci number. The number of edge-labeled perfect matchings of grid graphs on surfaces has been computed using Pfaffians, matching polynomials, and generating functions. Here we present an elegant and elementary approach to enumerating edge-labeled perfect matchings of n grid graphs on surfaces representable by opposite-edge-identified quadrilaterals. For simplicity in description, we give proofs using the language of tilings of grids.

Full version:  pdf,    dvi,    ps,    latex,     Mathematica notebook

(Concerned with sequences A000032 A000045 A000129 A000204 A000211 A001835 A003499 A005248 A020878 A048788 A052530 A068397 A079935 A103997 A162483 A162484 A162485 A351635.)

Received July 17 2009; revised versions received February 16 2022; February 7 2023; April 11 2023. Published in Journal of Integer Sequences, June 7 2023.

Return to Journal of Integer Sequences home page