# How many total increasing numbers are there?

I've been asked this question and I'm close but just can't figure it out.

To clarify, an "increasing number" has to have increasing digits from left to right and cannot repeat digits anywhere else in the number.

So an increasing number would be considered 12, or 125, or 2469; however, numbers that repeat certain digits such as 112 and/or numbers that fall such as 453 or 5498 are not increasing numbers.

An increasing number cannot begin with 0.

Single digits do count as an increasing number (1 or 9 would both be considered increasing numbers).

With the largest increasing number being 123456789, how many total increasing numbers are there?

Assuming single digits count as total increasing numbers, a total increasing number is given by its set of digits. Thus, there is a total increasing number for each subset of $\{1,2,3,4,5,6,7,8,9\}$, including the empty set (which corresponds to the number $0$). Thus there are $2^9 = 512$ such numbers.

If single digits do not count, we have overcounted by 10, and there are $502$ such numbers.

Edit (after a minor change to the question): The final answer depends on if $0$ counts (since you specified "numbers cannot begin with a $0$"). If it counts, there are $512$. If it does not, there are $511$.

• Was a little confused at first, but I eventually got it with the help of Doug. Thanks! – Dr. Tan Sep 6 '16 at 23:53

The trivial 1 digit numbers... there are 9 of them.

There are ${9\choose 2}, 2$ digit numbers.

${9\choose n}, n$ digit numbers with $1\le n\le 9$

$\sum_\limits{n=0}^9 {9\choose n} = 2^9$

Since $0$ is not a possibility.

$\sum_\limits{n=1}^9 {9\choose n} = 2^9 - 1$

• Yours and the guy's above really helped me. Thanks! – Dr. Tan Sep 6 '16 at 23:52