State matrix recursion method and monomer–dimer problem

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


The exact enumeration of pure dimer coverings on the square lattice was obtained by Kasteleyn, Temperley and Fisher in 1961. In this paper, we consider the monomer–dimer covering problem (allowing multiple monomers) which is an outstanding unsolved problem in lattice statistics. We have developed the state matrix recursion method that allows us to compute the number of monomer–dimer coverings and to know the partition function with monomer and dimer activities. This method proceeds with a recurrence relation of so-called state matrices of large size. The enumeration problem of pure dimer coverings and dimer coverings with single boundary monomer is revisited in partition function forms. We also provide the number of dimer coverings with multiple vacant sites. The related Hosoya index and the asymptotic behavior of its growth rate are considered. Lastly, we apply this method to the enumeration study of domino tilings of Aztec diamonds and more generalized regions, so-called Aztec octagons and multi-deficient Aztec octagons.

Original languageEnglish
Pages (from-to)1434-1445
Number of pages12
JournalDiscrete Mathematics
Issue number5
Publication statusPublished - 2019 May

Bibliographical note

Funding Information:
This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (No. NRF-2017R1A2B2007216).

Publisher Copyright:
© 2019 Elsevier B.V.


  • Aztec diamond
  • Dimer
  • Domino tiling
  • Hosoya index

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'State matrix recursion method and monomer–dimer problem'. Together they form a unique fingerprint.

Cite this