# 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.

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

• This explanation really helped me, there's just one thing I don't understand. $3^n$ represents all options like you said. Then we must divide by 2 because we counted double. Then we add 1 option where $A=B=S$. The only thing I don't see is where the $(-1)$ came from? Why do we divide $(3^n - 1)$ by 2, and not just $3^n$? – Cauthon Nov 1 '14 at 18:12
• Ah. I think the solution I gave treats A and B differently... – Daniel Goldman Nov 1 '14 at 18:15
• There are $3^n$ possibilities. Exactly $1$ of them is counted once and must not be touched. The remaining $3^n-1$ are all counted twice, wich can be repaired by taking $\frac{1}{2}(3^n-1)$ in stead. – drhab Nov 1 '14 at 18:16

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?

• OK so according to my approach, when $n=3$ the answer is 27 ($(3 choose 0) + 2^1*(3 choose 1) + 2^2*(3 choose 2) + 2^3*(3 choose 3)$). And according to your direction it should be 27 because of $3^3$ (3 options for each of the 3 elements). But then we must divide the answer by 2, so it would be 13? Is this correct? – Cauthon Nov 1 '14 at 17:56
• The general answer is $\frac{3^n-1}{2}+1$. It can be obtained (after adjusting for double-counting) using your approach, plus the Binomial Theorem. – André Nicolas Nov 1 '14 at 17:59

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.