1
$\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$. Let $1\leq r\leq \binom{n}{k}$. Among the $\dbinom{\binom{n}{k}}{r}$ subsets of $\mathcal{F}$ of size $r$, how many subsets contain subsets of $A$ whose union is $A$?

This is related to this question, which looks at all subsets of $\mathcal{F}$ instead of just subsets of size $r$. We can try to use inclusion-exclusion. For that, we'll need to calculate the number of subsets of $\mathcal{F}$ of size $r$ whose union do not contain some fixed element $a\in A$. But this doesn't seem as easy as in the linked question.

$\endgroup$

1 Answer 1

2
$\begingroup$

Fix $a\in A$; there are $\binom{n-1}k$ members of $\mathscr{F}$ not containing $a$, so there are $\binom{\binom{n-1}k}r$ $r$-subsets of $\mathscr{F}$ whose unions do not contain $a$. More generally, if $S\subseteq A$, and $|S|=m$, there are $\binom{\binom{n-m}k}r$ $r$-subsets of $\mathscr{F}$ whose unions are disjoint from $S$. Now repeat the inclusion-exclusion argument to get

$$\sum_j\binom{n}j(-1)^j\binom{\binom{n-j}k}r\;.$$

$\endgroup$
1
  • $\begingroup$ You're right. I tried but got confused. It's actually much easier to find that I thought. $\endgroup$
    – Alexi
    Commented Sep 10, 2015 at 6:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .