# Counting number of sets with the given restriction.

I want to count the number of sets (empty/non-empty) formed with n natural numbers if it is given some pairs of numbers can't occur together in a set. What is the fastest way to do this if I am considering large n upto 1000 . I want a quick algo for a computer program.

-
Is it possible that some of the pairs might share elements? For example, could the set of given pairs include both $\langle1,2\rangle$ and $\langle2,3\rangle$, so that 2 can't share a set with either 1 or 3, but 1 and 3 can be in the same set? – MJD Feb 10 '13 at 21:46

The total number of subsets is $2^n$. The number of bad subsets, where specific numbers $a$ and $b$ both occur, is $2^{n-2}$. This is because the bad subsets are the sets made up of $a$, $b$, and any subset of the rest of the numbers.
Thus the number of good subsets is $2^n-2^{n-2}$.