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

2 Answers 2

2
$\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$
1
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .