# How many functions require precisely $n^2$ gates?

I'm trying to determine an asymptotic bound on the cardinality of the following set of functions. It is the functions with $$n$$-bit inputs, $$\{0,1\}$$ output, and requires precisely $$n^2$$ NAND gates. I'm trying to show that this is $$2^{o(n^3)}$$.

I've thought about just counting all functions but that's too big, $$2^{2^n}$$. I've thought about all ways to wire up $$n^2$$ gates and the best bound that I can think of is to reason that each NAND has two wires in and one out. So each gate entails $$\binom{n^2+n}{3}$$ choices of wires in and out, by a rough over-count. Then you make a choice for each gate so that's $$\binom{n^2+n}{3}^{n^2+n}$$ by another rough over-count. But I believe this grows faster than $$n!$$ which is worse than $$2^n$$.

But any time I try to determine a more precise count of this set I just can't see the things I should count. When I think about writing a recurrence relation, that seems hopeless to write, let alone solve.

Note that $$\binom{n^2+n}{3}^{n^2+n} = O(n^2)^{O(n^2)} = 2^{O(n^2\log n)} = 2^{o(n^3)}.$$ In fact, using this kind of calculation you can show that most $$n$$-bit functions require circuits of length $$\Omega(2^n/n)$$.