The batched coupon collector problem is a generalization of the coupon collector problem. In this problem, there is a total of $n$ different coupons. The coupon collector gets a random batch of $b$ different coupons each time. What is the average number of batches required to collect all of the $n$ coupons? If $b=1$, this is the classic coupon collector problem.


There is an interesting answer (by Did) to a similar problem posed in [this link](https://math.stackexchange.com/questions/131664/coupon-collector-problem-with-batched-selections) . But this answer does not work for the case of $k=n$ (where $k$ is the number of different coupons collected). It is mentioned there that it is unclear on how to find $E\_{b,n}(T\_k)$. How about $E\_{b,n}[T\_n]$?



Batched Coupon Collector Problem
*Note. At the time of writing, the accepted answer to this question was that of Douglas Zare.*


The accepted answer to this question is incorrect, albeit for what appears to be a relatively minor reason. I discovered this while answering a special case of the same question over at [math.SE](https://math.stackexchange.com/questions/3278200/box-of-10-chocolates/3278285#3278230), where it was observed that in the special case $b=3$ and $n=10$, the formula from this post gave an absurdly large value.


After consulting the literature myself, I found the correct formula in Theorem 2 of [Stadje [1990]](https://math.stackexchange.com/questions/3278200/box-of-10-chocolates/3278285#3278230) (specifically equation (2.15) therein) with $p=1$ and $l=s=n$ and $m=b$. The desired expectation equals
$$
\binom{n}{b}\sum\_{j=0}^{n-1}\frac{(-1)^{n-j+1}\binom{n}{j}}{\binom{n}{b}-\binom{j}{b}}.
$$


Comparing this formula with the (incorrect) one from the accepted answer, we change variables in the sum to $s=n-j$, yielding


$$
\sum\_{s=1}^{n}\frac{(-1)^{s+1}\binom{n}{s}}{1-\binom{n-s}{b}/\binom{n}{b}},
$$
whereas the **incorrect** accepted answer states
$$
\sum\_{s=1}^{n-b}\frac{(-1)^{s+1}\binom{n}{s}}{1-\binom{n-s}{b}/\binom{n}{b}}.
$$
The only difference is in the range of the summation, and it arises due to a mistake made by the accepted answer in the $i=0$ case of the following manipulation:
$$
\sum\_{S\not=\varnothing}(-1)^{|S|+1}\left(\frac{\binom{n-|S|}{b}}{\binom{n}{b}}\right)^i\overset{!}{=}\sum\_{s=1}^{n-b}(-1)^{s+1}\binom{n}{s}\left(\frac{\binom{n-s}{b}}{\binom{n}{b}}\right)^i.
$$
The equality holds when $i\not=0$, but when $i=0$ the terms with $s>n-b$ do in fact contribute. The corrected formula reads as follows:
$$
\sum\_{S\not=\varnothing}(-1)^{|S|+1}\left(\frac{\binom{n-|S|}{b}}{\binom{n}{b}}\right)^i=\sum\_{s=1}^{n}(-1)^{s+1}\binom{n}{s}\left(\frac{\binom{n-s}{b}}{\binom{n}{b}}\right)^i.
$$
The rest of the reasoning in the accepted answer is correct, and with this fix yields the correct answer.


