# 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 $C(m)$ be the whole set of the $m$ collected coupons. Let $\mathcal{P}_k(m)$ be the subset of all partitions of $C(m)$ where in all partitions $P \in \mathcal{P}_k(m)$, for each coupon subset $S \in P$, we have: (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)?

Toy example: m=10, n=3, k=2. Multiset of coupon types collected after sampling $m$ coupons once: $C(m)=\{1, 1, 1, 1, 1, 1, 2, 2, 2, 3\}$. Mimimum cardinality of a partition in $\mathcal{P}_k(m)$: $6$. Maximum number of coupon subsets having size equal to $k$ of a partition in $\mathcal{P}_k(m)$: $4$. Partition example: $\{1, 2\}$, $\{1, 2\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1\}$, $\{1\}$.

• Could you give a toy example with small $m$ and $n$ so your definitions are clearer? For example $m=3$, $n=2$ and $k=1,2$ – Henry Apr 15 '18 at 18:09
• OK Henry, done. – Penelope Benenati Apr 16 '18 at 16:27