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-exclusion
- Dynamic programming based algorithms for set multicover and multiset multicover problems
The 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} \\ \hline 1 & 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?