By "a triangulation of $X$", I mean a simplicial complex whose geometric realization is homeomorphic to $X$. Tutte showed that the number of combinatorially distinct triangulations $t(n)$ of the $2$-dimensional sphere on $n+3$ vertices is asymptotically given by
$$t(n) \approx \frac{1}{16} \sqrt{\frac{3}{2 \pi}}n^{-5/2} \left( \frac{256}{27} \right)^n.$$
What is known about the number of combinatorially distinct triangulations $t(n,g)$ of the genus $g$ surface?
(1) It seems likely to me that for fixed $g$, the growth is still roughly exponential, and maybe even
$$ t(n,g) = \exp \left( c_1 n + c_2 \log n + c_3 + o(1) \right)$$ for some constants $c_1, c_2, c_3 \in \mathbb{R}$ which only depend on $g$. For example in the case $g=0$, Tutte's result gives that $c_1 = 256 / 27$, $c_2= -5 / 2$, and $c_3 = \log \left( \frac{1}{16} \sqrt{\frac{3}{2 \pi}} \right)$. Is the growth of $T(n,g)$ always exponential in $n$, and if so can we at least compute the base of the exponent $c_1$ for higher $g$?
Updated: The rooted version of this question is answered in the paper: Z.-C. Gao. The number of rooted triangular maps on a surface. Journal of Combinatorial Theory, Series B, 52(2):236 – 249, 1991. For fixed genus $g$, Gao establishes strong results along the lines of the above.
(2) At the other extreme, is anything known about the rate of growth of $t(n,g)$ as $n \to \infty$ if $g \approx cn^2$ for some constant $0 < c< 1/12$?
(3) Finally, let $T(n)$ be the total number of combinatorial types of triangulated surfaces on $n$ vertices. What is the rate of growth of $T(n)$ as $n \to \infty$?
Updated: What I would really like to know is if we can not establish the rate of growth of $T(n)$, is there at least an upper bound of order $$T(n) = n^{o(n)}?$$
Or let $\tilde{T}(n)$ denote the number of labelled triangulated surfaces on $n$ vertices. Is it true that
$$\tilde{T}(n) = n^{n+o(n)}?$$
Since $\tilde{T}(n) \le n! T(n)$, the second inequality would follow from the first.
Gao's results give that if we assume that the genus $g$ is bounded, then we get the stronger bound
$$T(n) = n^{O(n /\log n),}$$
but I still don't know how to handle $g$ growing with $n$.
Best Answer
I don't think a nice asymptotic formula like the one you've mentioned from Tutte's work is available for higher $g$ to the best of my understanding; it is entirely possible that someone who regularly deals with such things will come along and show us otherwise.
Meanwhile, the state-of-the-art on counting triangulations of genus $g$ surfaces is the lovely paper "The KP hierarchy, branched covers, and triangulations" of Goulden and Jackson, available here: see Theorem 5.4. There are two obstacles in terms of going from this Theorem to a Tutte-type asymptotic formula:
I think 1. is surmountable, but 2. might make things difficult: I have no idea how fast $f(n,g)$ grows, but I am sure various simplifications are possible if you set $g = cn$ in their formula.