×

Counting perfect matchings in polyominoes with an application to the dimer problem. (English) Zbl 0718.05018

Summary: A polyomino is a connected finite plane graph with no cut-points in which all interior regions (called cells) are unit squares. Let P be a given polyomino and e be a given edge of P. A simple algorithm is developed for calculating the numbers m(P) and m(P,e) of all perfect matchings of P and of those perfect matchings of P which contain the edge e, respectively. The numbers m(P) and m(P,e)/m(P) play an important role in the dimer problem of statistical crystal physics.

MSC:

05B50 Polyominoes
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
82D25 Statistical mechanics of crystals
PDFBibTeX XMLCite