Given a $\sqrt{n}\times\sqrt{n}$ piece of the integer $\mathbb{Z}^2$ grid, define a graph by joining any two of these points at unit distance apart. How many spanning trees does this graph have (asymptotically as $n\to\infty$)?


Can you also say something about the triangular grid generated by $(1,0)$ and $(1/2,\sqrt{3}/2)$?



Number of spanning trees in a grid
I think the best way to deal with grids is to find the general eigenfunction of the infinite grid, and then apply appropriate boundary conditions. This is an idea of Kenyon, Propp and Wilson, you can find an outline in the very last section of my Diplomarbeit [link text](http://www.mat.univie.ac.at/~kratt/theses/rubey.ps.gz)


They only do it for the square grid, as far as I remember, but I wouldn't be surprised if the very same Ansatz works with the triangular grid.


I think that Richard Kenyon
also shows how to compute the asymptotics in "Long-range properties of spanning trees in Z^2" (you can find it on his homepage) but I didn't check.


A second trick that might be useful for the triangular grid (due to Knuth), is to observe that the dual of the grid is "almost" regular. You can choose to delete the vertex corresponding to the outer face in the Laplacian when applying the matrix tree theorem, and will get a very nice matrix, I suppose.


**update:**


I just found a reference which proves the asymptotics for the triangular grid:
[On the entropy of spanning trees on a large triangular lattice](http://arxiv.org/abs/cond-mat/0309198). The formulas are gorgeous...


I should have remarked that the given reference contains (exact) expressions for the asymptotics of both lattices: the limit of $1/n \ln \tau(G\_n)$, where $\tau(G\_n)$ is the number of spanning trees of the graph with $n$ vertices, is


$$4/\pi\sum\_{n\geq1} \sin(n\pi/2)/n^2 = 1.166 243 616\dots$$


for the square grid (due to Temperly 1972), and 


$$5/\pi\sum\_{n\geq1} \sin(n\pi/3)/n^2 = 1.615 329 736 097\dots$$


for the triangular grid (proved in the reference).


