I'm given a universal set $N = \{1, 2, \dots, n\}$, a family of sets $\mathcal{F} = \{ S_1, S_2, \dots, S_m \}$, $S_i \subseteq N$, and I need to count the number of distinct ways to cover the universal set using sets from $\mathcal{F}$.I've found a couple of articles describing the usage of inclusion-exclusion principle to tackle a similar problem:Set partitioning via inclusion-exclusionDynamic programming based algorithms for set multicover and multiset multicover problemsThe papers describe how to compute the number of $k$-covers $c_k$. A $k$-cover is a tuple $(S_1, \dots, S_k)$ over $\mathcal{F}$ such that $S_1 \cup \dots \cup S_k = N$. According to the papers,$$c_k(\mathcal{F}) = \sum_{X \subseteq N} (-1)^{|X|} a(X)^k$$ where$a(X) = |\{S \in \mathcal{F} \mid S \cap X = \emptyset\}|$ (the number of sets in $\mathcal{F}$ that avoid $X$).I like this method because it (at least, theoretically) allows to compute the number of covers in $O(n 2^n)$ time. A simple DP approach I can think of requires $O(|\mathcal{F}| 2^n)$ time and is too expensive since in my case $|\mathcal{F}|$ is slightly less than $2^n$.I tried this formula on a simple example $\mathcal{F} = \{ \{1\}, \{2\}, \{1, 2\}\}$$$\begin{array}{c|c|r}X & a(X) & (-1)^{|X|} \\\hline\emptyset & 3 & 1 \\\{1\} & 1 & -1 \\\{2\} & 1 & -1  \\\{1, 2\} & 0 & 1 \end{array}$$$$\begin{array}{c|c|c|c}k & c_k(\mathcal{F}) & c_k \text{(computed)} & \text{Number of covers} \\\hline1 & 3 - 1 - 1 + 0 & 1 & 1\\2 & 3^2 - 1^2 - 1^2 + 0 & 7 & 3 \\3 & 3^3 - 1^3 - 1^3 + 0 & 25 & 1  \\\end{array}$$I don't know how to interpret the values of $c_k$ I've got. They look really strange. Is this method correct? Or is there a simpler way to count set covers in $O(n 2^n)$ time?
Counting distinct set covers
set cover;combinatorics
Thanks to Andreas Bjrklund, I realized that $c_k$ is the number of all tuples with repetitions. I reread the article carefully and reformulated the problem in the following way:Let $B = 2^{\mathcal{F}}$, $A_i = \{S \in 2^\mathcal{F} \mid S \cap \{i\} = \emptyset \}$ (i.e. set of all subsets of $\mathcal{F}$ that avoid singleton set $\{i\}$), and $C(\mathcal{F})$ is the number of distinct covers of $\mathcal{F}$. Then from the inclusion-exclusion principle we have:$$C(\mathcal{F}) = \sum_{X \subseteq N} (-1)^{|X|} 2^{a(X)}$$As before, $a(X)$ stands for the number of sets in $\mathcal{F}$ that avoid all of $X$.I've tested this formula on a couple of examples, and it works like a charm. For the simple example from the question above we have:$$2^3 - 2^1 - 2^1 + 2^0 = 5$$