# Use the principle of inclusion-exclusion to find the number of coverings of an n-set S.

A covering of a set $$S$$ is a set $$\{A_1,A_2,\cdots,A_t$$} of non-empty subsets of $$S$$ such that $$A_1\cup A_2\cup\cdots\cup A_t$$ is $$S$$. (Note that $$A_i\neq A_j$$ for $$i\neq j$$; also $$t$$ can vary from 1 to $$2^{|S|}-1$$. The sets are not required to be disjoint). Use the principle of inclusion-exclusion to find the number of coverings of an $$n$$-set $$S$$.

I'm a little confused on how to start this problem, and what the ambient set and properties should be. Any hints for those would be appreciated.

• So your covering is a subset $F$ of $P\left(S\right)$ (the power set of $S$) which is required to satisfy the condition $A_1 \cup A_2 \cup \cdots \cup A_t = S$. Can you restate the latter condition as "$F$ satisfies neither $P_1$ nor $P_2$ nor ..." for some bunch of properties $P_1, P_2, \ldots$ ? Nov 4 '19 at 4:06

We have $$n$$ conditions that each of the $$n$$ elements be covered. There are $$\binom nk$$ ways to choose $$k$$ particular conditions, and there are $$2^{2^{n-k}-1}$$ subsets of the power set that violate these conditions, namely, any set of sets that don't contain any of the $$k$$ elements. (We need to subtract $$1$$ because the sets must not be empty.) Thus, by inclusion–exclusion, the number of covers is
$$\sum_{k=0}^n(-1)^k\binom nk2^{2^{n-k}-1}\;.$$
For $$n=0,1,2$$ this yields $$1,1,5$$, and indeed the set $$\{1,2\}$$ has the $$5$$ covers $$\{\{1,2\}\}, \{\{1\},\{2\}\}$$, $$\{\{1,2\},\{2\}\}$$, $$\{\{1\},\{1,2\}\}$$ and $$\{\{1\},\{2\},\{1,2\}\}$$.