3
$\begingroup$

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\}$.

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – Henry Apr 15 '18 at 18:09
  • $\begingroup$ OK Henry, done. $\endgroup$ – Penelope Benenati Apr 16 '18 at 16:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.