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.

If a set $S$ has $n$ elements, how many such pairs $(A,B)$ can be formed where $A$ and $B$ are subsets of $S$ and $A \cap B = \emptyset$?

share|improve this question

4 Answers 4

There are (3n - 2n+1 + 1) / 2 such pairs of non-empty subsets.

We either put an element in A, in B or in the None bag. There are 3n possibilities to do that, but they include the cases where A or B is empty, the number of these cases has to be substracted from the result.

There are 2n cases where all of the elements were put in B and the None bag and A is empty, and similarly 2n cases where B is empty. Those 2 * 2n = 2n+1 cases has to be substracted from the result. There is one case though where everything went to None, that one case got substracted twice, so we only have to substract 2n+1 - 1.

Now we are at 3n - 2n+1 + 1 and have all possible pairs included twice as (x, y) and (y, x), so dividing by two gives the final result.

share|improve this answer

Number of different pairs of non-empty disjoint subsets of a set with n elements is:
(3n - 2n + 1 + 1) / 2.

share|improve this answer
    
It would help if you offered some reasoning. –  Chris Godsil Aug 29 '13 at 1:16
    
Please look at oeis.org/A000392 –  HEKTO Oct 19 '13 at 17:33

Hint:

If you consider fixed $A$ for a moment, then $B$ must be a subset of the complement of $A$, and so there are $2^{n-i}$ choices for $B$.

share|improve this answer

Hint: If you don't insist that $A \cup B = S$, each element has three places it can go: into $A$, into $B$ or neither.

share|improve this answer
    
Knowing your answers, Ross, and seeing the upvotes, I'm convinced this is a good hint. But for the life of me I cannot see how it works :) I think I'm just not a combinatorics person... –  rschwieb Oct 19 '12 at 17:06
1  
So would it just be $3^n$? –  user26069 Oct 19 '12 at 17:15
    
@rschwieb: think about picking up each element of $S$ in turn and putting into one of three boxes. How many ways are there to do that? Then the ones you put into first box are $A$, the second $B$ –  Ross Millikan Oct 19 '12 at 17:18
    
@user46221: that's right. It is like the argument that the number of subsets of $S$ is $2^n$-each element can be in or out. –  Ross Millikan Oct 19 '12 at 17:19
    
@rschwieb: What do you mean "no matter what sets $A,B$ you chose"? It is the very task to count the ways to chose $A,B$, not count some number for possibly different choices of $A,B$. –  Hagen von Eitzen Oct 19 '12 at 17:33

Your Answer

 
discard

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