# Families of subsets whose union is the whole set

Let $n\geq k>0$, and consider the family $\mathcal{F}$ consisting of all $\binom{n}{k}$ subsets of $A=\{1,2,\ldots,n\}$ of size $k$. Among the $2^{\binom{n}{k}}$ subsets of $\mathcal{F}$, how many subsets contain subsets of $A$ whose union is $A$?

For example, if $k=1$, then $\mathcal{F}=\{\{1\},\{2\},\ldots,\{n\}\}$, and only $1$ subset of $\mathcal{F}$ contain subsets of $A$ whose union is $A$, namely $\mathcal{F}$ itself.

For $k=2$, the situation seems much less clear.

## 2 Answers

Look at the complement, and use an inclusion-exclusion argument. For $\ell\in A$ let $$\mathscr{F}_\ell=\{F\in\mathscr{F}:\ell\notin F\}\;;$$ clearly $|\mathscr{F}_\ell|=\binom{n-1}k$. Let $\mathfrak{F}_\ell=\wp(\mathscr{F}_\ell)$; the members of $\mathfrak{F}_\ell$ are the subsets of $\mathscr{F}$ whose unions do not contain $\ell$. By the inclusion-exclusion principle there are

\begin{align*} \left|\bigcup_{\ell\in A}\mathfrak{F}_\ell\right|&=\sum_{\varnothing\ne J\subseteq A}(-1)^{|J|-1}\left|\bigcap_{\ell\in J}\mathfrak{F}_\ell\right|\\ &=\sum_{j=1}^n\binom{n}j(-1)^{j-1}2^{\binom{n-j}k} \end{align*}

subsets of $\mathscr{F}$ that do not cover $A$ and hence

$$2^{\binom{n}k}-\sum_{j=1}^n\binom{n}j(-1)^{j-1}2^{\binom{n-j}k}=\sum_{j=0}^n\binom{n}j(-1)^j2^{\binom{n-j}k}$$

that do.

As a quick check, when $k=1$ this reduces to

$$\sum_{j=0}^n\binom{n}j(-1)^j2^{n-j}=(-1+2)^n=1$$

by the binomial theorem. When $k=n-1$ it reduces to

\begin{align*} \sum_{j=0}^n\binom{n}j(-1)^j2^{\binom{n-j}{n-1}}&=2^n-2n+\sum_{j=2}^n\binom{n}j(-1)^j\\ &=2^n-1-n+\sum_{j=0}^n\binom{n}j(-1)^j\\ &=2^n-n-1\;, \end{align*}

which is also clearly right: there are $n$ subsets of $A$ of cardinality $n-1$, and the only subsets of that family that don’t cover $A$ are the $n$ singleton subsets and the empty subset.

For any set $R \subseteq \{1,\ldots, n\}$ of size $m$, the number of subsets of $\mathcal F$ whose union is disjoint from $R$ is $2^{n-m \choose k}$. We can then use inclusion-exclusion to count the number whose union is $A$:

$$\sum_{i=0}^n (-1)^i {n \choose i} 2^{n-i \choose k}$$

(where ${n-i \choose k} = 0$ if $n-i < k$).