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.

Suppose $k$ digits are chosen at random (with replacement) from the set $\{0, 1, 2, \ldots, 9\}$. What is the probability that $0$ will not be chosen?

In several other counting probability problems, one can formulate the answer in terms of permutations and combinations. To illustrate this, the common example I've found is the blue and red marble problem. So given $10$ marbles, $6$ being red, and $4$ being blue, one can say that the probability of picking $2$ blue marbles is $\frac{4 \choose 2}{10 \choose 2}$, or equivalently, we can say it's $\frac{4 \times 3}{10 \times 9}$.

Now the difference between the two problems is that we are considering choices with replacement in the title problem. I was able to solve it using the permutation formulation, namely by saying that out of $10^k$ possible length-k strings, we have $9^k$ possible length-k strings not containing zero, and thus the solution is $(\frac{9}{10})^k$.

Now I am interested in reaching this answer using combinations. First, is that possible? If so, then the only relevant fact that I can think of is that the number of length-$k$ subsets of an $n$-set with replacement is given by ${n+k-1 \choose k}$. However I don't seem to be able to come up with the correct way of formulating the solution using combinations. Any hints?

share|improve this question

1 Answer 1

Its because you aren't accounting for order. Suppose we take $k=2$. Then it is clear there should be $100$ different sets of $2$ digits you can pick. However, $\dbinom{10+2-1}{2} = 55$, which is not $100$.

The correct way to do this is there are $10^k$ selections from the ten digit set. However, there are only $9^k$ ways to pick from the set once $0$ is removed. Thus the probability is $\frac{9^k}{10^k}$ as desired.

share|improve this answer
    
Unfortunately I am not satisfied that it's an order thing. I've seen examples where both interpretations work (ordered and unordered), but the difference is that those examples didn't consider repetition as in the above question. –  perfect6 Oct 31 '12 at 23:21
    
Ordering is definitely the reason. The derivation for above formulas completely breaks down when you care about the order of the objects. And its not it breaks down to just a $k!$ term in front, it gets very ugly because not every set of numbers can be reshuffled in the same number of ways. –  dinoboy Oct 31 '12 at 23:32

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.