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-alikehttp://strangelyconsistent.org/blog/images/four-random-mazes.pngIn 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.
Exact formula for the number of spanning trees of a rectangle
graph theory;randomized algorithms;matrices;tree
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.