How many ordered pairs $(X, Y)$, where $X$, $Y$ are subsets of $\{5,6,7,8,9\}$

Question

How many ordered pairs $(X, Y)$, where $X$, $Y$ are subset of $\{5,6,7,8,9\}$ are there if $X \cap Y = \emptyset$. Find an old post, which gives me hint that works, but not $100\%$ sure I can visualize it correctly. it would be $3^5$. The hint says: "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".

What does it mean "if we don't insist that $A \cup B = S$"? Why does that matter? I can't each element has three choices would end up the same number as $A \cap B = \emptyset$.

Answer 1

One example of what you are describing would be: $$ X=\{5,6\},\quad Y=\{7,8\} $$ Then $X\cap Y=\emptyset$ since $X$ and $Y$ share no elements, and $X\cup Y\neq S$ since $X$ and $Y$ does not cover all elements of the base set $S=\{5,6,7,8,9\}$.

---

Another way to formulate this would be to mark each of the elements $5,6,7,8,9$ as either $X$, $Y$ or $S$ where the latter mark is for elements only in $S$ not in the other two. Then we are essentially asking for the number of markings. The marking corresponding to the example from before would be: $$ \begin{array}{c|c|c} 5 & 6 & 7 & 8 & 9\\ \hline X & X & Y & Y & S \end{array} $$ and since each mark has three options $(X,Y,S)$ and five digits $5,6,7,8,9$ are to be marked, there will be $3^5$ such possible markings.

Answer 2

5 6 5 7 5 8 5 9 6 7 6 8 6 9 7 8 7 9 8 9

9 8 9 7 9 6 9 5 8 7 8 6 8 5 7 6 7 5 6 5

Looks like 20 to me. Not sure how you get 3^5.

Answer 3

Well. Given set having 5 elements. They are ${5,6,7,8,9}=S$. Let $X and Y$ be the subset of $X$. Power set of $S$ contains $2^5=32$ subsets.

So the the number of order pairs $(X, Y)$ is equal to $32×32=1024$.

Adding the extra contraint $X\cap Y=\emptyset$ and $X\cup Y=S$. Power set of $S$ having 32 elements in which 16 pairs of sets are mutually disjoint and whose union is equal to $S$. Thus under these constraint the number of possibility of pairs $(X, Y)$ is equal to 16+16=32. (16 representing the inverting case, (Y, X)).