# Marbles in a bag (Combinatorics)

There are 10 numbered from 1 to 10 marbles. The marbles are placed in an opaque bag and shuffled. One random marble is taken out, its number is written on a piece of paper, marble is then returned to the bag, marbles are shuffled again. Procedure is repeated, until 25 records are accumulated on the paper.

Question №1: what is the probability that paper now contains all numbers from 1 to 10, at least once?

Q №2: what is the average amount of numbers to be written in such a manner, until all numbers from 1 to 10 are recorded at least once?

P.S. I found correct numbers by using the Monte Carlo method, but interested in purely mathematical solution.

Update Since asking this, I've questioned friends and collegues, tried to receive correct solution for #1 at different websites, but it all failed for me. The Emperor of Ice Cream's answer, simply doesn't seem to be entirely correct, as it's outcome is fairly far from my simulation results (which was conducted again on rewired algorithm, only to see the same outcome).

We can set our probability space to be the set of functions from $[1,2,3\dots 25]$ to $[1,2,3\dots 10]$. We want to find the probability we get a surjective function. Using the twelvefold way there are $10! S(25,10)$ of these. Hence the probability is $\frac{10!S(25,10)}{10^{25}}\approx 0.437$

For the second question this is the coupon collector problem, answered brilliantly by Henning Makholm here.

Initially I misunderstood the second question and calculated the average number of different coupons you will draw:

$$\dfrac{\sum\limits_{i=1}^{10}i(\binom{10}{i}i!S(25,i))}{10^{25}}\approx$$

This is because there are $\binom{10}{i}i!S(25,i)$ functions which have a range with size $i$. This is because there are $\binom{10}{i}$ ways to select the range. And after this we use the same argument as above, because all functions are surjective on their image.

• Could there be some minor error? My simulation on 100k iterations resulted with ~0.48 Feb 24, 2015 at 16:09
• It's possible, I'm going to run the number again once I finish downloading sage on my computer Feb 24, 2015 at 16:12
• The second solution is sure totally correct, thank you :) Feb 24, 2015 at 17:44