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?