Determine the total number of non-negative integers containing not more than 41 decimal digits but having non-decreasing digits.

For example, 33455 is a valid instance of such integers while 98 is not.

The number representation is a string of non-decreasing digits.  Other than the number 0, there are 9 possible digit values.  However, since we're considering all numerical sizes, from 1-digit to 41 digits, we can consider only 41-digit numbers, but allow leading zeros.  That is, for example, to consider 33455 as 00000000000000000000000000000000000033455; it counts as one representation either way.

Consider a series of 41 x's, letting each x represent a digit position. Initially assume that it starts with zero, but place among the 41 placeholders for digits, nine separators (|).  Each separator signals to advance the next x to the next higher valued digit.  If it's a fully 41-digit number with no leading zeros for example, the string would begin with one or more placeholders. For example, the 33455 would be represented as

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|||xx|x|xx||||

The 36 leading x's represent leading zeros, as there is no | before them.  The |||, being three dividers in a row, increase the digit value by 3, to 3, so that the next two x's represent 3's. The single bar advances the consideration of the next x to be 4, and the next divider advances the consideration to 5 for the next two x's. The remaining four bars have no effect other than to signal no digit is higher than 5.

There's a 1-to-1 correspondence between these representations and the ordinary representation. The above is the only way that 33455 can be represented in this notation (given that nine |'s must always be present) and 33455 is the only interpretation that this string can have.

As we have 41 x's and 9 |'s, it's a matter of which tokens are x's and which are |'s. The number of these representations is C(50,9) = C(50,41) = 2,505,433,700.

The problem could have been worked out similarly, treating each number of digits separately, with no leading zeros, and adding the results for each set.  Each number of digits would have that many placeholders and only 8 dividers, and so would be C(n+8,8), including n=0 for the zero. Then we'd sum for n=0 to 41. 

Edited on May 29, 2007, 4:49 pm

Posted by Charlie on 2007-05-29 16:49:02