<p>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:</p>

<p>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$.</p>

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

CC BY-SA 3.0
2015-12-30T20:04:38.507Z
2015-12-30T20:25:39.190Z
2015-12-30T20:25:39.190Z
roman-kashitsyn
<p>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}$.</p>

<p>I've found a couple of articles describing the usage of inclusion-exclusion principle to tackle a similar problem:</p>

<ul>
<li><a href="http://epubs.siam.org/doi/abs/10.1137/070683933" rel="nofollow">Set partitioning via inclusion-exclusion</a></li>
<li><a href="http://www.sciencedirect.com/science/article/pii/S0304397510001118" rel="nofollow">Dynamic programming based algorithms for set multicover and multiset multicover problems</a></li>
</ul>

<p>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$).</p>

<p>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$.</p>

<p>I tried this formula on a simple example $\mathcal{F} = \{ \{1\}, \{2\}, \{1, 2\}\}$</p>

<p>$$
\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}
$$</p>

<p>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?</p>

CC BY-SA 3.0
2015-12-30T09:22:34.103Z
This might fit better in cs.se, or even math.se.
Yuval Filmus
CC BY-SA 3.0
2015-12-30T15:33:43.050Z
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.
Andreas Björklund
<set-cover><combinatorics>
Counting distinct set covers
roman-kashitsyn
# Counting distinct set covers

(Asked by: username_0 on 2015-12-30)

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](http://epubs.siam.org/doi/abs/10.1137/070683933)
* [Dynamic programming based algorithms for set multicover and multiset multicover problems](http://www.sciencedirect.com/science/article/pii/S0304397510001118)

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?

**Tags:** set-cover, combinatorics

> **Comments:**
> **username_1**: This might fit better in cs.se, or even math.se.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_0 on 2015-12-30. Score: 0 | Accepted answer

Thanks to username_2, 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$$


---

