Tell me more ×
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.
up vote 1 down vote favorite

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

2 Answers

up vote 5 down vote

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
show 3 more comments
up vote 0 down vote

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

Your Answer

 
discard

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