0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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