# GATE CSE 2003 | Question: 61

9.6k views

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$?

1. $\frac{n(n-1)}{2}$
2. $\frac{n(n-1)}{4}$
3. $\frac{n(n+1)}{4}$
4. $2n[\log_2n]$

retagged
0
0
plz someone explain 2nd question
2
0
thanks for sharing,it contains awesome questions

# 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.

ago

## Related questions

1
11.6k views
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$. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of $1. . . n$ with at most $n$ inversions? $\Theta(n^2)$ $\Theta(n\log n)$ $\Theta(n^{1.5})$ $\Theta(n)$
The unusual $\Theta(n^2)$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will remain $\Theta(n^2)$ become $\Theta(n (\log n)^2)$ become $\Theta(n \log n)$ become $\Theta(n)$
In the following $C$ program fragment, $j$, $k$, $n$ and TwoLog_n are integer variables, and $A$ is an array of integers. The variable $n$ is initialized to an integer $\geqslant 3$, and TwoLog_n is initialized to the value of $2^*\lceil \log_2(n) \rceil$ for (k = 3; k <= n; k++) A[k] ... $\left\{m \mid m \leq n, \text{m is prime} \right\}$ { }
Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_{k+1}) \in E$ for all $k$ in $i$ through $j-1$. A simple path is a path in which no vertex ... longest path length from $j$ to $k$ If there exists a path from $j$ to $k$, every simple path from $j$ to $k$ contains at most $A[j,k]$ edges