# How to find the number of $5$-digit numbers whose digits are nondecreasing

I was working on a problem:

"Find the number of those $$5$$-digit numbers whose digits are non-decreasing."

I was able to calculate the number of decreasing $$5$$-digit numbers, which I found to be $$252$$. I subtracted this from $$90,000$$ five-digit numbers to obtain an answer of $$89,748$$. However, I am unsure whether this is correct. Can anyone confirm?

$$89748$$ numbers is way too large. Here is the correct derivation.

Zero cannot be in any of the five-digit numbers in question. If there was one, there would have to be zeros all the way left, making it not five-digit.

Any admissible such number thus corresponds to a choice of five digits from $$1$$ to $$9$$, possibly with repetition, but where order does not matter. By stars and bars the count of such choices, and thus the number of admissible numbers, is $$\binom{5+9-1}5=\binom{13}5=1287$$

The flaw in your attempt is that not every number whose digits are not strictly decreasing has nondecreasing digits. For instance, the number $$32856$$ is a five-digit number with digits that are not strictly decreasing. However, it is also a number in which the digits are not nondecreasing.

A five-digit number in which the digits are nondecreasing is completely determined by how many times each digit appears. For instance, if $$2$$ appears once, $$3$$ appears twice, $$5$$ appears once, and $$7$$ appears once, the number must be $$23357$$.

Notice that if $$0$$ did appear in a five-digit number with nondecreasing digits, it would have to be the leading digit, making the number less than five digits. Therefore, $$0$$ cannot appear in a five-digit number with nondecreasing digits.

Since the leading digit of a five-digit number cannot be zero, the number of five-digit numbers with nondecreasing digits is the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 5 \tag{1}$$ in the nonnegative integers, where $$x_i$$ is the number of times digit $$i$$ appears in the number.

A particular solution of equation 1 corresponds to the placement of $$9 - 1 = 8$$ addition signs in a row of five ones. For instance, $$+ 1 + 1 1 + + 1 + + 1 + +$$ corresponds to the solution $$x_1 = 0$$, $$x_2 = 1$$, $$x_3 = 2$$, $$x_4 = 0$$, $$x_5 = 1$$, $$x_6 = 0$$, $$x_7 = 1$$, $$x_8 = 0$$, $$x_9 = 0$$, and the number with nondecreasing digits $$23357$$.

The number of solutions of equation 1 is the number of ways we can place eight addition signs in a row of five ones, which is $$\binom{5 + 9 - 1}{9 - 1} = \binom{13}{8}$$ since we must choose which eight of the thirteen positions required for five ones and eight addition signs will be filled with addition signs.