How many $k$ tuples of subsets $S_1,...,S_k$ are there such that $S_1 \cap ..... \cap S_k = \emptyset $.

How many $k$ tuples of subsets $S_1,...,S_k$ are there such that

$S_1 \cap ..... \cap S_k = \emptyset $.

An attempt: Suppose we can make a sketch of a Venn diagram with $k$ subsets. Then there are $2^k$ total locations in the diagram, but we don't have to take their intersection since it has to be empty. Thus there are $2^{k} -1$ places to place $n$ numbers from $[n] = (1,...,n)$. Then there are $n-2^k \choose 2^k - 1$ total ways of doing this. Can someone please provide some feedback and tell me if I am in the right track ? I would really appreciate it. Thank you.

Solution 1:

Throughout, let $[n] = \{1, 2, \cdots, n\}$, and let $\mathcal{P}(S)$ denote the power set of $S$.

Given a $k$-tuple $(S_1, \cdots, S_k)$ of subsets of $[n]$ such that $\bigcap_{1\le i \le k} S_i = \emptyset$, consider the function $f: [n] \to \mathcal{P}([k])$ that takes $x \in [n]$ to the set of indices $i$ such that $x \in S_i$. In particular, since $\bigcap S_i = \emptyset$, we have $f(x) \neq [k]$ for all $x \in [n]$.

This function $f$ totally determines the $k$-tuple, since $S_i = \{x \in [n] \, : \, i \in f(x)\}$. Conversely, given any function $f: [n] \to \mathcal{P}([k])$ with $f(x) \neq [k]$ for all $x \in [n]$, we can obtain such a $k$-tuple by setting $S_i = \{x \in [n] \, : \, i \in f(x)\}$, as before.

Thus, to count the number of $k$-tuples, it suffices to count the functions satisfying the condition, of which there are evidently $(2^k -1)^n$.

Solution 2:

With this problem it does seem to have its origins in a combinatorics course and hence we may suppose that it is asking for inclusion-exclusion. We get the formula (follows by inspection)

$$\sum_{q=0}^n {n\choose q} (-1)^q (2^{n-q})^k.$$

With this inclusion-exclusion poset the nodes $P \subseteq [n]$ represent $k$-tuples whose intersection is $P$ or a superset of $P.$ This formula assigns weight one to $k$-tuples who do not intersect because they only appear in the $q=0$ term. Now for a $k$-tuple that intersects in exactly $p$ elements it is included in all nodes that are subsets of those $p$ elements. With $q$ the size of these nodes we get the contribution

$$\sum_{q=0}^p {p\choose q} (-1)^q = 0$$

because $p\ge 1.$ Therefore we assign weight one only to admissible tuples and weight zero to all others, which is the desired behaviour.

Simplifying the formula we get

$$2^{nk} \sum_{q=0}^n {n\choose q} (-1)^q 2^{-kq} = 2^{nk} (1-2^{-k})^n = (2^k-1)^n$$

which matches the result from the accepted answer.