Let $U$ be a finite set and $\mathcal O$ a set of subsets of $U$, how many subsets $\mathcal S$ of $\mathcal O$ satisfy the union of the elements of $\mathcal S$ is equal to $U$?
I think the problem of finding the smallest of these subsets is called the set cover problem, I can't find any reference to this structure though. Thanks in advance.
Regards.
EDITED:
Let $F({\cal O}, U)$ be the number of ways to cover $U$ using a multiset $\cal O$ of subsets of $U$ (so coverings using different versions of the same set are considered as different). Let $A$ be one element of $\cal O$, which occurs with multiplicity $k$ in $\cal O$. We can either include $A$ or not. If we do not include it, we then have to cover $U$ using ${\cal O} \backslash \{A^*\}$ (i.e. ${\cal O}$ with all occurrences of $A$ removed).
If we do include it, there are $2^k-1$ choices of which occurrences of $A$ in $\cal O$ to use for this, and then we have to cover the remaining points
$U \backslash A$ using $\{B \backslash A\;:\; B \in {\cal O}\}$ (note that this can introduce additional multiplicity, because different $B$ can have the same $B \backslash A$). Thus
$$F({\cal O},U) = F({\cal O} \backslash \{A^*\},U) + (2^k-1) F(\{B \backslash A \; :\; B \in {\cal O}\}, U \backslash A) $$
with "boundary conditions" $$F({\cal O},U) = 0\ \text{if}\ U \backslash \bigcup {\cal O} \ne \emptyset $$ $$F(k \times \emptyset, U) = \cases{2^k & if $U = \emptyset$\cr 0 & otherwise\cr}$$ Of course the time this requires will generally be exponential in $|{\mathcal O}|$ (though not necessarily as bad as $2^{|{\mathcal O}|}$ if you are clever at caching and exploiting symmetry).
EDIT: Here is a Maple program that seems to work quite well in not-too-large examples.
F:= proc(Oh, Mult, m)
# m positive integer
# Oh a list of subsets of {1..m}
# Mult their multiplicities
# Returns number of ways to cover {1..m} using Oh with multiplicities Mult
option remember;
local mp, n, i, k, Aind, A, smax, M, Ohp, Ohs, V,F1,F2,
F1needed, Nocc,Multp, Multpp, unco, Psubs;
n:= nops(Oh);
if n = 0 then return 0 fi;
Nocc:= [seq(numboccur(Oh,i),i=1..m)];
if has(Nocc,0) then
return 0 # can't cover elt 1
elif member(1,Nocc,'p') then
# only one member of Oh covers p. Need that one!
F1needed:= false;
Aind:= op(select(t -> has(Oh[t],p),[$1..nops(Oh)]));
else # take a largest element A of Oh
M:= [seq(nops(Oh[i]),i=1..n)];
smax:= max(M);
Aind:= min(select(t -> M[t]=smax, [$1..n]));
F1needed:= true;
fi;
A:= Oh[Aind];
k:= Mult[Aind];
Ohp:= subsop(Aind=NULL,Oh);
Multp:= subsop(Aind=NULL,Mult);
if F1needed then # case where we don't use A
F1:= F(Gperm(Ohp,m), Multp, m)
else
F1:= 0;
fi;
# now consider the case where we do use A.
unco:= {$1..m} minus A;
mp:= nops(unco);
if mp = 0 then # nothing left to cover, so A at least once and any subset of the rest
return F1 + (2^k-1)*mul(2^Mult[j],j=1..n-1);
fi;
# map elts of Ohp to their unco images
Psubs:= [seq(unco[i]=i,i=1..nops(unco))];
Ohp:= map(S -> subs(Psubs, S intersect unco),Ohp);
# now take account of multiplicity introduced
Ohs:= convert(convert(Ohp,set),list);
Multpp:= [0 $ nops(Ohs)];
for i from 1 to n-1 do
member(Ohp[i],Ohs,'j');
Multpp[j]:= Multpp[j]+Multp[i];
od:
F1 + (2^k-1)*F(Gperm(Ohs,mp), Multpp, mp);
end;
Gperm:= proc(Oh,m)
# return canonically permuted version of Oh
# sort 1..m in increasing order of number of occurrences in Oh
local Nocc,Perm,Psubs;
Nocc:= [seq(numboccur(Oh,i),i=1..m)];
Perm:= sort(Nocc,output='permutation');
Psubs:= zip(`=`,Perm,[$1..m]);
subs(Psubs,Oh);
end proc;
For example:
Oh:= convert(combinat:-powerset({$1..8}),list):
Mult:= [1$nops(Oh)]:
F(Oh,Mult,8);
Result (in about 1/2 second):
$115792089237316195423570985008687907850547725730273056332267095982282337798562$
(which agrees with OEIS sequence A000371)
If $\mathcal O$ is the set of all subsets of an $n$-element set $U$ then by inclusion-exclusion the number of subsets of $\mathcal O$ whose union is $U$ is $$\sum_{k=0}^n (-1)^{n-k} \binom nk 2^{2^k}.$$ This is sequence A000371 in the OEIS. I don't think there's any simple formula for an arbitrary set of subsets of $U$.
If $\mathcal{O}$ consists of all subsets of size 2, then you are counting graphs without isolated vertices, see A006129.
My feeling is that in general this problem will be #P-hard, but don't ask me for a proof.
Well, if $\mathcal O$ is the set of all subsets of $U$ then there are $2^{2^u}$ subsets of $\mathcal O$, where $u$ is the cardinality of $U$, and most of these will have union equal to $U$. In fact, any subset whose union is not equal to $U$ has some element of $U$ consistently missing from its elements, hence there are at most $u\cdot 2^{2^{u-1}}$ (which is much less than $2^{2^u}$) many such.
This simple estimate in the case $u=5$ gives that among the 4,294,967,296 sets of subsets of $U=\{1,2,3,4,5\}$, at most 327,680 don't union up to $U$.
Let me reduce the general case for multisets to a possibly simpler case with a smaller underlying set. Let $F(f,X)$ denote how many submultisets of a multiset $f$ that cover $X$, and if $f:\mathcal{A}\rightarrow\mathbb{N}\setminus\{0\}$, then let $F(f)$ denote how many submultisets of $f$ have the same union as the union of the multiset $f$.
Suppose that $f:\mathcal{A}\rightarrow\mathbb{N}\setminus\{0\}$ is a multiset that covers $X$. Then define the specialization ordering $\leq_{\mathcal{A}}$ to be the preordering where $x\leq_{\mathcal{A}}y$ iff $y\in A\Rightarrow x\in A$. We say that $\mathcal{A}$ is $T_{0}$ if $\leq_{\mathcal{A}}$ is a partial ordering and $\mathcal{A}$ is $T_{1}$ if $\leq_{\mathcal{A}}$ is the partial ordering where $x\leq_{\mathcal{A}}y\Rightarrow x=y$ (i.e. $\leq_{\mathcal{A}}$ is the trivial partial ordering). The multiset $f$ is said to be $T_{0}$ or $T_{1}$ iff the domain $\mathcal{A}$ is respectively $T_{0}$ or $T_{1}$. I claim that calculating $F(f,X)$ easily reduces to the case where $f$ is $T_{1}$. And in case you were wondering, yes these are the topological separation axioms $T_{0}$ and $T_{1}$ generalized to a more general case.
It is easy to show that the general case reduces to the case where $\mathcal{A}$ is $T_{0}$. First, if $f:\mathcal{A}\rightarrow\mathbb{N}\setminus\{0\}$ is not $T_{0}$, then define $\simeq_{\mathcal{A}}$ to be the equivalence relation on $X$ where $x\simeq_{\mathcal{A}}y$ iff $x\leq_{\mathcal{A}}y$ and $y\leq_{\mathcal{A}}x$. Then let $\pi:X\rightarrow X/\simeq$ be the projection onto the quotient. Let $f':\{\pi[A]|A\in\mathcal{A}\}\rightarrow\mathbb{N}$ be the mapping where $f'(\pi[A])=f(A)$. Then it is easy to see that $F(f',X/\simeq_{\mathcal{A}})=F(f,X)$ and $\{\pi[A]|A\in\mathcal{A}\}$ is $T_{0}$.
Now suppose that $f:\mathcal{A}\rightarrow\mathbb{N}\setminus\{0\}$ and $\mathcal{A}$ is $T_{0}$. Then $\leq_{\mathcal{A}}$ is a partial ordering. Let $D$ be the collection of all maximal elements of the partial ordering $\leq_{\mathcal{A}}$. We take note that if $\mathcal{B}\subseteq\mathcal{A}$ and $\mathcal{B}$ covers $D$, then $\mathcal{B}$ covers all of $X$. If $x\in X$, then $x\leq_{\mathcal{A}}a$ for some $a\in D$. Therefore, there is some $B\in\mathcal{B}$ with $a\in B$. Therefore since $x\leq_{\mathcal{A}}a$, we have $x\in B$ as well. Therefore $\mathcal{B}$ truly covers all of $X$.
Let $f\wedge D$ be the multiset that corresponds to $\mathcal{A}\wedge D=\{A\cap D|A\in\mathcal{A}\}$ when we count multiplicity. In other words, $f(R)=\sum\{f(A)|A\in\mathcal{A},A\cap D=R\}$. Then we have $F(f\wedge D,D)=F(f,X)$. However, it is clear that the specialization ordering $\leq_{\mathcal{A}\wedge D}$ is the restriction of the specialization ordering $\leq_{\mathcal{A}}$ to $D$. However, $D$ is an antichain with respect to $\leq_{\mathcal{A}}$, so the partial ordering $\leq_{\mathcal{A}\wedge D}$ is trivial. Therefore $f\wedge D$ is truly a $T_{1}$ multiset.
At last, I claim that the problem is no more general when one considers multisets instead of simply sets. Suppose $(A_{i})_{i\in I}$ is a collection of sets that cover a set $X$. Without loss of generality, we can assume that $X\neq A_{i}$ for all $i\in I$. Then define $F((A_{i})_{i\in I})=|\{J\subseteq I|\bigcup_{j\in J}A_{j}=X\}|$. Then define $\mathcal{A}=\{A_{i}\cup I\setminus\{i\}|i\in I\}$. Then $\bigcup\mathcal{A}=X\cup I$, but the subsets of $\mathcal{A}$ that cover $X\cup I$ are in a one-to-one correspondence with the subsets $J$ of $I$ such that $X=\bigcup_{j\in J}A_{j}$.
