Skip to main content
2 of 5
added 18 characters in body

Partitioning the coupons collected in the classical coupon collector's problem

Suppose that there is an urn containing $n$ different coupons, from which $m$ coupons are being collected, equally likely, with replacement.

Let $\mathcal{P}(m)$ be the set of all the partitions of the whole set of the $m$ collected coupons. Let $\mathcal{P}_k(m)$ be the subset of $\mathcal{P}(m)$ where in all partitions $P \in \mathcal{P}_k(m)$, for each coupon subset $S \in P$, (i) all coupon types in $S$ are distinct, and (ii) $|S| \le k$.

Questions: What is the mimimum cardinality of a partition in $\mathcal{P}_k(m)$ (in expectation)? What is the maximum number of coupon subsets having size equal to $k$ of a partition in $\mathcal{P}_k(m)$ (in expectation)?