0
$\begingroup$

In a permutation of the set ${1, 2, . . . , n}$, a pair $i$, $j$ is out of order if $i < j$ but $i$ occurs after $j$ in the permutation. In a random permutation of the set ${1, 2, . . . , n}$ with all permutations equally likely, what is the expected number of pairs that are out of order?

Solution: $\frac{n\choose2}{2}$

I'm confused on the solution because if $n=3$ then there'd be pairs $(1,1), (1,2), (2,1),(1,3),(3,1),(2,3),(3,2),(2,2),(3,3)$ where 6 our of 9 pairs are out of order. $3\choose2$ $= 3$ and $3/2=1.5$.

Edit: I'm confused on the solution because if $n=3$ then there'd be pairs $(1,2), (2,1),(1,3),(3,1),(2,3),(3,2)$ where 3 out of 6 pairs are out of order. $3\choose2$ $= 3$ and $3/2=1.5$

$\endgroup$
  • 1
    $\begingroup$ You can't talk about pairs being out of order until you choose one particular permutation. You haven't done that. ($(1,1)$ isn't a permutation of $\{1,2,3\}$; $(1,2,3)$, $(1,3,2)$, etc., are.) $\endgroup$ – Christopher Carl Heckman Apr 17 '16 at 1:11
  • 1
    $\begingroup$ Why are you considering the pairs of the form $(a,a)$? The elements of the pairs should be distinct. $\endgroup$ – Michael Burr Apr 17 '16 at 1:11
  • $\begingroup$ This MSE link might prove useful reading. $\endgroup$ – Marko Riedel Apr 17 '16 at 1:23
1
$\begingroup$

The key is to count by pair of values not by permutation: there are $\binom{n}{2}$ pairs of values and each pair of values $(i,j)$ (with $i<j$) is out-of-order in as many permutations as it is in-order. Therefore each pair of values is counted as out-of-order in $\frac{n!}{2}$ permutations, which means that overall there are $\binom{n}{2} \frac{n!}{2}$ total out-of-order pairs. Since there are $n!$ permutations, that gives an expected value of $\frac{1}{2} \binom{n}{2}$.

For example, if $n=3$: the pair $(1,2)$ is counted as in-order in $(123)$, $(132)$, and $(312)$ and out-of-order in $(213)$, $(231)$, and $(321)$ (permutations are written in one-line notation, not as cycles).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.