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.