medium   Probability

Non-Decreasing Numbers

A release-checked medium problem for training Stars and Bars.

Question

Fix $n \geq 1$. A sequence of digits $x_1x_2\dots x_n$ is said to be $\textit{non-decreasing}$ if $x_i \leq x_{i+1}$ for $1 \leq i \leq n-1$ and each $0 \leq x_i \leq 9$. How many non-decreasing $n$ digit strings exist when $n = 8$? There are no restrictions on how many times a digit can be used, and strings are allowed to start with $0$. Some examples with $n = 8$ are $00112234, 11111111,$ and $15678999$.

Practice focus

This Probability problem is tagged Stars and Bars. State the random variables and conditioning information explicitly, then check the result against boundary cases before opening hints or a solution.

Reviewed questions in this area

easyBaby BoyReviewed

Probability · SIG, DE Shaw

easyBad BagelReviewed

Probability · SIG, Jane Street