Giving a number of sets, what is a formula of number of different cases?

82 Views Asked by At

For example, two sets has 5 different cases. (Each sets in any cases must't be empty.)

enter image description here

$A \cap B = \varnothing$ , $A' \cap B \ne \varnothing$ , $A \cap B' \ne \varnothing$

enter image description here

$A \cap B \ne \varnothing$ , $A' \cap B \ne \varnothing$ , $A \cap B' \ne \varnothing$

enter image description here

$A \cap B \ne \varnothing$ , $A' \cap B = \varnothing$ , $A \cap B' \ne \varnothing$

enter image description here

$A \cap B \ne \varnothing$ , $A' \cap B \ne \varnothing$ , $A \cap B' = \varnothing$

enter image description here

$A \cap B \ne \varnothing$ , $A' \cap B = \varnothing$ , $A \cap B' = \varnothing$

For three sets, I think it has 117 different cases. (I'm not sure. I get it by counting. It is a lot. It may be wrong.)

For n number of sets, what is a formula of number of different cases?

1

There are 1 best solutions below

2
On BEST ANSWER

To be clear, it seems that by a "case" you mean a consistent set of data about which intersections and set-differences among the sets are empty or not. Now, there is a simple way to describe all such intersections and set-differences. If your sets are $A_1,\dots,A_n$, then for any subset $S\subseteq\{1,\dots,n\}$, let $B_S=\bigcap_{i\in S} A_i\cap \bigcap_{j\not\in S} A_j^c$. That is, $B_S$ consists of all the points that are in each $A_i$ for $i\in S$, but not in $A_j$ for each $j\in S$. Note that every point $x$ is in exactly one such set $B_S$ (since $S$ must be the set of all $i$ such that $x\in A_i$). So, any set formed by intersections and set-differences of the $A_i$ is the union of the sets of the form $B_S$ which it contains.

This means that a "case" is just determined by which of these sets $B_S$ are nonempty. There are $2^n$ different subsets $S\subseteq\{1,\dots,n\}$, so there are $2^{2^n}$ different ways to determine which sets $B_S$ are nonempty.

But wait! In the case $n=2$, that would give $2^{2^2}=16$ cases, not just the $5$ that you found. What's going on? There are a couple things. First, note that when $S=\emptyset$, $B_S$ is just the complement of the union of all the $A_i$. You are ignoring this complement: your cases don't care whether there is anything outside of all the $A_i$ or not. So, we don't care about $B_\emptyset$, halving our number of cases to $2^{2^n-1}$.

The second issue is your restriction that all of the sets must be nonempty. That means that we need to subtract the cases where any of the sets are empty. We can do this using inclusion-exclusion. Note, for instance, that there are $2^{2^{n-1}-1}$ cases where $A_1$ is empty, since this is equivalent to just choosing a case for the sets $A_2,\dots,A_n$. More generally, if we pick $k$ of the sets to be empty, there are $2^{2^{n-k}-1}$ cases. So counting the number of cases where none of the $A_i$ are empty by inclusion-exclusion, we get $$\sum_{k=0}^n (-1)^k\binom{n}{k}2^{2^{n-k}-1}$$ (here the $k$th term corresponds to picking $k$ of the sets to be empty, with $\binom{n}{k}$ coming from the different ways to pick the $k$ sets).

For instance, when $n=2$, this sum is $$8-2\cdot 2+1=5,$$ just as you found. Here $8$ is counting all cases where the sets are allowed to be empty. We then subtract $2\cdot 2$ for the cases where either $A$ is empty or $B$ is empty (if $A$ is empty, there are two cases: either $B$ is empty or not; similarly there are two cases if $B$ is empty). Finally, we add back in $1$ since we subtracted the case where both $A$ and $B$ are empty twice.