How many players to play coupon collector without replacement so they collect all type of coupons

57 Views Asked by At

I am looking into something similar to coupon collector's problem but with some modifications and changing the question.

Actual problem: I have $N$ nodes in a graph and these nodes come from $C$ distinct clusters of size $|C_j|$. I want to randomly partition the nodes into $M$ parts but I need each partition to have instances of all clusters. Definitely if I choose $M=1$ the only partition I make will have at least a member of each cluster but I am wondering how large can I choose the parameter $M$. It seems that the answer depends on the size of the smallest cluster with size $|C_{smallest}|$.

I think the translation to coupons collector's would be: How many players could play coupon game without replacement with $C$ coupons $|C_j|$ instances of each coupon, so they can all collect all coupons after all the instances being assigned to the players.