Counting distinct set covers 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 &amp; a(X) &amp; (-1)^{|X|} \\
\hline
\emptyset &amp; 3 &amp; 1 \\
\{1\} &amp; 1 &amp; -1 \\
\{2\} &amp; 1 &amp; -1  \\
\{1, 2\} &amp; 0 &amp; 1 
\end{array}
$$
$$
\begin{array}{c|c|c|c}
k &amp; c_k(\mathcal{F}) &amp; c_k \text{(computed)} &amp; \text{Number of covers} \\
\hline
1 &amp; 3 - 1 - 1 + 0 &amp; 1 &amp; 1\\
2 &amp; 3^2 - 1^2 - 1^2 + 0 &amp; 7 &amp; 3 \\
3 &amp; 3^3 - 1^3 - 1^3 + 0 &amp; 25 &amp; 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?
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$$