Let's call n an ascending number, if it has the following 2 properties:

- The number n has at least 2 digits.
- All digits of n are in ascending order, in base 10.

How many ascending numbers are there?

We must assume that ascending order means strictly ascending, that is, with no repeats, as repeats, such as in 2445, could be strung out indefinitely. Also, I'll assume we don't put a leading zero on any number, but we can adjust the answer for that possibility later.

Since zeros are out in the first position, they are out everywhere as the digits are in ascending order. Each of the nine remaining digits can appear either zero or one time in the number, so this is just the task of finding the number subsets of nine things and then subtracting out those with zero or one element.

There are 2^9 subsets of nine things, or 512. There's one empty subset and nine with just one element (digit), leaving 502 subsets, each to be arranged in ascending sequence.

So there are 502 such numbers. If we allow a leading zero, any one of these can be preceded by a zero, bringing the total so far to 1004, but we can also precede a zero to the single-digit numbers, bringing that total to 1013.

So: without leading zeros, it's 502; with leading zeros it's 1013.

Posted by Charlie on 2003-05-25 05:26:17