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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|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
@perfect6 If you insist on doing it without order, that's fine. The quotient probability measure will give the same answer. It just won't have a uniform law anymore. For example, for $k=3$ the unordered $k$-tuple {9,9,9} is obviously much less likely than the unordered $k$-tuple {1,2,3} (there's only one way to pick {9, 9, 9}, but six ways to pick {1, 2, 3}). The problem tells you that the P-measure is the $k$-fold product of the uniform P-measure on 0 through 9, so dinoboy used that directly. You are welcome to pass through the quotient if you like to make your work harder for yourself. – Marcel T. Nov 16 '14 at 2:23

Your Answer


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.