Counting circuits with constraints Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one).
In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be computed only using circuits of size $\Omega(2^n/n)$, we use a counting argument: there are at most $O(2^{k \log k})$ circuits of size $k$, and $2^{2^n}$ such functions.
Suppose that I am interested in counting circuits of size $k$ that compute different functions. The &quot;simple&quot; counting argument won't work since it may be possible that two &quot;syntactically&quot; different circuits actually compute the same function.
In other words, I want to bound the size of the set: $$F =  \{ f: \{0,1\}^n \rightarrow \{0,1\} | f \text{ can be computed using a circuit of size }k \} $$
Then $|F| &lt; $ the number of circuits of size $k$ (since any circuit computes one function), but how can I bound $|F|$ from below? (i.e. $ x &lt;|F|$)
In order to bound the number of functions computed by circuits of size $k$, you have at least two options:

Construct a large number of circuits of size $k$, which by construction compute different functions.
Consider a natural probability distribution on circuits of size $k$, and estimate the probability that two random circuits compute the same function.

As an example, it is known that every function on $m$ variables can be computed by a circuit of size $O(2^m/m)$. By considering functions of the form $f_1(x_1,\ldots,x_m) \lor \cdots \lor f_{n/m}(x_{n-m+1},\ldots,x_n)$, this shows that there are at least $(2^{2^m})^{n/m}$ different functions computed by circuits of size $k = O(n2^m/m^2)$. In terms of $k$, the number of functions is roughly exponential in $k\log k$, for $m \gg \log n$.