# Prove that the number of circuits with bounded fan-in (of 2) of size $s$ is at most $s^{O(s)}$

Prove that the number of circuits with bounded fan-in (of 2) of size $$s$$ is at most $$s^{O(s)}$$.
Give the best explicit bound you can get.

I know that for a circuit of size $$s$$ in order to generate a string to represent it I need for every edge, which I have at most $$s$$ of those, to represent from which vertex it start and in which vertex it ends and for that I need $$2s \log s$$ bits. In addition I need another 2 bit for every vertex to mark whether it is an input, an OR/AND/NOT Gate. So overall I need $$O(s \log s)$$ bits to represent a circuit, and there are $$2^{O(s \log s)} = s^{O(s)}$$ circuits like that.

Am I in the right direction or am I missing something? And is $$2^{3(s \log s)} = 8s^{O(s)}$$ the bound?

• I wasn't sure if I was correct so that is why I posted this question. The only part I'm not sure about is how can I identify each input node, because saving also the indices of every one of them is another $slogs$, or maybe the information I stored so far is enough?
• The simplest solution is to have the first $n$ vertices contain the $n$ inputs. Oct 26 '20 at 17:06