長さNのすべての順列に対する転倒数の総和
DPで$ O(N)で求まる
長さ$ nの順列に対する転倒数の総和を$ A_nと表すことにする
$ A_1 = 0
$ A_{N} = N A_{N - 1} + (N - 1)! \frac{N (N-1)}{2}
長さ$ N-1の順列のどこかに$ Nを挿入すると考える
長さ$ N-1の順列は$ (N-1)!通りあり、それぞれについて$ N通りの挿入箇所が考えられる
要素$ Nが右から$ i番目（0-index）になるように挿入するとき、転倒数は$ i増える