Choosing pairs of subsets so that their union is S I'm struggling with a combinatorics problem - in how many ways can I choose two subsets of set S, so that their union is set S. Subsets do not have to be disjoint.
I first thought of it this way: For each size of subset A - I know how many subsets B there are. For instance, if subset A is of size 5, then there are exactly $2^5$ choices for subset B (because we must choose all $n-5$ elements, and now there are $2^5$ options to add to these $n-5$ elements from set A).
My problem is that this way I count many pairs twice. Let's say $n=100$ and I choose subset A of size 5, and its pair subset B of size 97 (the 95 elements that must be chosen, and 2 elements out of subset A). This would be counted again when I choose subset A of size 97, and subset B of size 5.
I'm not sure how to get rid of all subsets that I count twice. Thanks for any help.
 A: For every element in $S$ there is a choice to be made: it belongs
to $A-B$, to $B-A$ or to $A\cap B$. That gives $3^{n}$ possibilities
where $n$ denotes the cardinality of $S$. 
However, this result corresponds
with the cardinality of $\left\{ \left\langle A,B\right\rangle \mid A\cup B=S\right\} $
and what we are really after is the cardinality of $\left\{ \left\{ A,B\right\} \mid A\cup B=S\right\} $.
If $A\neq B$ then $\left\langle A,B\right\rangle \neq\left\langle B,A\right\rangle \wedge\left\{ A,B\right\} =\left\{ B,A\right\} $
and a double counting must be repaired. In special case $A=B$ the
condition $A\cup B=S$ leads to $A=B=S$ and only in that case there
is no double counting. 
This leads to $\frac{1}{2}\left(3^{n}-1\right)+1$
for the cardinality of $\left\{ \left\{ A,B\right\} \mid A\cup B=S\right\} $.
A: You will always count any pair twice.  Except $A=B=S$, I suppose.
Another approach: Any element is in $A$, $B$ or both.  So how many options for 100 elements?
A: Here are my initial thoughts. I feel like it's missing something though.
Let $n = |S|$. Suppose you select m elements for A. Then, in that same trial (so that's multiplication inside the sum) you must, at least select the remaining $n-m$ elements for B.
$\sum\limits_{m=0}^n [{n \choose m}\sum\limits_{k=n-m}^n{n \choose k}]$
This is considering A and B as being different in some way. Divide by two and you should get the correct result.
