Number of possible circuits with N NOR gates and M inputs I have a circuit enumeration question related to my research. My combinatorics knowledge is lacking, so any help would be appreciated.
Given N 2-input, 1-output NOR gates (x1, x2, ..., xn) and M circuit inputs (y1, y2, ..., ym), how many possible circuit wirings can be generated using some or all of the inputs and some or all of the gates (including feedback)? Each of the NOR gates' inputs may be connected to one of the M circuit inputs or alternatively connected to a NOR gate's output (including its own).
Functionally and structurally redundant circuits are allowed. I'm just interested in an upper-bound figure for the number of possible circuits. Much thanks!
 A: Although weak upper bounds can be readily had, I would like to consider an arrangement that
provides a better upper bound when more of the architecture is known.  Since it helps cut down
on the numbers, I will assume that the n-many gates are identical, have two inputs each, and are
symmetric, so that x GATE y and y GATE x give the same results.  This analysis can easily extend to
gates with more inputs that are not symmetric.  Knowing something of the feedback portion will be crucial to
refining the estimate. 
Let us start with the purely combinatorial portion.  All the gates in this portion take their inputs
from the m provided inputs.  As an input can be repeated, there can be up to m^2 different possible
basic functions represented by a 2 input gate on the m inputs.  Because of symmetry and the fact that
the same input line can be repeated, there are M = (m+1) choose 2 different possible outputs.
If order is important, then C such gates can be painted with the M colors in M^C different ways.
However, we can get a tighter bound on the number of functionally distinct circuits by ordering
the M colors and arranging the gates in color order.  If I got it right, this results in CC= (M+C+1) choose (M+1)
distinct circuits.
Now of the remaining number (N-C) of gates, let us assume F of them have their outputs involved
in feedback mechanisms.  Thus there are I=(m+C+F) many possibilities for inputs to these F many
gates.  Order is important here, as the F gates are interwired, so I will settle for a weak bound of
FF= ((I+1) choose 2)^F possibly distinct subcircuits.  There may be a way to show that enough
redundancy exists that the actual number of distinct subcircuits is more like FF/(F!), but a
professional graph theorist should be consulted for this part.
Finally the rest of the N gates, say R, draw from the J = (m +C +F) signals available, but since these are
not combinatorial circuits, one has something like K= (J+1) choose 2 - (m+1) choose 2 possibilities, and
this is just like the combinatorial case before, as we can eliminate redundancy and orient the outputs
as we please, so we actually have RR= (R+K+1) choose (K+1) possibilities.
So, for a given triple (C,F,R) of nonnegative integers summing to N, there is an upper bound of
CC*FF*RR circuits for that triple, with a final upper bound being a sum over all such triples of that
number of circuits.  
Gerhard "Ask Me About Programmable Logic" Paseman, 2013.01.31
