The following statement is found on the page 199 of Nielsen and Chuang's book (10th Anniversary Edition) in the proof for the fact that 'approximating arbitrary unitary gates is generically hard':
Suppose we have $g$ different types of gates available, and each gate works on at most $f$ input qubits. These numbers, $f$ and $g$, are fixed by the computing hardware we have available, and may be considered to be constants. Suppose we have a quantum circuit containing m gates, starting from the computational basis state $|0⟩^{\bigotimes n}$. For any particular gate in the circuit there are therefore at most$\binom{n}{f}^g=O(n^{fg})$ possible choices.
I kind of think the number of possible choices for any particular gate is more in line with $\binom{n}{f}\cdot g=O(n^fg)$. What do you think?