The Number of Monomer-Dimer Tilings of an m by n Rectangle with a Fixed Proportion of Monomers

Manuel KAUERS, Gleb POGUDIN and Doron ZEILBERGER

Abstract: We use symbolic and numeric computations to study the asymptotic behavior of the number of monomer-dimer tilings of a strip of fixed width with a fixed proportion of monomers, and study the “entropy” as a function of the propotion, and try to extrapolate the date to the whole plane (for a strip of width infinity). Introduction The problem of enumerating dimer tilings is one of the most celebrated problems in both combinatorics and statistical physics, that was solved completely by Kasteleyan and Temperly & Fisher ([K][FT]). The corresponding problem for the monomer-dimer problem is wide open, and is believed to be intractable. Nevetheless, it is possible to say something about it. In this article we will study the following problem. Fix a rational number k = a/b, between 0 and 1, and a positive integer m, how many ways can you tile an m by 2nb using dimers (dominoes, i.e. 2 × 1 and 1 × 2 tiles) and monomers (1 × 1 tiles), with exactly 2nbm · k = nma dimers? Let’s call that number T_{k,m}(2nb) We are mainly interested in the entropy

λ_{2,m}(k) := lim_{n→∞} \frac{log T_{k,m}(2nb)}{2mnb} .

We will compute if for many rational numbers k, and for m ≤ 8, and look at the trend, and try to estimate the limiting function λ_{2,∞}(k) = λ_{2}(k).

Supporting Maple Package and Output All the results in this article were obtained by the use of the Maple packages

• http://www.math.rutgers.edu/~zeilberg/tokhniot/BDD.txt ,

whose output files, along with links to diagrams, are available from the front of this article

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/bdd.html .

Acknowledgment We wish thank Manuel Kauers for helpful discussions, and for introducing the authors to each other. References [FT] M. Fisher and H. Temperley, Dimer Problems in Statistical Mechanics-an exact result, Philos. Mag. 6 (1961), 1061-1063.

[K] P. W. Kasteleyn, The statistics of dimers on a lattice: I. The number of dimer arrangements in a quadratic lattice, Physica 27 (1961), 1209-1225.

[J] Mark Jerrum, Two-dimensional monomer-dimer systems are computationally intractable, Journal of Statistical Physics, 48 121134.

Manuel Kauers, Institute of Algebra, Johannes Kepler University, Email: mkauers@kauers.de .

Gleb Pogudin, Institute of Algebra, Johannes Kepler University, Email: pogudin.gleb@gmail.com .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .