2
$\begingroup$

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:

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?

$\endgroup$
  • 1
    $\begingroup$ This might fit better in cs.se, or even math.se. $\endgroup$ – Yuval Filmus Dec 30 '15 at 9:22
  • 1
    $\begingroup$ For k=1, there is only the {1,2} solution. For k=2, there is {1}{2},{1}{1,2},{2}{1},{2}{1,2},{1,2}{1},{1,2}{2}, and {1,2}{1,2} which is seven. If you don't want ordered covers you need to replace a(X)^k for a more complicated formula. $\endgroup$ – Andreas Björklund Dec 30 '15 at 15:33
0
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.