The elements of {$1,2,3,...,n$} and {$1,2,3,...,n$} are randomly paired. What is the probability distribution of $S=\text{sum of pair products}$?

Question

The elements of {$1,2,3,...,n$} and {$1,2,3,...,n$} are randomly paired. What is the probability distribution of $S=\text{sum of pair products}$ ?

For example, say $n=5$. There are $5!$ ways to pair the elements, for example $(1,3)\ (2,5)\ (3,1)\ (4,4)\ (5,2)$ which gives $S=(1)(3)+(2)(5)+(3)(1)+(4)(4)+(5)(2)=42$.

I know that, in general:
$S_{\text{min}}=\sum_{k=1}^n{(k)(n-k+1)}=\frac{1}{6}n(n+1)(n+2)$, the triangular pyramidal numbers.
$S_{\text{max}}=\sum_{k=1}^n{k^2}=\frac{1}{6}n(n+1)(2n+1)$, the square pyramidal numbers.

I suspect that the probability distribution of $S$ is well-documented but I don't know what it's called.

Context: In 2020, the IB cancelled exams due to the pandemic and gave grades (1-7) based on other factors (predicted grades, coursework, school's historical grades). When the results were released, some schools felt that some of the grades seemed random. Then I wondered, if seven students got random Math grades 1, 2, 3, 4, 5, 6, 7 and random Physics grades 1, 2, 3, 4, 5, 6, 7, what is the probability distribution of the correlation coefficient between Math grades and Physics grades? That is essentially my question here, except my question here is generalized for $n$ students and grades.

Answer 1

As I suspected, the distribution is well-documented.

Arrange this sequence into rows by cutting through pairs of consecutive 1's.

$$1$$ $$1\ 1$$ $$1\ 2\ 0\ 2\ 1$$ $$1\ 3\ 1\ 4\ 2\ 2\ 2\ 4\ 1\ 3\ 1$$

$$...$$

Divide the numbers in the $n^{\text{th}}$ row by $n!$. For example, the $4^{\text{th}}$ row becomes

$$\frac{1}{24}\ \frac{3}{24} \frac{1}{24} \frac{4}{24} \frac{2}{24} \frac{2}{24} \frac{2}{24} \frac{4}{24} \frac{1}{24} \frac{3}{24} \frac{1}{24}$$

These are the probabilities that $S=S_{\text{min}},\ S_{\text{min}}+1,\ S_{\text{min}}+2,\ ...,\ S_{\text{max}}$, respectively.

Here is a graph related to the distribution.

It seems there is no simple formula for the probabilities.

I found the sequence by using an online permutation generator, excel, and OEIS.

(The sequence is based on work done by the late John Conway in 1993. Professor Conway was my teacher in 1993. Little did I know that he would still be "teaching" me 29 years later.)

Answer 2

You can calculate the mean at least. Write all the permutations of $(1,\ldots n)$ in $n!$ rows:

1, 2,   3, ...,   n-1, n
1, 2,   3, ...,   n,   n-1
...
n, n-1, n-2, ..., 2,   1

Then you would need to multiply the first column by $1$, the second row by $2$... the last column by $n$, sum everything up and divide by the number of rows $n!$.

But if you consider just the first column, since every two numbers are interchangeable, each number appears exactly $n!/n=(n-1)!$ times. The same is true for every column. So the total sum: $$ n!\bar S = \underbrace{\sum_{k=1}^{n}}_{\text{sum by cols}} \left(k\cdot\underbrace{\sum_{i=1}^{n} i(n-1)!}_{\text{sum by elements in a col}} \right) = (n-1)!\left(\sum_{k=1}^{n} k\right)\left(\sum_{k=i}^{n} i\right) =\\ (n-1)!\left(\frac{n(n+1)}2\right)^2,\\ \bar S = \frac{n(n+1)^2}4 $$