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

  • 1
    $\begingroup$ 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. $\endgroup$ Aug 29, 2018 at 17:59
  • 1
    $\begingroup$ @MikeEarnest: That's for weakly increasing; the question is about strixtly increasing. $\endgroup$
    – joriki
    Aug 30, 2018 at 2:49
  • $\begingroup$ @joriki You are right, I was confused. $\endgroup$ Aug 30, 2018 at 4:03

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.