3
$\begingroup$

The number of ways to fully-cover a m -by- n rectangle with mn/2 dominoes is: $\prod_{j=1}^m \prod_{k=1}^n \left ( 4\cos^2 \frac{\pi j}{m + 1} + 4\cos^2 \frac{\pi k}{n + 1} \right )^{1/4}.$

Is there any more general result of the number of ways to fully-cover any fully-coverable Polyomino by dominoes

  • 0
    @FiniteA, http://oeis.org/A004003 says, "$a(n)$ is the number of different ways to cover a $2n\times2n$ lattice with $2n^2$ dominoes. John and Sachs show that $a(n)=2^nB(n)^2$, where $B(n)\equiv n+1\pmod{32}$ when $n$ is even and $B(n)\equiv(-1)^{(n-1)/2}n\pmod{32}$ when $n$ is odd." The full table is at http://oeis.org/A099390, where you might get some idea of the growth rate, and where there are references.2012-04-21

2 Answers 2

2

Considering how many parameters you would need to specify a general polyomino, I can't imagine there being any useful, fully-general result. Here's a special result, quoted from http://en.wikipedia.org/wiki/Aztec_diamond: "The Aztec diamond theorem (Noam Elkies, Greg Kuperberg and Michael Larsen et al. 1992) states that the number of domino tilings of the Aztec diamond of order $n$ is $2^{n(n+1)/2}$." Full bibliographic details are given.

I'd suggest typing $\rm domino\ tiling*$ into a search engine to see what comes up.

4

The number of ways to fully-cover a $m$-by-$n$ rectangle with $mn/2$ dominoes was solved by Kasteleyn and as well as Temperley and Fisher, both in 1961. This problem is equivalent to counting the number of perfect matchings in the $m$-by-$n$ grid graph.

In 1967, Kasteleyn generalized this result to planar graphs. However, instead of a closed form, the number of perfect matchings is computable in polynomial time. The algorithm is called the FKT algorithm in their honor of all three researchers. He published this algorithm in the chapter titled "Graph theory and crystal physics" of the book Graph Theory and Theoretical Physics.

In 1988, Vijay Vazirani generalized the FKT algorithm to graphs which do not contain a subgraph homeomorphic to $K_{3,3}$, the complete bipartite graph with 3 vertices in each partition.