Sum of all terms in convolution of the permutation of 1 to n Find all the permutation of 1 to $n$ and treat the $n$ numbers produced as a series
and find their sums.  What is the total of all $n!$ sums?  Example for 1,2,3 gives
one of six permutation 2,1,3: convolving gives $3*3 + (1*3+3*1) + (2*3+1*1+3*2)=9 + 6 + 13 = 28$.  The total for the six permutations of 1 to 3 is 144 and for 1 to 4 
is 1480.  It seems that the only way to find this sum is by laborious additions by considering all the cases.  Can anyone think of a shortcut?
I will give another example and hope the machine prints what I want it to print.  Take 1,2,3,4 which has 24 permutations and select 2,4,1,3.  Try to visualize that these numbers are vertical and that I am convolving them to get for the first column 2 4 1 3*3; 2nd 2 4 1*3 3*1; 3rd 2 4*3 1*1 3*4; 4th 2*3 4*1 1*4 3*2. Add the sum of the products 3*3 + 1*3 + 3*1 + 4*3 1*1 3*4 2*3 + 4*1 + 1*4 + 3*2 and you get 60.  If this does not make it clear, I can do no better with the limitations of what the machine wants to send to you.                                        
 A: Convolution can be expressed by multiplication of polynomials. For example, $$(2x^2+x+3)^2=4x^4+4x^3+13x^2+6x+9$$
gives $[2,1,3]*[2,1,3]=[13,6,9]$ by the last $3$ coefficients. In general, we may use the coefficients of $1,x,\ldots,x^{n-1}$ to formulate the convolution of sequences of length $n$.
So the polynomial
$$P(x):=\sum_{\sigma\in S_n}\biggl(\sum_{i=1}^n\sigma(i)x^{n-i}\biggr)^2$$
contains all the information we need. It is easy to see that $\deg P=2n-2$. We may assume that $P(x)=\sum_{i=0}^{2n-2}a_ix^i$ and we need to compute $S:=\sum_{i=0}^{n-1}a_i$.
Let $\tau\in S_n$ be the reflection $\tau(i)=n+1-i$, then
\begin{align}
P(x)&=\sum_{\sigma\in S_n}\biggl(\sum_{i=1}^n\sigma(i)x^{n-i}\biggr)^2\\
&=\sum_{\sigma\in S_n}\biggl(\sum_{i=1}^n\sigma\tau(i)x^{n-i}\biggr)^2\\
&=\sum_{\sigma\in S_n}\biggl(\sum_{i=1}^n\sigma(n+1-i)x^{n-i}\biggr)^2\\
&=\sum_{\sigma\in S_n}\biggl(\sum_{i=1}^n\sigma(i)x^{i-1}\biggr)^2\\
&=x^{2n-2}\sum_{\sigma\in S_n}\biggl(\sum_{i=1}^n\sigma(i)x^{i-n}\biggr)^2\\
&=x^{2n-2}P(1/x)
\end{align}
We know that $P(x)$ is self-reciprocal, i.e. $a_i=a_{2n-2-i}$ for $i=0,1,\ldots,2n-2$. Hence
$$S=\sum_{i=0}^{n-1}a_i=\sum_{i=n-1}^{2n-2}a_i=\frac{1}{2}\left(\sum_{i=0}^{n-1}a_i+\sum_{i=n-1}^{2n-2}a_i\right)=\frac{1}{2}\left(a_{n-1}+\sum_{i=0}^{2n-2}a_i\right).$$
In order to compute $S$, we first compute
$$\sum_{i=0}^{2n-2}a_i=P(1)=\sum_{\sigma\in S_n}\biggl(\sum_{i=1}^n\sigma(i)\biggr)^2=\sum_{\sigma\in S_n}\biggl(\frac{n(n+1)}{2}\biggr)^2=\frac{n^2(n+1)^2n!}{4}.$$
For $a_{n-1}$, we have
$$a_{n-1}=\sum_{\sigma\in S_n}\sum_{i=1}^n\sigma(i)\sigma(n+1-i)=\sum_{i=1}^n\sum_{j=1}^nij\left|\{\sigma\in S_n:\sigma^{-1}(i)+\sigma^{-1}(j)=n+1\}\right|$$
and
$$\left|\{\sigma\in S_n:\sigma^{-1}(i)+\sigma^{-1}(j)=n+1\}\right|=\begin{cases}
n(n-2)!, & \text{$n$ even and $i\neq j$}\\
0, & \text{$n$ even and $i=j$}\\
(n-1)!, & \text{$n$ odd}\\
\end{cases}$$
which implies
$$a_{n-1}=\begin{cases}
\dfrac{n(3n+2)(n+1)!}{12}, & \text{$n$ even}\\
\dfrac{n(n+1)(n+1)!}{4}, & \text{$n$ odd}\\
\end{cases}$$
So
$$S=\frac{1}{2}\left(a_{n-1}+\frac{n^2(n+1)^2n!}{4}\right)=\begin{cases}
\dfrac{n(3n^2+6n+2)(n+1)!}{24}, & \text{$n$ even}\\
\dfrac{n(n+1)^2(n+1)!}{8}, & \text{$n$ odd}\\
\end{cases}.$$
A: The key in this question is a function defined on finite lists of numbers using convolution. The definition can best be seen by an example:
$$f([a,b,c,d,e])\!=\!(aa)\!+\!(ab\!+\!ba)\!+\!(ac\!+\!bb\!+\!ca)\!+\!(ad\!+\!bc\!+\!cb\!+\!da)\!+\!(ae\!+\!bd\!+\!cc\!+\!db\!+\!ea).$$
There is an alternate definition using alternating sum of squares of partial sums. Same example: $$f([a,b,c,d,e])=(a+b+c+d+e)^2-(b+c+d+e)^2+(b+c+d)^2-(c+d)^2+(c)^2.$$ The example given by the OP can be computed as $$f([2,4,1,3])\!=\!2+4+1+3)^2-(4+1+3)^2+(4+1)^2-(1)^2=10^2-8^2+5^2-1^2\!=\!60.$$
The question asks for the sequence $a(n)$ which is the sum over all permutations $\pi$ of $\{1,\dots,n\}$ of $f(\pi).$ The sequence (not yet in the OEIS) begins $[1,13,144,1480,16200,183960,2257920,\dots]$ and I have no shortcut for it yet.
A: Building on Somos's answer, we first write $a(n)$ as a sum over all subsets of $\{1,\ldots,n\}$:
$$a(n) = \sum_{S \subseteq \{1,\ldots,n\}} (-1)^{n-|S|} |S|! (n-|S|)! \big(\sum_{i\in S} i\big)^2,$$
since each $S$ occurs as a partial sum in exactly $n!/C(n,|S|) = |S|! (n-|S|)! $ permutations.  If $b(n,k,r)$ counts the number of $k$-subsets of $\{1,\ldots,n\}$ which sum to $r$, then we can combine like terms in the above sum to get
$$a(n) = \sum_{k=1}^n (-1)^{n-k} k!(n-k)! \sum_{r=1}^{n(n+1)/2} b(n,k,r) r^2.$$
In particular, if we have the generating function $F_{n,k}(x) = \sum_r b(n,k,r) x^r$, then $F'_{n,k}(1) = \sum_r r b(n,k,r)$ and $F''_{n,k}(1) = \sum_r r(r-1) b(n,k,r)$, so the inner sum above can be written as $F''_{n,k}(1) + F'_{n,k}(1)$.
In fact we do have a generating function for $F_{n,k}(x)$: it is given by the $q$-binomial coefficient, or more specifically:
$$F_{n,k}(q) = q^{k(k+1)/2} \binom{n}{k}_q.$$
Adding this all up, if we use $\binom{n}{k}'_x$ to denote the derivative of $\binom{n}{k}_q$ with respect to $q$ evaluated at $q=x$ (similarly for higher derivatives), then:
$$a(n) = \sum_{k=1}^n (-1)^{n-k} k!(n-k)! \left( \frac{k^2(k+1)^2}{4} \binom{n}{k}_1 + (k^2+k+1) \binom{n}{k}'_1 + \binom{n}{k}''_1 \right).$$
Finally, $\binom{n}{k}_1$ is just the regular binomial coefficient $\binom{n}{k}$, so we can pull it out of the sum as.
$$a(n) = n! \sum_{k=1}^n (-1)^{n-k} \frac{k^2(k+1)^2}{4}  +  \sum_{k=1}^n (-1)^{n-k} k!(n-k)! \left( (k^2+k+1) \binom{n}{k}'_1 + \binom{n}{k}''_1 \right).$$
The first sum can be evaluated explicitly, but it isn't very pretty (per Wolfram Alpha it's $\frac{1}{16} ( 2n^4 + 8n^3 + 8n^2 - 1 + (-1)^n)$).   Sadly, I know absolutely nothing about the properties of $\binom{n}{k}'_1$ and $\binom{n}{k}''_1$, but I'll bet someone else here does.
