Facts about spanning trees

Yes! As a child I became lost in a hedge maze. When finally found, my father explained the left (or right) hand rule. After this, I found that I liked mazes quite a bit. I do not know what exists in the literature about mazes, or even if my terminology is correct, but if a labyrinth means a rectangular maze where any two 'squares' are connect by exactly one 'path', then my question is:
How many mazes are there for an m x n rectangle?

Noam Elkies, however, gave the following reply:

Remarkably this has a nontrivial closed-form answer. In general the number of spanning trees of a graph is the determinant of the matrix D-A where D is the diagonal matrix of degrees of the graph and A is the adjacency matrix. Well, not quite -- that matrix has determinant zero (the all-ones vector is in the nullspace), so omit the first row and column. For the graph in question the eigenfunctions of D-A, and thus also the eigenvectors, can be written explicitly as trigonometric functions; the product of all the nonzero eigenvectors divided by m*n then gives the answer.

...but (i) of course it's eigenvalues one must multiply, not eigenvectors, and (ii) I neglected to actually give the eigenvalues to be multiplied. Barring silly computational errors, these eigenvalues are

4 * [ sin^2(a pi / 2 m) + sin^2(b pi / 2 n) ]

where a,b are nonnegative integers, not both zero, and less than m,n respectively.

A few further notes about these numbers: if (say) m is given then the number of spanning trees as a function of n satisfies a constant linear recurrence; for instance if m=2 the counts are 1, 4, 15, 56, 209, 780, 2911, 10864, 40545, 151316, ... satisfying c(n) = 4 c(n-1) - c(n-2). Finally, the number of *square* mazes is itself a square up to small factors; for instance there are

2^34 3^2 5^3 11^4 19^4 41^2 59^2 101^2 181^2 281^2

square mazes of order 10.

ObPuzzles:

1. What exactly is the "small factor" as a function of n?
2. Why do these huge numbers factor into such small primes?
3. We have not accounted for symmetries: mazes related by reflection or (in the square case) rotations are regarded as distinct. What are the counts if we identify such mazes; equivelntly, for each symmetry of the square or rectangle how many mazes have that symmetry?

I am not a real mathematician. I would be interested to see a reference to what you wrote. Do you think it is related to the method I use? Did you ever look into spanning trees with the additional restriction that each vertex has either degree 1 or 3?

Yes -- it's the same determinant formula, except that here the eigenfunctions and associated eigenvalues can be written explicitly. (The eigenfunctions are f(a,b)=g(a)*h(b) where g,h are eigenfunctions of the D-A matrix for a path of length m,n respectively; the eigenvalue of f is the sum of those for g and h, whence the formula I posted in a subsequent message.) I'm not very good at keeping track of references for such things, though I think Knuth wrote something along these lines some years ago. I don't know if there's a good way to enumerate spanning trees of odd degree, except when the graph has an odd number of vertices in which case a parity argument makes such a tree impossible. If you post a query to sci.math.research you'll likely get a more definitive answer to both questions.