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.

2,505,433,700

10 1-digit numbers (0,1,2,3,4,5,6,7,8,9).

45 2-digit numbers (11,12,...,19,22,23,...,29,...,88,89,99).  Of those, 9 are in the 10s, 8 are in the 20s, 7 are in the 30s,...,2 are in the 80s, and 1 is in the 90s.

165 3-digit numbers.  There are 45 (or 9+8+7+6+5+4+3+2+1) starting with 1, 36 (or 8+7+6+5+4+3+2+1) starting with 2, 28 (or 7+6+5+4+3+2+1) starting with 3,...,3 (or 2+1) starting with 8, and only 1 starting with 9.

...

450,978,066 41-digit numbers.

Edited on May 29, 2007, 4:39 pm

Posted by Guest on 2007-05-29 16:31:48