Probability that $k$ random subsets of a fixed size covers a set Let $A=\{1,\ldots,n\}$. Now, we uniformly randomly select $k$ subsets, $A_i$ of size $d$ from $A$. What is the probability that $\bigcup_i A_i=A$? This seems to be natural variant of the set cover problem.
 A: For $i\in[k]:=\{1,\dots,k\}$ and $j\in[n]$, let $B_{i,j}$ denote the event that $j$ is in the random set $A_i$:
\begin{equation}
    B_{i,j}:=\{j\in A_i\}. 
\end{equation}
We need to find $P(B)$, where
\begin{equation}
    B:=\bigcap_{j\in[n]}\bigcup_{i\in[k]}B_{i,j}. 
\end{equation}
By the de Morgan rule,
\begin{equation}
    B^c=\bigcup_{j\in[n]}C_j,\quad\text{where}\quad C_j:=\bigcap_{i\in[k]}B_{i,j}^c.  
\end{equation}
So, by inclusion-exclusion,
\begin{equation}
P(B^c)=\sum_{r=1}^n(-1)^{r-1}\sum_{J\in\binom{[n]}r}
P\Big(\bigcap_{j\in J}C_j\Big), 
\end{equation}
where $\binom{[n]}r$ is the set of all subsets of $[n]$ of cardinality $r$.
In turn, if $J\in\binom{[n]}r$, then
\begin{equation}
    P\Big(\bigcap_{j\in J}C_j\Big)=P\Big(\bigcap_{i\in[k]}\bigcap_{j\in J}B_{i,j}^c\Big)
    =P\Big(\bigcap_{j\in J}B_{1,j}^c\Big)^k,
\end{equation}
by the independence of the $A_i$'s, and
\begin{equation}
    P\Big(\bigcap_{j\in J}B_{1,j}^c\Big)=P\big(A_1\cap J=\emptyset\big)
    =\binom{n-r}d\Big/\binom nd. 
\end{equation}
Thus, the probability in question is
\begin{equation}
\begin{aligned}
    P(B)&=1-\sum_{r=1}^n(-1)^{r-1}\binom nr \binom{n-r}d^k\Big/\binom nd^k \\ 
    &=\sum_{r=0}^n(-1)^r\binom nr \binom{n-r}d^k\Big/\binom nd^k. 
\end{aligned}
\end{equation}

The latter expression is probably impossible to simplify in general.
Mathematica can do nothing with it even for $k=2$ (click on the image to enlarge it):

Here is the table of values of $P(B)$ for $k=2$ and $n,d$ such that $1\le d\le n\le10$ (click on the image to enlarge it):

A: For $k = 2$ the answer is $\frac{\binom{d}{2 d - n}}{\binom{n}{d}} = \frac{\binom{d}{n - d}}{\binom{n}{n - d}}$.
Proof: without loss of generality, we can assume that the first set is $\{ n - d + 1, \dots, n\}$ and the question is now what is the probability that a subset of $\{ 1, \dots, n \}$ of size $d$ contains $\{ 1, \dots, n - d \}$, which is evidently what I said.
Now let us try for $k = 3$. Once again we can assume that the first set is $\{ n - d + 1, \dots, n\}$. Splitting into cases depending on the size of the intersection of the second set with $\{ 1, \dots, n - d \}$ the probability is equal to
$$\frac{1}{\binom{n}{d}^2} \sum_{k = 0}^{n - d} \binom{n - d}{k} \binom{d}{d - k} \binom{d + k}{2 d + k - n}$$
In general, one can get a certain multiple sum by splitting into cases depending on the size of the intersection of $A_i$ with the complement of the union of $A_1, \dots, A_{i - 1}$, but for $k > 2$ it doesn't appear to give an expression simpler than the one in Iosif's answer.
A: The case of $d=1$ is the classic coupon collector's problem . Of course inclusion exclusion applies, but it does not give an answer one can do much with. The expected number of selections until everything is covered has a nice expression.  Oversimplifying quite a bit, the expected number of trials is around $n \ln{n}$. The probability of succeeding with $n\ln{n}+cn$ selections converges to $e^{-e^{-c}}$ so about $87\%$ and $95\%$ for $c=2$ and $c=3.$
You could study what was done there and see what you can do for $d>1.$
The probability of succeeding with $k$ $d$-sets is better than the probability of succeeding with $kd$ $1$-sets. So that gives bounds. For small $d$ and large $n$ they might be close.
