There are n balls in a jar labeled with numbers 1,2,...,n. A total of k balls are drawn WITH REPLACEMENT.

Question

There are n balls in a jar, labeled with the numbers 1, 2, . . . , n. A total of k balls are drawn, one by one with replacement, to obtain a sequence of numbers.

What is the probability that the sequence obtained is strictly increasing?

For this problem since you are dealing with replacement, there are $n^k$ ways of selecting the balls. THe key observation, is that if you draw a repeated ball with a number already selected, you can not have a strictly increasing sequence.

THere are ${n \choose k}$ ways of selecting balls with $n^k$ total possibilities. however you are interested only in a one sequential ordering of the labels (increasing) so Probability of strictly increasing: $ \frac{ {n\choose k }}{k!n^k}$

If you have 3 numbered balls (1,2,3), and you draw $\textbf{WITH REPLACEMENT}$, then you have a 3 X 3 square. The diagonal represents a repeated ball,label, pulled. The upper-triangle represents the sequential increasing outcome space of interest $\{ (1,2), (1,3), (2,3) \}$ from total possibilities of 9. dividing the equation by 2! represents selecting only the upper-triangle and not the lower triangle $\{(2,1), (3,1), (3,2)\}$

This is more of a discussion, to check as to whether this reasoning is correct? thank you very much

Answer 1

There is a more simple way of looking at this. For any set of distinct integers, for example, $1, 7, 2, 8$, there is a single ordering of these numbers that is strictly increasing. You can convince yourself of this with a couple examples: $(5, 8, 0, -7, 23) \rightarrow (-7, 0, 5, 8, 23)$.

By this, we see that for any selection of k distinct integers from n possible integers, we can order them in exactly one way to ensure strictly increasing order. We can select k distinct integers from n possible integers $n \choose k$ different ways. For each of these, we implicitly order them in increasing order, and we have a solution.

Thus, the total strictly increasing orders are $n \choose k$ and as discussed in the original question, the total possible orderings of k numbers from n is $n^k$

Giving us an answer of $\frac{n\choose k}{n^k}$

Answer 2

Using the example with $n=3$ and $k=2,$ namely

\begin{align} \begin{bmatrix} (1,1) & (1,2) & (1,3) \\ (2,1) & (2,2) & (2,3) \\ (3,1) & (3,2) & (3,3) \end{bmatrix}, \end{align} the derived expression gives probability: $\frac{\binom{3}{2}}{2!3^{2}} = \frac{1}{6}.$ However, we observe three outcomes in the event $(1,2), (1,3),$ and $(2,3)$ and nine outcomes in the sample space. Hence, the probability is $\frac{1}{3}.$

The example shows that the $k!$ term in the denominator is incorrect. Hence, the solution is $\frac{\binom{n}{k}}{n^{k}}.$

There is also the following solution by Newb, which describes the numerator $\binom{n}{k}.$