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

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

• The correct probability, with replacement, is $\binom{n+k-1}{k}/n^k$. The numerator counts the number of ways to select $k$ elements from an $n$ element sets, where order does not matter, but repeats are allowed. Aug 29 '18 at 17:59
• @MikeEarnest: That's for weakly increasing; the question is about strixtly increasing. Aug 30 '18 at 2:49
• @joriki You are right, I was confused. Aug 30 '18 at 4:03

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}.$$