For simplicity, we can assume that only NAND gates are allowed. An asymptotically correct solution is all I really need.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Hint: Each of the $s$ gates is connected to two other gates or inputs, for a total of $(s+n)^2$ possibilities. This gives a rough upper bound which isn't tight, but is good enough for many purposes, for example to show that some functions require circuits of size $\Omega(2^n/n)$. See Steurer's notes, for example.