GATE CSE 2003 | Question: 61

Question

In a permutation \(a_1 ... a_n\), of n distinct integers, an inversion is a pair \((a_i, a_j)\) such that \(i < j\) and \(a_i > a_j\).

If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of \(1. . . n\)?

• A. \(\dfrac{n(n-1)}{2}\)
• B. \(\dfrac{n(n-1)}{4}\)
• C. \(\dfrac{n(n+1)}{4}\)
• D. \(2n[\log_2n]\)

Comments

thanks for sharing,it contains awesome questions

---

we want a[i]> a[j] while i<j

for a pair we need to choose NC2 elements , these are maximum elements where i<j

probability of each pair where a[i]>a[j] is 1/2

so ,

Expectation = 1/2 * nC2

---

Simplest Big brain approach - 

Take n = 2 
1,2 
1,2 = 0 inversion 
2,1 = 1 inversion 

E(2) = 1/2*1 = 1/2 

Put n=2 in all options 
match with 1/2 only Option B Matches 

Please try to understand other approaches also after understanding this. 

Answer 1

61.Take n=3,

Permutation ----> no of inversions

1 2 3                        0

1 3 2                        1

2 3 1                         2

2 1 3                         1

3 1 2                         2

3 2 1                         3

Total inversions =9, no of permutation =6,

So, here n=6

putting it in option n(n-1)/4=6⨉5/4=7.5

So, (B) is most closer option

62. Now elements are comes like 5,4,3,2,1

So,  first 5 comes order is 5--------------0 inversion

 Now, 4 comes........"       " 5,4 -----------1 inversion

 Now 3 comes..........."       " 4,5,3--------2 inversions

Now 2      "..........................3,4,5,2--------3  inversions

Now 1     " .......................2,3,4,5,1---------4 inversions

total 10 inversion

No more permutation could be done in insertion sort

So, number of permutation could be n(n-1)/2= O(n²)

Ans (A) here

Comments

For 62 did not get what you are doing. Question says there are at most $n$ inversions and in your example there are $\frac{n . (n-1)}{2}$ inversions. So, you are solving wrong.

---

at most 1 inversion in each time. right?

then 1 card picking 0 inversion

2nd card picking atmost 1inversion

..............

nth card picking at most n inversion

So, adding all inversion 1+2+...+n =O(n^2)

---

That is for that particular input- but question says to consider inputs with at most $n$ inversions.

Answer 2

Select 2 out of n and half of them will be inversions B.

Comments

@anshu garu

How can we say that the answer is half of it plzz xplain

Answer 3

61. Option B is correct.

62. Option D is correct.

Answer 4

B is the Answer

Answer 5

Ans -B 

Let \(X_{ij}\) be an indicator random variable s.t. $$X_{ij} = \begin{cases} 0 &\mbox{if } (a_i,a_j) \text {not inverted} \\ 1 & \mbox{if } otherwise. \end{cases}$$ Let random variable \(X\) denotes total number of inversions. So clearly \(X=\sum\limits_{\substack{i,j \\ i<j}}X_{ij}\). Note that their are \(^n\mathrm{C}_2\) terms in summation, because there are total \(^n\mathrm{C}_2\) pairs, and each pair is either inverted or not.
So now we want to find \(E(X)\). Now \(E(X)=\sum\limits_{\substack{i,j \\ i<j}}E(X_{ij})\). But \(E(X_{ij}) = \frac{1}{2}\), because for any pair, probability of inversion is same as of not inversion.
So \(E(X) = \frac{^n\mathrm{C}_2}{2} = \frac{n(n-1)}{4}\).
So option (B) is correct.

Answer 6

https://youtu.be/KFcodn4qfrQ

please check this video for the method used by others to solve the question (linearity of expectation) MIT video

just think it as expected no. of heads in n coin flips.

here n coin flips refers to no. of pairs in the sequence which is n©2. probability of head = probability of a pair being a inversion=0.5

 

remember expectation of a binomial distribution is np, here also same.

expectation of no. of inversion pairs =np=n©2*0.5