Cubic-exponential enumerative combinatorics

Question

There are many quantities in enumerative combinatorics that grow roughly exponentially, like the Fibonacci numbers, the Catalan numbers, and the factorials; indeed, most of the functions that arise in pre-19th century combinatorics -- even ones as large as the function $n^{n-2}$, which counts spanning trees of the complete graph on $n$ vertices among other things -- in a sense grow like an ordinary exponential, inasmuch as the logarithm can be asymptotically bounded above and below by linear functions of $n$.

Over the past century enumerative combinatorialists have studied other quantities that grow faster than an ordinary exponential, associated with newer sorts of combinatorial objects, such as plane partitions, alternating sign matrices, and tilings of plane regions. In these situations one often encounters functions $f(n)$ that grow quadratic-exponentially, in the sense that $\log \log f(n)$ divided by $\log n$ converges to 2 rather than 1.

My question is, are there any exact (non-trivial) combinatorial results concerning quantities that grow like a cubic-exponential function of $n$, with $(\log \log f(n)) / (\log n)$ converging to 3 (or maybe converging to something even larger, or diverging)?

One can certainly find combinatorial problems that give rise to functions exhibiting this kind of growth, but in no cases that I am aware of (outside of trivial cases) can one actually exhibit closed formulas for these sequences, or even computationally useful recurrence relations. (If for instance a formula for $f(n)$ involves a sum of $2^n$ binomial coefficients, it's not going to enable you to compute $f(50)$, even if $f(50)$ has only a few million digits and hence is within the range of exact computer arithmetic.)

Let me stress that I'm aware that a set with $n^3$ elements has exactly $2^{n^3}$ subsets, but this is the sort of case that I intended to rule out by my use of the phrase "trivial cases".

Answer 1

Since you mentioned Cayley's theorem for spanning trees, I believe one important example is its higher dimensional analogue due to Kalai. Indeed the number of simplicial spanning trees of the k-skeleton of an n-simplex is $$f(n)=n^{\binom{n-2}{k}} \implies \lim_{n\to \infty}\frac{\log\log f(n)}{\log n}=k.$$

Some further work has been done in this direction, for example in the paper "Simplicial Matrix-Tree Theorems" by Duval, Klivans, and Martin they give a weighted enumeration formula for such higher dimensional "spanning trees".

The reason why I think this constitutes an important example for the question at hand is that in my mind I think of combinatorial enumerations of spanning trees, perfect matchings, non-intersecting paths, plane partitions, etc. as being equivalent to each other and are really enumeration problems about 1-dimensional simplicial complexes (whereas permutations for example are an enumeration question in the 0-dimensional world). With the increase of the dimension in these enumeration problems one gets an increase in the degree of the polynomial exponential growth.

Answer 2

The number of truth tables generated by boolean expressions of $n$ variables is $2^{2^n}$.

Answer 3

The number $m_n$ of matroids on $n$ elements is an interesting example, since a priori, it is unclear how fast $m_n$ grows. Knuth (1974) showed that $\log \log m_n$ is at least $n- \frac{3}{2} \log n -O(1)$. On the other hand, Piff (1973) showed that $\log \log m_n$ is at most $n-\log n + \log \log n + O(1)$. Recent work of Bansal, Pendavingh and van der Pol suggests that the true answer is closer to Knuth's lower bound.