Guys I just discovered something amazing. Can someone please confirm this? The sum of all possible ways to form a number with $n$ digits, using its digits, without repetition, is equal to $11\ldots1\cdot m(n-1)!$, where $m$ is the sum of the digits of the number, and the amount of $1$'s is equal to $n$. For example, $123$ can be arranged $132, 231, 213, 312, 321$. The sum of these numbers is equal to $1332$. $(111)(6)(2)$. I'll be waiting for my Fields Medal.
[Math] Sum of all possible combinations
combinatoricsnumber theorysummation
Related Solutions
The "resort" of a permutation is its inverse, and $\pi(i)=\pi^{-1}(i)$ iff $i$ is either fixed by $\pi$ or belongs to a 2-cycle in $\pi$. That means $q(n,k)$ is the number of permutations of $n$ things with exactly $k$ numbers $i$ such that $\pi^2(i)= i$.
To count these, first choose the $k$ numbers fixed by $\pi^2$ - there are $n\choose k$ ways to do that. On these $k$ numbers $\pi$ acts as an involution: there are A000085 of those, which is your $s(k)$. On the other $n-k$ numbers $\pi$ must be fixed point free with all cycles of length at least 3, and there are A038205 of those, which is your $t(n-k)$.
So all you need is to prove that these sequences have the claimed generating sequences. Here's a sketch of how to do that: for the details (and for much greater generality) look at chapter 3 of Wilf's Generatingfunctionology, freely available online.
Suppose you want to count the number of permutations on $n$ letters all of whose cycle lengths come from a particular set $S$. The exponential generating function is defined to be: $$ \mathcal{H}_S(x) = \sum_{n \geq 0} h_S(n) x^n /n!$$ where $h_S(n)$ counts how many permutations in $S_n$ can be written as a product of cycles with lengths in $S$. We then have the following lemma: let $S_1$ and $S_2$ be disjoint and let $S =S_1 \cup S_2$. Then $$ \mathcal{H}_S = \mathcal{H}_{S_1}\mathcal{H}_{S_2}.$$ This is a very special case of the Fundamental Lemma from Wilf $\S3.4$ (put $y=1$ there). It's not difficult to prove: if you compare coefficients of $x^n$, it is equivalent to proving that $$ h_S(n) = \sum_{m \geq 0} \binom{n}{m} h_{S_1}(m)h_{S_2}(n-m).$$ To see this, consider building a permutation on $n$ letters whose cycle lengths come from $S=S_1 \cup S_2$, such that $m$ of those $n$ letters are involved in cycles with lengths from $S_1$ and the rest from $S_2$. There are $\binom{n}{m}$ ways to choose those $m$ letters, then $h_{S_1}(m)$ ways to choose a permutation of those $m$ letters with lengths from $S_1$. On the remaining $n-m$ letters has cycle lengths from $S_2$, and there are therefore $h_{S_2}(n-m)$ ways to choose it. Summing over the possible values of $m$ gives the result.
Here's a simple example where we can compute $\mathcal{H}_S$ directly: let $S = \{r\}$, so you are counting the number of permutations in $S_n$ all of whose cycles have length $r$. Clearly $h_S(n)=0$ unless $n=kr$, in which case $h_S(n) = \frac{n!}{r^k k!}$ (each of the $k$ $r$-cycles can be written in $r$ different ways, hence the $r^k$, and the order of the cycles doesn't matter, hence the $k!$). It follows $$\mathcal{H}_S(x) = \sum_{k} \frac{x^{kr}}{(kr)!} \frac{(kr)!}{r^k k!} = \exp(x^r/r).$$
For your $s(n)$ we need to look at permutations all of whose cycles have lengths 1 or 2. Using the fundamental lemma and the cases $r=1$ and $r=2$ of our example and putting $y=1$, the exponential generating function is $$ \exp( x) \exp(x^2/2) = \exp(x + x^2/2)$$ as you observed. For $t(n)$, which counts permutations all of whose cycles have length at least 3, we end up with $$ \exp(x^3/3)\exp(x^4/4)\cdots = \exp\left( \sum_{i \geq 3} x^i/i\right) = \exp\left(\log \frac{1}{1-x} - x - x^2/2\right) = \frac{e^{-x-x^2/2}}{1-x}$$ again agreeing with your observation.
Best Answer
Let's take your example of
123.$123$
$132$
$213$
$231$
$312$
$321$
Let's look at the first digit (the hundreds' place). Since the number of digits is $3$, there will be $3 - 1 = 2$ digits after the first digit. Thus, there will be a total of $(3 - 1)! = 2! = 1$ numbers with each digit as the first.
Thus, the sum of the digits that occur in the hundreds' place (note: all of the digits show up as the first digit) is equal to the sum of the digits, and each digit shows up $(N - 1)!$ times.
Thus, the sum of all of the first-digits is $(digitsum)(N - 1)!$.
It follows that this applies to all of the digits.
Thus, the sum of all of the numbers is $(1\times{digitsum}) + (10\times{digitsum}) + (100\times{digitsum}) + ... + (10^N\times{digitsum})(N - 1)! = 11...11\times{digitsum})(N - 1)!$
QED