Counting distinct set covers

Question

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?

Answer 1

Thanks to Andreas Björklund, 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$$