# Expected number of duplicates (triplicates etc) when drawing with replacement

I have the following problem:

I have 100 unique items (n), and I'm selecting 43 (m) of them one at a time (with replacement).

I need to solve for the expected number of uniques (only selected once, k = 1), doubles (selected exactly twice k = 2), tripples (exactly k =3), quads etc...

I've been able to find plenty of results on the probability of there being at least one double (birthday paradox), but not on the expected number of pairs in the population.

• Would a Monte Carlo estimate be useful to you, or do you need the answer in a closed form? – David J. Harris Apr 26 '13 at 15:56
• I would prefer a closed form formula so I can easily apply it to different values of n, m and k. – Kaitlyn K Apr 26 '13 at 17:04

The $i^{th}$ iterm will be selected $\text{Binom}(m, \, 1/n)$ times. From this, you can find all the quantities you want, because, e.g., $$\mathbb{E}[\text{number of pairs}] = \sum_{i = 1}^n \mathbb{P}[i^{th} \text{ item appears twice}]$$ For example, the expected number of pairs is given by $$n \cdot \mathbb{P}[\text{Binom}(m, \, 1/n) = 2].$$