# 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
add comment

## 1 Answer

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}$.

Edit In a comment, it is asked how one can count if several pairs are to be not allowed. One can do it by using the above method, and Inclusion/Exclusion, if the number of not allowed pairs is quite small. That quickly gets out of control if a medium-sized set of pairs is to be excluded.

-
Nicolas: I forgot to specify that there can be many pairs like that. for example (1,2) (2,3) (4,5) must not occur together in any set if numbers can be chosen from 1-5 inclusive for making a set. –  kavish Feb 10 '13 at 21:35
add comment