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)$?
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
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. 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).
You can (write a program to) form the graph Laplacian (for n reasonably small) and use the matrix-tree theorem to get the number of spanning trees. See
http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem
The triangular grid is a bit trickier to handle both on paper or on a computer; you may find techniques for the graded lexicographic index described at
http://blog.eqnets.com/2009/10/06/a-graded-lexicographic-index-part-1/
and subsequent posts helpful in dealing with the triangular lattice.
EDIT: The answer is at http://www.oeis.org/A007341.
Expanding on Steve Huntsman's answer, call the product which appears in A007341 f(n). That is,
$$f(n) = \prod_{k=0}^{n-1} {\prod_{l=0}^{n-1}}^\prime \left(2 - \cos {\pi k \over n} - \cos {\pi l \over n } \right)$$
where the $\prime$ on the second product indicates that we start at $l=1$ in the case $k = 0$. The number of interest here is $a(n) = 2^{n^2-1} f(n)/n^2$ .
The product is the exponential of a sum, so
$$\log f(n) = \sum_{k=0}^{n-1} {\sum_{l=0}^{n-1}}^\prime \log \left(2 - \cos {\pi k \over n} - \cos {\pi l \over n } \right).$$
This sum is, in turn, $n^2$ times a Riemann sum for the integral
$$ C = \int_0^1 \int_0^1 \log(2-\cos x\pi - \cos y\pi) \: dx \: dy $$
which I believe converges, although actually evaluating it numerically is tricky. If you believe that, then $\log f(n) \sim Cn^2$ as $n \to \infty$, and $\log a(n) \sim (C+\log 2) n^2$ as $n \to \infty$. From evaluating $f(n)$ for various $n$, it appears that $C$ is near $0.473$, $e^C$ is near $1.605$ and so we have
$$ a(n) \approx 3.21^{n^2} $$
where I write $p(n) \approx q(n)$ for $\log p(n)/\log q(n) \to 1 $ as $n \to \infty$, i. e. $\log p(n) \sim \log q(n)$.
You might try looking at:
