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.



Given A set $U$ and a set $\mathcal O$ of subsets of $U$, how many subsets of $\mathcal O$ have union $U$?
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](http://oeis.org/A000371))


