<p>The eigenvalues of the m-by-n rectangle graph can be used to obtain an expression for the number of perfect matchings in such graphs.  See <a href="https://en.m.wikipedia.org/wiki/Domino_tiling" rel="nofollow">the Wikipedia article on domino tilings</a>.</p>

CC BY-SA 3.0
2015-07-12T09:14:57.463Z
This is interesting, but can you elaborate how this adresses the question? Is there any kind of mapping between perfect matchings and spanning trees in this particular case?
Saeed
CC BY-SA 3.0
2015-07-11T01:11:36.203Z
2015-07-11T01:11:36.203Z
Tyson Williams
<p>According to <a href="https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf">https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf</a> there is no closed-form formula known.</p>

<p>According to <a href="http://arxiv.org/pdf/cond-mat/0004341v1.pdf">http://arxiv.org/pdf/cond-mat/0004341v1.pdf</a> the number is asymptotic (for $n$ and $m$ both large) to
$$\exp (z_{\mathrm{sq}}mn)$$
where
$$z_{\mathrm{sq}}=\frac{4}{\pi}\sum_{i=0}^\infty\frac{(-1)^i}{(2i+1)^2}\approx 1.16624$$
but I'm not sure whether this is a rigorous bound or the result of heuristic physics-based reasoning. The same paper also gives asymptotic formulas of similar type when $m$ is fixed to a small constant and $n$ is large.</p>

CC BY-SA 4.0
2018-07-29T01:01:54.560Z
There are precise asymptotic formulas for the number of spanning trees in a rectangle (and more general sequences of subgraphs described by rectilinear polygons) given here: https://arxiv.org/pdf/math-ph/0011042.pdf (specifically, corollary 2 and proposition 13)
Elle Najt
CC BY-SA 4.0
2018-07-30T07:30:26.380Z
Again, that's in a mathematical physics repository. Do they prove the asymptotic formulas rigorously or do they just use physics-like ansatz reasoning?
David Eppstein
CC BY-SA 4.0
2018-07-31T16:16:51.033Z
It was published in Acta Math 185 (2000) no. 2, 239-286.
Elle Najt
CC BY-SA 3.0
2015-07-11T06:11:46.727Z
2015-07-11T06:11:46.727Z
David Eppstein
<p>This blog talks about generating "twisty little mazes" using a computer an enumerating them.  The enumeration can be done using <a href="http://bl.ocks.org/mbostock/11357811" rel="nofollow noreferrer">Wilson's algorithm</a> to get the <a href="http://bl.ocks.org/mbostock/11363008" rel="nofollow noreferrer">UST</a>, but I don't remember the formula for how many there.</p>

<p><a href="http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike" rel="nofollow noreferrer">http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike</a></p>

<p><img src="https://i.sstatic.net/XVzQ9.png" alt=""></p>

<p>In principle the <a href="http://math.mit.edu/~levine/18.312/alg-comb-lecture-19.pdf" rel="nofollow noreferrer">Matrix Tree Theorem</a> states the number of spanning trees of a graph is equal to the determinant of the Laplacian matrix of the graph.  Let <span class="math-container">$G= (E,V)$</span> be the graph and <span class="math-container">$A$</span> be the adjacency matrix, <span class="math-container">$D$</span> be the degree matrix, then <span class="math-container">$\Delta = D - A$</span> with eigenvalues <span class="math-container">$\lambda$</span>, then:</p>

<p><span class="math-container">$$ k(G) = \frac{1}{n} \prod_{k=1}^{n-1} \lambda_k $$</span></p>

<p>In the case of an <span class="math-container">$m \times n$</span> rectangle both <span class="math-container">$A$</span> and the eigenvalues should take a particularly simple form, which I can't find.  </p>

<p><strong>What is the exact formula (and asymptotics) for the # of spanning trees of an <span class="math-container">$m \times n$</span> rectangle?</strong></p>

<p><img src="https://i.sstatic.net/DhoRB.png" alt="enter image description here"></p>

<p><a href="http://bl.ocks.org/mbostock/c03ee31334ee89abad83" rel="nofollow noreferrer">Here</a> is a pretty example of Wilson's algorithm in action.</p>

CC BY-SA 3.0
2015-07-11T02:16:36.367Z
[Online Encyclopedia of Integer Sequences](http://oeis.org/A116469) The exact formulas don't look easy to derive.
Peter Shor 
CC BY-SA 3.0
2015-07-11T11:06:16.753Z
@PeterShor OEIS cites: Germain Kreweras, *Complexite et circuits Euleriens dans les sommes tensorielles de graphes*, J. Combin. Theory, B 24 (1978), 202-212.  He is the same objects as us right?
john mangual
CC BY-SA 3.0
2015-07-11T11:17:37.353Z
They cover a lot of different objects, including the *quadrillage planaire*, which is the $m \times n$ grid.
Peter Shor 
<graph-theory><randomized-algorithms><matrices><tree>
Exact formula for the number of spanning trees of a rectangle
john mangual
# Exact formula for the number of spanning trees of a rectangle

(Asked by: username_0 on 2015-07-10)

This blog talks about generating "twisty little mazes" using a computer an enumerating them. The enumeration can be done using [Wilson's algorithm](http://bl.ocks.org/mbostock/11357811) to get the [UST](http://bl.ocks.org/mbostock/11363008), but I don't remember the formula for how many there.

<http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike>

![](https://i.sstatic.net/XVzQ9.png)

In principle the [Matrix Tree Theorem](http://math.mit.edu/~levine/18.312/alg-comb-lecture-19.pdf) states the number of spanning trees of a graph is equal to the determinant of the Laplacian matrix of the graph. Let $G= (E,V)$ be the graph and $A$ be the adjacency matrix, $D$ be the degree matrix, then $\Delta = D - A$ with eigenvalues $\lambda$, then:

$$ k(G) = \frac{1}{n} \prod\_{k=1}^{n-1} \lambda\_k $$

In the case of an $m \times n$ rectangle both $A$ and the eigenvalues should take a particularly simple form, which I can't find.

**What is the exact formula (and asymptotics) for the # of spanning trees of an $m \times n$ rectangle?**

![enter image description here](https://i.sstatic.net/DhoRB.png)

[Here](http://bl.ocks.org/mbostock/c03ee31334ee89abad83) is a pretty example of Wilson's algorithm in action.

**Tags:** graph-theory, randomized-algorithms, matrices, tree
> **Comments:**
> **username_1**: [Online Encyclopedia of Integer Sequences](http://oeis.org/A116469) The exact formulas don't look easy to derive.  
> **username_0**: @PeterShor OEIS cites: Germain Kreweras, *Complexite et circuits Euleriens dans les sommes tensorielles de graphes*, J. Combin. Theory, B 24 (1978), 202-212.  He is the same objects as us right?  
> **username_1**: They cover a lot of different objects, including the *quadrillage planaire*, which is the $m \times n$ grid.  

---

## 2 answers

### Answer by username_4 on 2015-07-11. Score: 9 | Accepted answer

According to <https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf> there is no closed-form formula known.

According to <http://arxiv.org/pdf/cond-mat/0004341v1.pdf> the number is asymptotic (for $n$ and $m$ both large) to
$$\exp (z\_{\mathrm{sq}}mn)$$
where
$$z\_{\mathrm{sq}}=\frac{4}{\pi}\sum\_{i=0}^\infty\frac{(-1)^i}{(2i+1)^2}\approx 1.16624$$
but I'm not sure whether this is a rigorous bound or the result of heuristic physics-based reasoning. The same paper also gives asymptotic formulas of similar type when $m$ is fixed to a small constant and $n$ is large.

> **Comments:**
> **username_5**: There are precise asymptotic formulas for the number of spanning trees in a rectangle (and more general sequences of subgraphs described by rectilinear polygons) given here: https://arxiv.org/pdf/math-ph/0011042.pdf (specifically, corollary 2 and proposition 13)  
> **username_4**: Again, that's in a mathematical physics repository. Do they prove the asymptotic formulas rigorously or do they just use physics-like ansatz reasoning?  
> **username_5**: It was published in Acta Math 185 (2000) no. 2, 239-286.  

---

### Answer by username_2 on 2015-07-11. Score: 0

The eigenvalues of the m-by-n rectangle graph can be used to obtain an expression for the number of perfect matchings in such graphs. See [the Wikipedia article on domino tilings](https://en.m.wikipedia.org/wiki/Domino_tiling).

> **Comments:**
> **username_3**: This is interesting, but can you elaborate how this adresses the question? Is there any kind of mapping between perfect matchings and spanning trees in this particular case?  

---

