Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Assume I have a set of 20 numbers. Each number in the set is unique. I am able to retrieve one number at a time from the set with the probability of retrieving any one member of the set being equal. How would I go about determining the probability that after ten random retrievals with replacement (i.e. a retrieval does not remove a number from the set) I would have 10 unique members?

Many thanks for your assistance.

share|improve this question
add comment

2 Answers

up vote 8 down vote accepted

We give three not very different arguments. The first two use counting, and the third works directly with probabilities.

Let us record the numbers that we get as a sequence of length $10$. So the sequence $(a_1, a_2, \dots, a_n)$ means that we got $a_1$ on the first pick, $a_2$ on the second pick, and so on.

There are $20^{10}$ such sequences, all equally likely, since we are replacing at each stage.

Suppose that we will be happy only if all the numbers are different.

Any of the $20$ numbers is fine for $a_1$. But for every choice of $a_1$, there are only $19$ values of $a_2$ that keep us hoping, for a total of $(20)(19)$ choices for $(a_1,a_2)$. But for every such choice of $(a_1,a_2)$, there are only $18$ values of $a_3$ that keep us hoping, for a total of $(20)(19)(18)$ choices for $(a_1,a_2,a_3)$. Continue.

We find that there are $(20)(19)(18)\cdots (12)(11)$ sequences of length $10$ that make us happy. Thus the required probability is $$\frac{(20)(19)(18)\cdots (12)(11)}{20^{10}}.$$

Another way: We count again the number of sequences of length $10$ that make us happy. Call a string of length $10$ good if all its entries are different. The numbers that appear in a good string can be chosen in $\dbinom{20}{10}$ ways. Here $\dbinom{n}{r}$ is the number of ways to choose $r$ objects from $n$ distinct objects. On scientific calculators, the label is ${}_nC_r$.

For every choice of the $10$ distinct numbers, these numbers can be lined up in a row in $10!$ ways. So there are $\dbinom{20}{10}10!$ good sequences of length $10$. The probability we will be happy is therefore $$\frac{\binom{20}{10}10!}{20^{10}}.$$

Still another way: We can work directly with probabilities. The probability that we are still hopeful after the second draw is $\dfrac{19}{20}$.

Given that we are still hopeful after the second draw, the probability we are hopeful after the third draw is $\dfrac{18}{20}$. So the probability that we are still hopeful after the third draw is $\dfrac{19}{20}\cdot\dfrac{18}{20}$.

Continue. The probability that we get $10$ distinct integers is $$\frac{19}{20}\cdot\frac{18}{20}\cdot\frac{17}{20} \cdots\frac{12}{20}\cdot\frac{11}{20}.$$ We can make the answer look nicer, at least to a mathematician, by putting a $\dfrac{20}{20}$ at the front.

share|improve this answer
add comment

The first selection will have $20$ possibilities, the next selection $19$ possibilities, and so on until the $10$-th selection has $11$ possibilities. The total number of ways of to choose a ball from these possibilities each time is $20\cdot19\cdots12\cdot11$. The total number of ways to choose $10$ balls at all is $20^{10}$. So you're looking at

$$P=\frac{20!}{10! 20^{10}}\approx 0.0655.$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.