discrete geometry - Number of spanning trees in a grid

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 xpi - cos ypi) : 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)$.