# Exact formula for the number of spanning trees of a rectangle

This blog talks about generating "twisty little mazes" using a computer an enumerating them. The enumeration can be done using Wilson's algorithm to get the UST, 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

In principle the Matrix Tree Theorem 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?

Here is a pretty example of Wilson's algorithm in action.

• Online Encyclopedia of Integer Sequences The exact formulas don't look easy to derive. – Peter Shor Jul 11 '15 at 2:16
• @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 Jul 11 '15 at 11:06
• They cover a lot of different objects, including the quadrillage planaire, which is the $m \times n$ grid. – Peter Shor Jul 11 '15 at 11:17

## 2 Answers

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.

• 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: arxiv.org/pdf/math-ph/0011042.pdf (specifically, corollary 2 and proposition 13) – Lorenzo Najt Jul 29 '18 at 1:01
• 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 Jul 30 '18 at 7:30
• It was published in Acta Math 185 (2000) no. 2, 239-286. – Lorenzo Najt Jul 31 '18 at 16:16

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.

• 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 Jul 12 '15 at 9:14