0
$\begingroup$

Suppose $S$ is a set with $n$ elements. Let $U=\{T|T\subseteq S\text{ and }|T|=k\}$, i.e., $U$ is the set of all possible subsets of $S$ with cardinality $k$. Clearly $|U|=\binom{n}{k}$. Then how many ways are there to select $m$ subsets, such that the union of these subsets is $S$?

My attempt basically takes advantage of the inclusion-exclusion principle. The number of distinct ways to select $m$ subsets from $U$ is $$\binom{\binom{n}{k}}{m}.$$ We subtract the combination of subsets which does not include one element of $S$. For $x\in S$, the number of subsets which does not contain $x$ is $\binom{n-1}{k}$, so we should subtract $$n\binom{\binom{n-1}{k}}{m}.$$ We then add the combinations that does not include two elements of $S$. Similarly, we add $$\binom{n}{2}\binom{\binom{n-2}{k}}{m}.$$ Repeat this procedure until $\binom{n-j}{k}<m$, where $j$ is the number of elements in $S$ that are not contained in the subset. So, at last, the answer to the problem is $$\Large\sum\limits_{\begin{matrix}j=0\\\binom{n-j}{k}\ge m\end{matrix}}^{n}{(-1)}^j\binom{n}{j}\binom{\binom{n-j}{k}}{m}.$$ But I'm not quite satisfied to this answer. Is there a closed form of this expression? Or has this problem be well-studied? Thanks.

$\endgroup$
3
  • 2
    $\begingroup$ I am pretty certain you have found the most satisfying form of the answer. There is one mistake; you forgot the $(-1)^j$ factor. Less importantly, there is no need to specify $\binom{n-j}k\ge m$ in the subscript; any terms with $\binom{n-j}k<m$ are automatically zero, so there is no harm in including them. $\endgroup$ Jul 8, 2023 at 16:19
  • 1
    $\begingroup$ This answer comes to the same conclusion. $\endgroup$ Jul 8, 2023 at 16:21
  • $\begingroup$ @MikeEarnest Thanks, I've fixed the formula. $\endgroup$
    – Soha
    Jul 9, 2023 at 2:59

0

You must log in to answer this question.