Domino Tilings of 2 × n Grids (or Perfect Matchings of Grid Graphs) on Surfaces
Mathematical Staircase, Inc.
Holyoke, MA 01040
Department of Mathematical Sciences
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,
(Concerned with sequences
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.
Journal of Integer Sequences home page