MathDB

A permutation

Source: Indian IMOTC 2004 Practice Test 1 Problem 4

September 23, 2005

combinatorics unsolvedcombinatorics

Problem Statement

Given a permutation

\sigma = (a_1,a_2,a_3,...a_n)

of

(1,2,3,...n)

, an ordered pair

(a_j,a_k)

is called an inversion of

\sigma

if

a \leq j < k \leq n

and

a_j > a_k

. Let

m(\sigma)

denote the no. of inversions of the permutation

\sigma

. Find the average of

m(\sigma)

as

\sigma

varies over all permutations.

Back to Problems View on AoPS