Q: Consider a digital circuit that reads an n-bit input string and writes a 1bit output. Two circuits are considered different if they have a different output for some input string, otherwise they are considered the same (i.e. two circuits are considered the same if they have the same output bit for every possible input string). Count the number of different circuits.
