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

Question

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.

Answer 1

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)$.