Sum of permutations Given a number N and The permutations of N are supposed to be taken in a particular way. Given a number, you can erase some of the digits of the number, but keeping the order of the rest of the digits same.
Eg. the number is 389. The permutations allowed are as following – 3,8,9,38,39,89,389.
So i need to find the total sum of these total permutations.
I know the simple approach would be to find all the permuatations.
But the N can be very large so how to approach this question.
 A: Hint: Assume your number has $n+1$ (distinct, i.e. no repetitions allowed) digits $d_0, ... d_{n}$ (where $d_0$ denotes the unit digit that corresponds to $10^0$, $d_1$ the tenth's digit that corresponds to $10^1$ and so on), so that the number $N$ can be written as $$\sum_{i=0}^{n}10^id_i$$ Denote with $P$ the set of all the allowed permutations $\sigma$. For a specific permutation $\sigma$ denote with $1\le \sigma(d_i) \le n+1$ the position of the digit $d_i$. Using the above notation we want to calculate the sum $$\sum_{i=0}^{n}\left(\sum_{\sigma \in P}10^{\sigma (d_i)}d_i\right)$$ The inner sum denotes the summation for each digit over all allowable permutations and the outer sum denotes the sum over all digits. So, you can forget the outer sum becomes it simply means repeat for each digit (so the difficult summation is the inner one). Then each digit $d_i$ appears in exactly:


*

*All permutations with 1 missing digit (except for the digit $d_i$). There are $n$ permutations of length $n$ that are derived by the elimination of one digit each. For the first $n-i$ digits $d_i$ remains in it's position so that we have $(n-i)\cdot10^i\cdot d_i$. For the last $i$ digits $d_i$ loses one position so that we have $i\cdot10^{i-1}d_i$. So in total we sum $$d_i10^{i-1}\left[10n-9i\right]$$ for all $0\le i\le n$.

*All permutations with 2 missing digits (except for the digit $d_i$). There are know already many cases. First case, both digits are in front of $d_i$ so that $d_i$ remains in place. Second case, one digit is front of $d_i$ and one digit is behind $d_i$ which means that $d_i$ loses one position. Third case, both digits are behind $d_i$ so that $d_i$ loses two positions. The number of permutations that correspond to each case are: For the first case there are $\dbinom{n-i}{2}$ ways to eliminate a number in front of $d_i$. In each of this $d_i$ remains in place $i$ so that we have $\dbinom{n-i}{2}10^id_i$. For the second case there are $(n-i)\cdot(i)$ ways to pick one digit in front of $d_i$ and one behind it and exclude them. Therefore we have $(n-i)i10^{i-1}d_i$. For the third case we have again $\dbinom{i}{2}$ ways to exclude two digits behind (I mean smaller) from $d_i$ so that we have $\dbinom{i}{2}10^{i-2}d_i$. So in total we sum $$10^{i-2}d_i\left[\dbinom{n-i}{2}10^2+(n-i)i10+\dbinom{i}{2}10^{i-2}\right]$$


Accordingly you procced for the number of permutations with 3 missing digits, 4 missing digits and so on. This is very arduous in general (though not mathematically difficult) and I strongly recommend that you restrict your problem and specify more things about your number. A general algorithm for a general number as you see exists but it's implementation is comptutationally demanding.
