This one has to do with combinatorics and we use the good old fashion binomial coefficient identity (built from factorials or Bang!). Any increasing number can be represented using binary strings. For example, all 3-digit increasing numbers using 0, 1, 2 can be represented with 5-digit binary numbers:
11100 = 000 11010 = 001 11001 = 002 10110 = 011 10101 = 012 10011 = 022 01110 = 111 01101 = 112 01011 = 122 00111 = 222
Which means that there are (5 choose 3) - 1 = 9 of these numbers. The reason for subtracting 1 is that we don’t want to count the number “000”. By extension, all 3-digit increasing numbers with the digits 0-9 requires a binary string containing 3 ones and 9 zeroes and so on. The same can be extended to 10^100.
For decreasing numbers, the only difference is that we might have a zero in the front and end of the string. Note the following pattern of zeros.
111000 = 000 110100 = 002 110010 = 001 110001 = 000 * 101100 = 022 101010 = 021 101001 = 020 100110 = 011 100101 = 010 100011 = 000 * 011100 = 222 011010 = 221 011001 = 220 010110 = 211 010101 = 210 010011 = 200 001110 = 111 001101 = 110 001011 = 100 000111 = 000 *
You can see for 3-digit numbers that “000” will be repeated 3 times after the initial time. For an n-digit number the pattern repeats n times. This gives us (n+10 choose 10) -1 -n. Additionally, numbers like 222 and 11 have both properties. Since we have counted them twice, they need to be removed. There are 9*100 of these numbers which are counted twice.
Here's the Python code. Its pretty short since we've simplified everything down to a couple binomial calculations.
def bang (x): return x > 1 and x * bang (x - 1) or 1 def choose (n, k): return bang (n) / (bang (k) * bang (n-k)) if __name__ == "__main__": print (int (choose (110, 10) + choose (109, 9) - 1002))