Count the number of non-decreasing numbers with d digits, lower than X

Question

A number is said to be made up of non-decreasing digits if all the digits to the left of any digit is less than or equal to that digit.

For example, the four-digit number 1234 is composed of digits that are non-decreasing. Some other four-digit numbers that are composed of non-decreasing digits are 0011, 1111, 1112, 1122, 2223.

Notice that leading zeroes are required: 0000, 0001, 0002 are all valid four-digit numbers with non-decreasing digits.

I arrived at the conclusion that there are in total $$\sum_{l=0}^9 \sum_{k=0}^l \sum_{j=0}^k ... \sum_{a=0}^b 1 = \binom{9+d}{d}$$ ways to calculate the non decreasing numbers, for d digits, without constrains.

My question is, suppose I want to find the number of non-decreasing numbers with D digits, under a given limit (in the same order of magnitude). For example, how many 4 digit numbers are non-decreasing and under 5000?

I realize that for this case, I need this summations, but I can't neither figure out how to solve them, nor how to generalize them $$\sum_{l=0}^9 \sum_{k=0}^l \sum_{j=0}^k\sum_{i=0}^{min(5,j)} 1 $$

where I limit this first number to 5.

Any help?

Answer 1

We can represent a number with non-decreasing digits by placing vertical bars in a string of nine ones. The number of ones to the left of the vertical bar represents the digit. For instance, $$| 1 1 1 | | 1 1 1 1 1 1 |$$ represents the number $0339$, while $$1 1 | 1 1 | 1 1 | 1 1 | 1$$ represents the number $2468$. Since a particular number is determined by which four of the thirteen symbols (four vertical bars and nine ones) are vertical bars, the number of non-decreasing numbers with four digits (including leading zeros) is $$\binom{13}{4} = \binom{13}{9}$$ as you found. To determine how many four-digit numbers (including those with leading zeros) are less than $5000$, we must subtract from these those non-decreasing four-digit numbers that are at least $5000$. Notice that in those non-decreasing four-digit numbers that are at least $5000$, the first vertical bar must be placed to the right of at least five ones. For instance, $$1 1 1 1 1 | | 1 | 1 | 1 1$$ represents the number $5567$. Since a particular non-decreasing four-digit number that is at least $5000$ is determined by which four of the last eight symbols (four vertical bars and four ones) are vertical bars, the number of non-decreasing four-digit numbers that are at least $5000$ is $$\binom{8}{4}$$ Hence, there are $$\binom{13}{4} - \binom{8}{4}$$ non-decreasing four-digit numbers, including those with leading zeros, that are less than $5000$.

Alternate Method: A non-decreasing number is completely characterized by the number of times each digit appears. Let $x_k$ represent the number of times the digit $k$ appears in the non-decreasing four-digit number, including those with leading zeros. Since there are four digits, $$x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 4$$ A particular number is determined by which nine of the thirteen symbols (nine addition signs and four ones) is an addition sign. For instance, $$1 + + + 1 1 + + + + + + 1$$ represents the number $0339$, while $$+ + 1 + + 1 + + 1 + + 1 +$$ represents the number $2468$. Thus, the total number of non-decreasing four-digit numbers is the number of ways nine addition signs can be placed in a row of four ones, which is $$\binom{4 + 9}{9} = \binom{13}{9}$$ From these, we subtract those non-decreasing four-digit numbers that are at least $5000$. The digits of non-decreasing four-digit numbers that are at least $5000$ satisfy the equation $$x_5 + x_6 + x_7 + x_8 + x_9 = 4$$ A particular number is determined by which four of the eight symbols (four addition signs and four ones) is an addition sign. Hence, there are $$\binom{4 + 4}{4} = \binom{8}{4}$$ non-decreasing four-digit numbers that are at least $5000$. Hence, the number of non-decreasing four-digit numbers that are less than $5000$, including those with leading zeros, is $$\binom{13}{9} - \binom{8}{4}$$