Thought Process

I solved Problem 885 first which is quite similar, please view that page to understand the next statement. There are 21C9 = 293,930 increasing numbers in this case so it is easy to brute force.

Instead of counting all the permutations of the digits, we need to count the number of permutations without any leading 0's. 

The way I did this is, let x be the increasing number we have:

1. Count the permutations of all the digits that are not 0. That is (n - d0)!/(d1!d2!d3!d4!d5!d6!d7!d8!d9!), where di = number of times digit i appears in x.

2. Then imagine you can place the 0's in any position except at the front, that is there are (n - 1)Cd0 ways to do this.

Hence the total number of permutations without leading 0's is k = (n - d0)!(n - 1)!/(n - 1 - d0)!/(d1!d2!d3!d4!d5!d6!d7!d8!d9!), then we can directly sum T(x) for these k permutations using k(k - 1)/2.

Example:

Take x = 0223, then d0 = 1, d2 = 2, d3 = 1, hence we have k = 3!3!/2!/2! = 9, as shown above. Then T(2023) = 8, T(2032) = 7, ... , T(3022) = 2, T(3202) = 1, T(3220) = 0, so sum of all these T(x) = 9*8/2 = 36.