Numbers with increasing digits

Let's say the sum of all numbers with strictly increasing digits ending with $n$ be $S_n$ .

If the number satisfies such a property, then, the the number excluding the ones' digit also satisfies that property. Thus,

$S_n = 10 \sum_{k=0}^{n-1} {S_k} + \left(\text{No. of such numbers} \right) \times n$

Now, for no. of such numbers, we have the recurrence -

$a_n = 1 + a_1 + a_2 + a_3 + \cdots + a_{n-1}$

$a_n = 2 a_{n-1}, a_1 = 1$

$a_n = 2^{n-1}$

Thus, the sum recurrence becomes -

$S_n = 10 \sum_{k=0}^{n-1} {S_k} + 2^{n-1} n$

Now, we can use method of generating functions,

$\displaystyle S(z) = \sum_{n \geq 0} S_n = \sum_{n \geq 1} S_n$

$S(z) = 10 z \frac {S(z)} {1-z} + \frac{z} {{(1 - 2z)}^2}$

$S(z) = \frac{z(1-z)} {(1 - 11z){(1 - 2z)}^2}$

$S(z) = \frac{10}{81 (1-11z)} - \frac{11}{162 (1 - 2z)} - \frac{1}{18 {(1 - 2z)}^2}$

$S_n = \frac{10}{81} 11^n - \frac{11}{162} 2^n - \frac{1}{18} (n+1) 2^n$

We have to find $\displaystyle S_1 + S_2 + S_3 + \cdots + S_9 = \frac{S_{10} - 10 \times 2^9} {10} = 320214537$

The one digit numbers sum to 45.

The two digit numbers sum to 1440.

The three digits numbers sum to 25830

The four digit numbers sum to 310968

How do we know what number goes in a spot? For example, how do we know there are 30 four digit numbers with a 6 in the 10s place?

Consider _ _ 6 _. There are 10 three digit numbers that end in 6 and there are 3 two digit numbers that begin with 6. Just multiply the beginnings by the endings.

So we can keep building tables like the above, but I'll just give the totals.

five digits: 2592450

six digits: 14814720

seven digits: 55555515

eight digits: 123456780

nine digits: 123456789

total: 320214537

There are 511 ( $2^9-1$ ) such numbers. Using the numbers from 1 to 511 (zero is not used as that would be a no digit number) as a binary mask to digits and add the numbers. This is a small programming loop. The sum is 320214537.

Okay, I got the same answer as you did, 320214537.