  A spanning tree of an edge-colored graph is rainbow provided that each of its
edges receives a distinct color. In this paper we consider the natural extremal
problem of maximizing and minimizing the number of rainbow spanning trees in a
graph $G$. Such a question clearly needs restrictions on the colorings to be
meaningful. For edge-colorings using $n-1$ colors and without rainbow cycles,
known in the literature as JL-colorings, there turns out to be a particularly
nice way of counting the rainbow spanning trees and we solve this problem
completely for JL-colored complete graphs $K_n$ and complete bipartite graphs
$K_{n,m}$. In both cases, we find tight upper and lower bounds; the lower bound
for $K_n$, in particular, proves to have an unexpectedly chaotic and
interesting behavior. We further investigate this question for JL-colorings of
general graphs and prove several results including characterizing graphs which
have JL-colorings achieving the lowest possible number of rainbow spanning
trees. We establish other results for general $n-1$ colorings, including
providing an analogue of Kirchoff's matrix tree theorem which yields a way of
counting rainbow spanning trees in a general graph $G$.
