An $n$ element set can be written as a union of disjoint sets, in $B_n$ different ways. But what if the sets are not disjoint?

Question

If we let $X=\{1,2,3,\ldots n\}$ then what is the value of $\left|\{\mathcal{F}\subseteq\wp(X):\bigcup\mathcal{F}=X\}\right|?$ I know that if one requires the sets in $\mathcal{F}$ be pairwise disjoint this is just the the $n^{\text{th}}$ bell number. However I'm interested in counting all the set covers of an $n$ element set. Could anyone point me to a reference?

Answer 1

I believe the answer is $$\displaystyle\sum_{k=0}^{n} {n\choose k} \left(-1\right)^{k} 2^{2^{n-k}}$$ The idea is to think of collections which do not cover $S$, and subtract them away. The reason is that we take the power set of the power set of $S$, but then we must subtract off those for which a particular element appears in no subset. The collections of subsets of which $1$ isn’t a member is equinumerous with the collections of subsets of $n-1$ items: subtract this $n$ times, one for each element. Now collections of subsets that don’t include $1$ or $2$ say, have been subtracted twice, so we add them back in and so on with a inclusion exclusion argument continuing.

To prove this, for $\mathcal{F}\subseteq S$ let $$\mathcal{T}_{\mathcal{F}}=\mathcal{P}\left(\mathcal{P}\left(S\setminus\mathcal{F}\right)\right)$$ Clearly, $\left|\mathcal{T_{\mathcal{F}}}\right|=2^{2^{n-k}}$ when $\left|\mathcal{F}\right|=k$. $$\left\{ \mathcal{F}\subseteq S\vert\bigcup\mathcal{F}=S\right\} =\bigcap_{i=1}^{n}\overline{\mathcal{T}_{\left\{ i\right\} }}$$ So, by inclusion-exclusion, $$\left|\left\{ \mathcal{F}\subseteq S\vert\bigcup\mathcal{F}=S\right\} \right|=\left|\mathcal{T_{\emptyset}}\right|-\sum_{i=1}^{n}\left|\mathcal{T}_{\left\{ i\right\} }\right|+\sum_{1\leq i<j\leq n}\left|\mathcal{T}_{\left\{ i,j\right\} }\right|\mp... $$ $$={n \choose 0}2^{2^{n}}-{n \choose 1}2^{2^{n-1}}+{n \choose 2}2^{2^{n-2}}\mp...$$ $$=\displaystyle\sum_{k=0}^{n} {n\choose k} \left(-1\right)^{k} 2^{2^{n-k}}$$