Calculate number of elements of $\mathcal{P}(\mathcal{P}(M))$ whose elements themselves are cover ing M

Question

Given a set M. Can I easily calculate the number of elements $S_i \in \mathcal{P}(\mathcal{P}(M))$ such that $\bigcup\limits_{s \in S_i}s = M$?

For example, $M = \{A,B\}$. Then the number of elements of $\mathcal{P}(\mathcal{P}(M))$ meeting that condition would be 10: there are $2^{2^2} = 16$ elements, every element except for $\emptyset, \{\emptyset\}, \{A\}, \{B\}, \{\emptyset, A\}, \{\emptyset, B\}$ has $A$ and $B$ in it.

Thanks in advance.

Answer 1

A very nice question. You can determine this number using inclusion-exclusion. Denote $|M|$ by $n$, and consider the $n$ conditions of a particular element missing from the union. Then by inclusion-exclusion the desired count is

$$ \sum_{k=0}^n\binom nk(-1)^k2^{2^{n-k}}\;. $$

In your example with $n=2$, this is $2^{2^2}-2\cdot2^{2^1}+2^{2^0}=16-8+2=10$.