3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ And these are subsets of? $\{1,2, \ldots n\}$? $\endgroup$ – kishlaya Mar 2 '17 at 18:32
  • $\begingroup$ the problem does not mention anything, But I think these are subsets of a set $S$ with $n$ elements $\endgroup$ – Mahidevran Mar 2 '17 at 18:33
  • $\begingroup$ Yeah it should be some "finite" set with cardinality atleast $k$. Otherwise the answer is clearly $0$ or infinite. Alongwith it should also be mentioned that these subsets are non-empty otherwise again just take all empty subsets and you're done. $\endgroup$ – kishlaya Mar 2 '17 at 18:38
  • $\begingroup$ I haven't checked that yet because the question wasn't really precise.. $\endgroup$ – kishlaya Mar 2 '17 at 18:42
  • $\begingroup$ Can you please check ? $\endgroup$ – Mahidevran Mar 2 '17 at 18:43
2
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.