# 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

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.