# The distribution of cycle length in random derangement

It is known that for a fixed x $\in \{0,1,...,N-1\}$, the length of the cycle of x in a random permutation in $S_N$ distributes uniformly in $\{1, . . . ,N\}$.

My question is regarding the length of x in a random derangement (permutation without any fixed point).

Does the length distributes uniformly in $\{2, . . . ,N\}$? If not - what is the distribution?

Any proof, proof sketch, reference or good explanation will be appreciated. I tried to google it, or to find relevant papers in google-scholar, but without success.

The number of permutations where $x$ is in a cycle of length $k$ is $(N-1)!$. In order to have a derangement, $k$ must be at least 2 and the remaining $N-k$ elements must be "deranged". When $N-k$ is not too small, the fraction of derangements will be very close to $1/e$, so the cycle length in a derangement will be asymptotically uniformly distributed in the sense that if we divide by $N$, it converges in distribution to uniform on $[0,1]$. But for $k$ close to $N$, there will be irregularities, for instance the cycle length is never $N-1$.
The number $D_n$ of derangements of $n$ elements is $n!/e$ rounded up for even $n$, down for odd $n$. There are $(N-1)!/(N-k)!$ ways of choosing a cycle of length $k$ containing a prescribed element $x$, then $D_{N-k}$ ways of deranging the remaining elements. Divide by $D_N$ to get the probability. –  Johan Wästlund May 13 '13 at 10:59
From your answer I understand that the the probability for a cycle of length k is approximately: $(N-1)!/(N-k)! \cdot (N-k)!/e = (N-1)!/e$ (with additional division by $D_N$). But for $N>2$ there are only $N-2$ possible cycle lengths ($k \ne 1,N-1$), so the total sum of the probabilities is not $1$, because $(N-2)(N-1)!/e \ne D_N$. I might miss something. –  Nate May 16 '13 at 7:14
The probability of being in a cycle of length $k$ is $(N-1)!/(N-k)!\cdot D_{N-k}/D_N$ for $k=2,\dots, N$. For instance, when $N=5$ the probabilities for $k=2,3,4,5$ are $2/11, 3/11, 0, 6/11$, summing to 1. –  Johan Wästlund May 16 '13 at 8:55
OK. Thanks. My next challenge is to find the distance (exact or bounds) between this distribution to uniform distribution for values like $N=2^{16}$ or $N=2^{32}$. –  Nate May 16 '13 at 19:50