1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Cauthon Nov 1 '14 at 18:12
  • $\begingroup$ Ah. I think the solution I gave treats A and B differently... $\endgroup$ – Daniel Goldman Nov 1 '14 at 18:15
  • 1
    $\begingroup$ 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. $\endgroup$ – drhab Nov 1 '14 at 18:16
0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Cauthon Nov 1 '14 at 17:56
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Nov 1 '14 at 17:59
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.