Tutte's formula (circa 1963) for the number of rooted planar maps with $n$ edges: $$\#M_n = \frac{2}{n+3}3^nC_n$$ where $C_n = \frac{1}{n+1}\binom{2n}{n}$ is the $n$th Catalan number. This is a surprisingly simple formula. Moreover, this formula is the beginning of an important story about universal $2$-dimensional random structures because the limit of the uniform random planar map is the so-called "Brownian map" which has seen a lot of attention in the last ~10 years. As such it is related to topics like quantum gravity. Note, however, that Tutte used generating function techniques to prove the above formula whereas the scaling limit phenomena are based off bijective techniques that came later (80s-90s).
See these notes for some more details: http://arxiv.org/abs/1101.4856.
Tutte's theory of counting planar maps and triangulations is a true festival of formulas. Here is the original formula (given above in a slightly different form) of Tutte for rooted planar maps and another one from the paper A new branch of enumerative graph theory
Answer by Sam Hopkins
