1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ When I look at this post, I see eight-digit numbers such as $12341234$ rather than four-digit numbers such as $1234$. $\endgroup$ – N. F. Taussig Nov 17 '15 at 10:01
  • $\begingroup$ Fixed the examples, posted this late at night. Thanks @N.F.Taussig $\endgroup$ – José Pedro Marques Nov 17 '15 at 10:37
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Thanks for the explanation! The first one really changed the way I looked at the problem, and allowed me to compute the generic formula! Thanks! $\endgroup$ – José Pedro Marques Nov 17 '15 at 13:27

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.