5. let $M$ be a set with $n$ elements. Determine the number of possibilities to select three subsets $A, B, C$ of $M$ such that

$$
\begin{gathered}
A \cap B \neq \emptyset, \quad B \cap C \neq \emptyset, \quad C \cap A \neq \emptyset \\
A \cap B \cap C=\emptyset
\end{gathered}
$$

## Solution:
Look at the Venn diagram in the figure. To burrow a triple $(A, B, C)$ as in the task is the same as distributing the $n$ elements of $M$ to the eight fields in this diagram so that the field $w$ is empty, but not the fields $x, y$ and $z$.

We first count the number of triples $(A, B, C)$ so that $A \cap B \cap C=\emptyset$. Each of the $n$ elements can be in any field except $w$, the field $w$ must remain empty. Consequently, according to the product rule, there are exactly $7^{n}$ such triples.

From this number we still have to subtract the number of triples $(A, B, C)$ for which $A \cap B=\emptyset$ or $B \cap C=\emptyset$ or $C \cap A=\emptyset$ applies (note that $A \cap B \cap C=\emptyset$ then automatically applies as well, we no longer have to consider this condition). We set

$$
\begin{aligned}
X & =\{(A, B, C) \mid A \cap B=\emptyset\} \\
Y & =\{(A, B, C) \mid B \cap C=\emptyset\} \\
Z & =\{(A, B, C) \mid C \cap A=\emptyset\}
\end{aligned}
$$

According to the on/off formula

$$
|X \cup Y \cup Z|=|X|+|Y|+|Z|-|X \cap Y|-|Y \cap Z|-|Z \cap X|+|X \cap Y \cap Z|
$$

Furthermore, for reasons of symmetry, $|X|=|Y|=|Z|$ and $|X \cap Y|=|Y \cap Z|=$ $|Z \cap X|$. The triples in $X$ correspond exactly to the distributions in which the two fields $x$ and $w$ remain empty, hence $|X|=6^{n}$. For the triples in $|X \cap Y|$, the fields $w, x$ and $y$ must remain empty, so $|X \cap Y|=5^{n}$. Finally, for the triples in $|X \cap Y \cap Z|$, the fields $w, x, y$ and $z$ remain empty, so $|X \cap Y \cap Z|=4^{n}$. Together, this results in $|X \cup Y \cup Z|=3 \cdot 6^{n}-3 \cdot 5^{n}+4^{n}$. The number you are looking for is therefore equal to

$$
7^{n}-3 \cdot 6^{n}+3 \cdot 5^{n}-4^{n}
$$