Probability for an element to appear in at least one set Say that we have $k$ sets, each with cardinality $N$, where the elements in each set are taken at random from $M \ge N$ possible ones. The elements in each set are known to be distinct.

What is the probability that $j$ ($j=1,...,M$) elements appear at least once in the (union of the) sets?

We know that for $j = N$ the probability is $1$. For $j &gt; N$ I wanted to use the binomial distribution, but the parameter $p$ should be conditioned somehow on the number of elements that already appear in the sets. Should I use some recursive formula for this?

Edit:

(1) This maybe also be formulated as the famous balls in bins problem, with the twist that the balls are thrown $N$ at a time to $M$ bins, where it is known that each group of $N$ balls falls into distinct $N$ bins.

(2) Another option to see this is as the (extended) Coupon Collector's Problem, who acquires $N$ (instead of $1$) distinct coupons at a time, from a set of $M$ distinct coupons. Denoting by $W_t(j)$ the probability that he acquired $j$ distinct coupons at time $t$, my questions is what is the probability distribution of $W_t(j)$, for $j=N,N+1,...,M$, for each time (or set in the original formulation) $t=1,2,...,k$. I saw something relevant here:
https://math.stackexchange.com/questions/100175/probability-of-non-empty-bins-after-randomly-inserting-balls-by-pairs
For very crude bounds, you could use Chebyshev's inequality.

Let $x$ denote one (fixed) value from the set of $M$ possibilities.  The probability that $x$ appears at least once in the union of the sets is something like

$$p = 1 - \left({{M-1 \choose N} \over {M \choose N}}\right)^k.$$

Now if we let the random variable $X$ denote the number of elements that appear at least once in the union of the sets, we can use linearity of expectation to get that $\mathbb{E}[X] = Mp$.  You should be able to compute $\text{Var}[X]$ using similar methods.  Then, you should be able to use Chebyshev's inequality to bound the probability that $X$ is far away from its expected value.

This will give a pretty weak bound, so it's unlikely that this is the best approach.  Hopefully others will suggest better methods.