Expected number of switches

Question

Consider the random permutation of $n$ integers $1,2,\ldots,n$. We say that $i$ and $j\;\;(i\neq j)$ are switched if the integer $i$ occupies the $j^{th}$ position and $j$ occupies the $i^{th}$ position after the permutation. Find the expected number of switches in a random permutation.

Answer 1

Let $n\ge 2$. Define random variable $X_i$ by $X_i=1$ if $i$ is a partner in a switch, and by $X_i=0$ otherwise. Then the number $S$ of switches is given by
$$S=\frac{1}{2}\left(X_1+X_2+\cdots+X_n\right).$$ By the linearity of expectation, $$E(S)=\frac{n}{2}E(X_1).$$

To find the probability that $1$ is involved in a switch, we find the probability that $1$ and $2$ are switched, and multiply by $n-1$.

There are $(n-2)!$ permutations in which $1$ and $2$ are switched, so the probability they are switched is $\frac{1}{n(n-1)}$. Putting things together, we find that $$E(S)=\frac{n}{2}(n-1)\frac{1}{n(n-1)}.$$ This simplifies to $\frac{1}{2}$, which means we have missed a simple argument.

Answer 2

More of a comment: the general question is how many $k$-cycles there are in a random permutation. This is answered in this question, see also this wiki article.