# Finding the number of subset pairs of a set

If a set $S$ has $n$ elements, how many such pairs $(A,B)$ can be formed where $A$ and $B$ are subsets of $S$ and $A \cap B = \emptyset$?

-

## 2 Answers

Hint: If you don't insist that $A \cup B = S$, each element has three places it can go: into $A$, into $B$ or neither.

-
Knowing your answers, Ross, and seeing the upvotes, I'm convinced this is a good hint. But for the life of me I cannot see how it works :) I think I'm just not a combinatorics person... – rschwieb Oct 19 '12 at 17:06

1
So would it just be $3^n$? – user26069 Oct 19 '12 at 17:15
@rschwieb: think about picking up each element of $S$ in turn and putting into one of three boxes. How many ways are there to do that? Then the ones you put into first box are $A$, the second $B$ – Ross Millikan Oct 19 '12 at 17:18
@user46221: that's right. It is like the argument that the number of subsets of $S$ is $2^n$-each element can be in or out. – Ross Millikan Oct 19 '12 at 17:19
@rschwieb: What do you mean "no matter what sets $A,B$ you chose"? It is the very task to count the ways to chose $A,B$, not count some number for possibly different choices of $A,B$. – Hagen von Eitzen Oct 19 '12 at 17:33
show 3 more comments

Hint:

If you consider fixed $A$ for a moment, then $B$ must be a subset of the complement of $A$, and so there are $2^{n-i}$ choices for $B$.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 24, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9333704113960266, "perplexity_flag": "head"}