# A generalization of coupon collector problem - $\geq1$ pick per experiment

Mix $T\geq1$ coupons numbered $1$ to $T$ with a set of $S\geq0$ number of dummy coupons with no numbers. Select $N\geq1$ coupons at each trial at random and put them back.

$N=1$ is standard coupon collector problem. I have not seen any reference for $N>1$.

1. What is the probability that after $k$ trials you selected each coupon from $1$ to $T$ at least once?

2. What is the expected number of trials one needs to select each coupon from $1$ to $T$ at least once with probability $1-\frac{1}{c}$ for some $c>1$?

3. Fix a coupon $x_t\in\{1,\dots,T\}$. How many trials to do you expect to have to select this particular coupon at least once with probability $1-\frac{1}{c}$ for some $c>1$?

I am looking for sharp asymptotics.

• Not an asymptotic but exact answer for question 1: $$\binom{T+S}{N}^{-k} \sum_{i=0}^T (-1)^i \binom{T}{i} \binom{T-i+S}{N}^k.$$ – Max Alekseyev Aug 18 '15 at 18:42
• If $N=1$ then the expectation is $(S+T)H_T$ – Henry Aug 18 '15 at 20:16
• @Henry Yes. $N=1$ is standard. What about $N>1$? – user76479 Aug 19 '15 at 1:21
• @MaxAlekseyev I am not getting prob <1? Could you write your proof? – user76479 Aug 19 '15 at 1:44
• @Arul: What are your numerical values? The formula follows from the inclusion-exclusion principle. – Max Alekseyev Aug 19 '15 at 2:06