Time left $0$:$08$:$37$

Question $1$

Not yet answered

Marked out of $1\mathrm{.}00$

Flag question

Question text

Assume we are interested to sort a random permutation of integers from $1$ to n$.$ No matter what sorting method we use, ultimately sorting will be done by swapping positions of the elements in the permutation. For example, if we consider the permutation $[1,3,2,6,5,4]$ we can sort it by permuting the values $3$ and $2,($so indices of permuted elements are $2$ and $3)$ and values $6$ and $4($so indices of permuted elements are $4$ and $6).$ In general, sorting a permuation of numners from $1$ to n$,$ we will end up doing a number of permutations of elements with indices i$,$j for all possible i and j values from $1$ to n$.$ Let Xij be a random variable counting how many permuations of the elements with indices i and j we need to permute in order to sort a random permutation of integers from $1$ to n$.$ From the following, select the correct mathematical expecation of the random variable Xij $($recall that the mathematical expectation of a random variable can be computed by summing its values multipled by the probabailities of each value; for example, if a random variable X takes three values : X$=\{1,2,3\}$ and p$($X$=1)=1/2,$ p$($X$=2)=1/2,$ p$($X$=3)=1/3$ then E$($X$)=1*(1/2)+2*(1/2)+3*(1/3)=2\mathrm{.}5).$

Question $1$Answer

a$.$

$1/2$

b$.$

$1$

c$.$

n

d$.$

n$!$