Processing math: 100%

Problem #247

Too Difficult

Given a sequence a consisting of n integers, an inversion is defined as a pair of indices (i, j) such that i < j and a[i] > a[j]. Let {\mathrm{inv}}(a) denote the total number of inversions in a. A permutation p of order n is a sequence p of size n such that for any 1\le i \le n, there exists a valid index j such that p_j = i. For example, the sequence p = (1, 3, 2, 4) is a permutation of order 4, and it has 1 inversion, namely (2, 3).

Calculate the sum of {\mathrm{inv}} (p) over all distinct permutations of order n = 15. (Two permutations p and q are different if there is an index i for which p[i] \ne q[i].)

Contributed by Manas Gupta

Solved by 74 users

Log in to submit answers.

Is something wrong?

Maintaining a collection of high quality questions is our top priority. If, however, you do find an error, report the problem and we'll make sure it is reviewed soon.