Q: How many positive integers are there whose digits strictly increase from left to right? ($0$ is not allowed to be the leading digit)
Here're my thoughts on the problem.
For one digit numbers.
There are only $9$ such integers that satisfy the problem.
For two digit numbers.
If we start with $1$ as the left most digit, then we have $8$ choices for the one's place. So we have $8$ such numbers.
If we start with $2$ as the left most digit, then we have $7$ choices for the one's place.
If we start with $3$ as the left most digit, then we have $6$ choices for the ones place.
Continuing this process we have $8+7+6+ … +2+1 = 36$ such numbers.
But for three – digit numbers, I'm stuck. What am I suppose to do, after I've chosen the first digit? I'll have to make sub cases for the second digit, and it'll get more complicated as I go up to 9 – digit numbers.
P.S. I know we have a question such as [Number of strictly increasing and decreasing 4 digit numbers?], but I don't quite get the hints …
Best Answer
An easier approach is to see there is one such integer for each nonempty subset of $\{1,2,3,4,5,6,7,8,9\}$. Once you have a subset, you arrange the digits in increasing order, so there are $2^9-1$ integers with strictly increasing digits.