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