Count the number of non-decreasing numbers with d digits, lower than X 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? 
 A: 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}$$ 
