← RoseCode

ROSECODE 466

Displacement of permutation

liuguangxi · Math ·

Let p be a permutation of the set {1,2,3,…,n}. We call the sum Dk(p)=∑i=1n|pi−i|k the total displacement with kth power of p. For example, if p = (4,2,1,3), D1(p)=|4−1|+|2−2|+|1−3|+|3−4|=6, D2(p)=|4−1|2+|2−2|2+|1−3|2+|3−4|2=14, D3(p)=|4−1|3+|2−2|3+|1−3|3+|3−4|3=36.

For any positive integer n, assume every possible permutation p of the set {1,2,3,…,n} is uniformly distributed. Let E(n) be the expected value of D1(p)+D2(p)+D3(p). You are given E(2)=3, E(3)=40/3, E(5)=432/5, and all E(n) are rational number. Let F(n) be the numerator of E(n) with E(n) be fraction in lowest terms. So, F(2)=3, F(3)=40, F(5)=432 and so on.

Let S(n)=∑i=1nF(i). Find S(12345678987654321)mod1000000007.


Thanks to baihacker for the idea.