Imagine two sets $A = \{1, 2, \dots, a\}$ and $B = \{1, 2, 3, \dots, b\}$ with $a \leq b$. Let $f$ be a uniformly independently distributed random map $f:A\rightarrow B$ and $F = \bigcup_{i=1}^a f_{i}$
If I pick different functions $f$ until I find one such that $|A| = |F|$ what is the expected number of functions I pick? What is the probability that none of the $p$ functions I pick first results in $|A| = |F|$?
This looks like a sampling problem? How to think about it?
Let $G$ denote the set of functions such that $|F|=a$. Since $|G|=b!/(b-a)!$, the event that a function is in $G$ has probability $$ q=\frac{b!}{(b-a)!b^a}. $$ The rank $N$ of the first function in $G$ is such that $P[N=n]=(1-q)^{n-1}q$, thus, $P[N\gt n]=(1-q)^n$, for every $n\geqslant1$.
Let $M$ denote the random set of the different functions not in $G$ picked before the first one in $G$. Any given function not in $G$ is in $M$ if and only if it was picked before any of the $|G|$ functions in $G$. This happens with probability $1/(|G|+1)$ and there are $b^a-|G|$ functions not in $G$, hence the expected size of $M$ is $(b^a-|G|)/(|G|+1)$. Thus, $$ E[|M|]=\frac{1-q}{b^{-a}+q}. $$ Edit: A new question asked in the comments is to compute $E[|F|]$. This can be done using the trick of evaluating the probability, for any given $f$, to be in $F$. Rather, the probability that $f$ is not in $F$ is $(1-b^{-a})^a$ hence $$ E[|F|]=\sum_fP[f\in F]=b^a(1-(1-b^{-a})^a). $$