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.
Best Answer
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\} $.