Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.