Probability that a random permutation of n elements has a cycle of length k > n/2 When $k > n/2$, the probability that a random permutation of an $n$-element set has a cycle of length $k$ is $1/k$.
This is well-known and easy enough to see.  We can just count permutations with a cycle of length $k$ and divide by $n!$.  This is made easier by the fact that any permutation has at most one cycle of length $k > n/2$.
Take an $n$-element set $X$.   Choosing a permutation of $X$ with a cycle of length $k$ is the same as choosing a $k$-element subset $S \subseteq X$, a cyclic ordering on $S$, and an arbitrary permutation of $X - S$.
There are $\binom{n}{k}$ choices of $S$, $(k-1)!$ cyclic orderings on $S$, and $(n-k)!$ permutations of $X - S$.   Multiplying these, we get
$$  \binom{n}{k} (k-1)! (n-k)! = \frac{n! (k-1)! (n-k)!}{k! (n-k)!} = \frac{n!}{k}  $$
Dividing by $n!$ we get $1/k$ as desired.
Here is my question, raised in email by Emily Zhang: is there a way to directly get the answer $1/k$ without all the cancellations required in the above approach?
Perhaps to do this we need more sophisticated math of some sort.
 A: Fix an element $x\in X$, where $\#X=n$, and fix $k>n/2$. It suffices to show that the probability that $x$ is contained in a $k$-cycle is $\frac1n$, since exactly $\frac kn$ of the elements of $X$ are contained in any given $k$-cycle and $\frac1k\frac kn=\frac1n$.
But in fact the distribution (among all permutations of $X$) of the length of the cycle containing $x$ is uniform on $\{1,2,\dots,n\}$! To see this, note that the image of $x$ under a random permutation has a $\frac1n$ chance of being $x$ itself; if not, then the image of its image has a $\frac1{n-1}$ chance of being $x$, leading to a $\frac{n-1}n\frac1{n-1}=\frac1n$ chance of $x$ being in a cycle of length $2$; and so on.
A: Greg Martin's nice argument can be used to prove something more general: for any $1 \le k \le n$, the expected number of $k$-cycles is $\frac{1}{k}$. For $k > \frac{n}{2}$ there can be at most one $k$-cycle so the expectation reduces to the probability.
To see this, we observe that the expected number of $k$-cycles is $\frac{n}{k}$ times the probability that a fixed element lies in a $k$-cycle, by linearity of expectation together with the fact that a $k$-cycle contains, of course, $k$ elements. And Greg shows that this probability is $\frac{1}{n}$.
