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.