# Confusion on in order problem with combinations

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$

• 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.) – Christopher Carl Heckman Apr 17 '16 at 1:11
• Why are you considering the pairs of the form $(a,a)$? The elements of the pairs should be distinct. – Michael Burr Apr 17 '16 at 1:11
• This MSE link might prove useful reading. – Marko Riedel Apr 17 '16 at 1:23

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