Given a permutation $p$ of $n$ numbers, we create an array $a$ consisting of $2n$ numbers, which is equal to $p$ concatenated with its reverse. We then define the beauty of $p$ as the number of inversions in $a$. Your task is to find the sum of beauties of all $n!$ permutations of size $n$. Print the remainder we get when dividing this value by $1000000007$.
Let us call the reverse of $p$ as $\operatorname {rev}(p)$, then we notice that if $0\leq i \lt j \lt 2n$ form an inversion in $a$ then either one of these three cases must occur:
- $i \in p, \quad j \in p$
- $i \in p, \quad j \in \operatorname {rev}(p)$
- $i \in \operatorname {rev}(p), \quad j \in \operatorname {rev}(p)$
Since we are going to iterate over all permutations of $p$, we note that the first and third cases are exactly the same and we write, considering $\operatorname{inv}(p)$ to be the number of inversions in $p$, and $\pi(\cdot)$ being the set of all permutations of an array:
\[\operatorname{inv}(a) = \operatorname{inv}(p) + \operatorname {inv}(\operatorname {rev}(p)) + \dfrac{n(n-1)}{2}\]Summing over all the $n!$ permutations of $p = $ {$1 \dots n$} we get
\[\displaystyle \sum\operatorname{inv}(a) = \sum\operatorname{inv}(p) + \sum\operatorname {inv}(\operatorname {rev}(p)) + n!\cdot\dfrac{n(n-1)}{2}\tag{1}\] \[=2\sum\operatorname{inv}(p) + n!\cdot\dfrac{n(n-1)}{2}\tag{2}\]Now the task of finding the sum of the number of inversions over all permutations of [1…n] is something we must tackle. $(**)$
EDIT
09 November 2024
Wait! This approach makes the problem significantly harder than it needs to be.
Approach 1
Pick any two numbers (not indices) $x$ and $y$ in $p$. In $a$, they can appear either in the order $x\ y \ y \ x$ or $y \ x \ x \ y$, in both of which cases we get a total of two inversions. Thus for any permutation $p$, its beauty is given by $2\cdot \displaystyle\binom{n}{2} = n(n-1)$, independent of the specific permutation $p$.
Hence the total number of inversions is simply this constant multiplied by the number of possible permutations, which is $n!\cdot n(n-1)$.
Approach 2
Suppose we pick two indices $i, j$ from $p$. If $(i, j)$ is an inversion in the first half of $a$, then $(i + n, j + n)$ will not be an inversion in the second half of $a$. However, if $(i, j)$ is NOT an inversion in the first half of $a$, then $(i + n, j + n)$ MUST be an inversion in the second half of $a$.
This simply means that any pair of indices $(i, j)$ from $p$ will give us exactly one inversion in $a$, and there are $\displaystyle \binom n2$ such pairs. Add to this the cross inversion term from $(2)$ and we get the same answer again, $n!\cdot n(n-1)$.
So the lesson learnt is sometimes we might need to stop a little bit early and look at the problem from a holistic point of view instead of simplifying the expression as much as possible.