Determine number of ways

Question

How can we find with how many ways we can choose three subsets $A_1, A_2, A_3$ of $\{1,2,3, \dots, 9\}$ such that $A_1 \cap A_2 \cap A_3= \varnothing$ ? (their pairwise intersection can be non-empty)

Can you give me a hint?

Answer 1

Try forming a sequence of 9 numbers that consists of the numbers 0, 1, 2 and 3, by the following rule:

• If the digit in the i-th index is 0, that means that the number i is not a member of any subset.
• If the digit in the i-th index is 1, that means that the number i is a member of the subset $A_1$
• If the digit in the i-th index is 2, that means that the number i is a member of the subset $A_2$
• If the digit in the i-th index is 3, that means that the number i is a member of the subset $A_3$

Any index has only one digit assigned to it, so the union of the sets is empty.

I'm not sure from your question if this is relevant, but notice that if there is no difference between the different subsets (you only care about the choices of members), then you need to take this symmetry into account (you don't want to count the same arrangement twice).