2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.