# Counting ordered triples of sets, with empty intersection.

I was recently asked this question which I couldn't solve.

Give the number of ordered triples $(A_1, A_2, A_3)$ of sets which have the property that

1. $A_1 \cup A_2 \cup A_3 = \{1,2,3,4,5,6,7,8,9,10\}$, and
2. $A_1 \cap A_2 \cap A_3 = \emptyset$

You are supposed to express the answer in the form $2^a3^b5^c7^d$ where $a,b,c,d$ are nonnegative integers.

-
Do you have any thoughts on the problem, even though you might have not been able to solve it? What have you tried? Regards – Amzoti Apr 15 '13 at 18:13

This of it this way:

You are trying to assign each $i \in \{1,2,\dots,10\}$ a set from $\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\}$, where for e.g. if $i$ is assigned $\{2,3\}$, it is in $A_2$ and $A_3$.

So the answer is $6^{10}$.

-
$a= b=10$ is the answer in that case? – Anush Apr 15 '13 at 18:06
@Anush: Yes, you are familiar with $a^m \times b^m = (ab)^m$ right? – Aryabhata Apr 15 '13 at 18:07
Yes. I was just surprised the question listed $c$ and $d$ which turn out to be zero. – Anush Apr 15 '13 at 18:24

Hint: each number ($1$ through $10$) has to be in at least one of the sets and cannot be in all of them. How many choices does that give you?

-