Return to Answer

One way to calculate the expected number of cycles of length $k$ is by the inclusion-exclusion formula. You can get the set of permuations of length $n$ with no fixed points by taking the set of permutations, subtracting the multiset of permutations with a fixed point at $i$ (for all $i$), adding the multiset of permuations with a fixed point at $i$ and $j$ (for all $i$ and $j$), etc. Let $D_n$ be the set of permutations with no fixed points (derangements). This gives

$\{D_n\} = \{S_n\} -n\{S_{n-1}\} +\frac{1}{2!}n(n-1) \{S_{n-2}\} -\frac{1}{3!}n(n-1)(n-2)\{S_{n-3}\} \ldots$

where $\{S_k\}$ is the set of permutations of length $k$. Now, we can find the number of $k$-cycles on the right-hand side. The expected number of $k$-cycles in $\{S_{n-i}\}$ is $1/k$ if $k\leq n-i$ and $0$ if $k > n-i$. If we make this replacement, and divide by the number of derangements, we find that the expected number of $k$-cycles is

$\frac{1}{k} \cdot \frac{1 -1 +1/2! -1/3! + \ldots \pm 1/(n-k)!}{1 - 1 + 1/2! - 1/3! +\ldots \pm 1/n!}$.

One can check this formula by noting that it gives the expected number of $n-1$ cycles as 0 and the expected number of $n$-cycles as approximately $e/n$ (this is correct, since the probability that a permutation is a derangement is approximately $1/e$).

For large $n$ and $k\leq n-\log{n}$, this is almost exactly $\frac{1}{k}$. For $k > n-\log{n}$, the expected contribution of the number of cycles from long cycles is quite small, so the expected number of cycles is roughly $\sum_{k=2}^n \frac{1}{k}$.

One way to calculate the expected number of cycles of length $k$ is by the inclusion-exclusion formula. You can get the set of permuations of length $n$ with no fixed points by taking the set of permutations, subtracting the multiset of permutations with a fixed point at $i$ (for all $i$), adding the multiset of permuations with a fixed point at $i$ and $j$ (for all $i$ and $j$), etc. Let $D_n$ be the set of permutations with no fixed points (derangements). This gives

$\{D_n\} = \{S_n\} -n\{S_{n-1}\} +\frac{1}{2!}n(n-1) \{S_{n-2}\} -\frac{1}{3!}n(n-1)(n-2)\{S_{n-3}\} \ldots$

where $\{S_k\}$ is the set of permutations of length $k$. Now, we can find the number of $k$-cycles on the right-hand side. The expected number of $k$-cycles in $\{S_{n-i}\}$ is $1/k$ if $k\leq n-i$ and $0$ if $k > n-i$. If we make this replacement, and divide by the number of derangements, we find that the expected number of $k$-cycles in a derangement is

$\frac{1}{k} \cdot \frac{1 -1 +1/2! -1/3! + \ldots \pm 1/(n-k)!}{1 - 1 + 1/2! - 1/3! +\ldots \pm 1/n!}$.

One can check this formula by noting that it gives the expected number of $n-1$ cycles as 0 and the expected number of $n$-cycles as approximately $e/n$ (this is correct, since the probability that a permutation is a derangement is approximately $1/e$).

For large $n$ and $k\leq n-\log{n}$, this is almost exactly $\frac{1}{k}$. For $k > n-\log{n}$, the expected contribution of the number of cycles from long cycles is quite small, so the expected number of cycles is roughly $\sum_{k=2}^n \frac{1}{k}$.

One way to calculate the expected number of cycles of length $k$ is by the inclusion-exclusion formula. You can get the set of permuations of length $n$ with no fixed points by taking the set of permutations, subtracting the multiset of permutations with a fixed point at $i$ (for all $i$), adding the multiset of permuations with a fixed point at $i$ and $j$ (for all $i$ and $j$), etc. Let $D_n$ be the set of permutations with no fixed points (derangements). This gives

$\{D_n\} = \{S_n\} -n\{S_{n-1}\} +\frac{1}{2!}n(n-1) \{S_{n-2}\} +\frac{1}{3!}n(n-1)(n-2)\{S_{n-3}\} \ldots$

where $\{S_k\}$ is the set of permutations of length $k$. Now, we can find the number of $k$-cycles on the right-hand side. The expected number of $k$-cycles in $\{S_{n-i}\}$ is $1/k$ if $k\leq n-i$ and $0$ if $k > n-i$. If we make this replacement, and divide by the number of derangements, we find that the expected number of $k$-cycles is

$\frac{1}{k} \cdot \frac{1 -1 +1/2! -1/3! + \ldots \pm 1/(n-k)!}{1 - 1 + 1/2! - 1/3! +\ldots \pm 1/n!}$

For large $n$ and $k\leq n-\log{n}$, this is almost exactly $\frac{1}{k}$. For $k > n-\log{n}$, the expected contribution of the number of cycles from long cycles is quite small, so the expected number of cycles is roughly $\sum_{k=2}^n \frac{1}{k}$.

One way to calculate the expected number of cycles of length $k$ is by the inclusion-exclusion formula. You can get the set of permuations of length $n$ with no fixed points by taking the set of permutations, subtracting the multiset of permutations with a fixed point at $i$ (for all $i$), adding the multiset of permuations with a fixed point at $i$ and $j$ (for all $i$ and $j$), etc. Let $D_n$ be the set of permutations with no fixed points (derangements). This gives

$\{D_n\} = \{S_n\} -n\{S_{n-1}\} +\frac{1}{2!}n(n-1) \{S_{n-2}\} -\frac{1}{3!}n(n-1)(n-2)\{S_{n-3}\} \ldots$

where $\{S_k\}$ is the set of permutations of length $k$. Now, we can find the number of $k$-cycles on the right-hand side. The expected number of $k$-cycles in $\{S_{n-i}\}$ is $1/k$ if $k\leq n-i$ and $0$ if $k > n-i$. If we make this replacement, and divide by the number of derangements, we find that the expected number of $k$-cycles is

$\frac{1}{k} \cdot \frac{1 -1 +1/2! -1/3! + \ldots \pm 1/(n-k)!}{1 - 1 + 1/2! - 1/3! +\ldots \pm 1/n!}$.

One can check this formula by noting that it gives the expected number of $n-1$ cycles as 0 and the expected number of $n$-cycles as approximately $e/n$ (this is correct, since the probability that a permutation is a derangement is approximately $1/e$).

For large $n$ and $k\leq n-\log{n}$, this is almost exactly $\frac{1}{k}$. For $k > n-\log{n}$, the expected contribution of the number of cycles from long cycles is quite small, so the expected number of cycles is roughly $\sum_{k=2}^n \frac{1}{k}$.

One way to calculate the expected number of cycles of length $k$ is by the inclusion-exclusion formula. You can get the set of permuations of length $n$ with no fixed points by taking the set of permutations, subtracting the multiset of permutations with a fixed point at $i$ (for all $i$), adding the multiset of permuations with a fixed point at $i$ and $j$ (for all $i$ and $j$), etc. Let $D_n$ be the set of permutations with no fixed points (derangements). This gives

$\{D_n\} = \{S_n\} -n\{S_{n-1}\} +\frac{1}{2!}n(n-1) \{S_{n-2}\} +\frac{1}{3!}n(n-1)(n-2)\{S_{n-3}\} \ldots$

One way to calculate the expected number of cycles of length $k$ is by the inclusion-exclusion formula. You can get the set of permuations of length $n$ with no fixed points by taking the set of permutations, subtracting the multiset of permutations with a fixed point at $i$ (for all $i$), adding the multiset of permuations with a fixed point at $i$ and $j$ (for all $i$ and $j$), etc. Let $D_n$ be the set of permutations with no fixed points (derangements). This gives

$\{D_n\} = \{S_n\} -n\{S_{n-1}\} +\frac{1}{2!}n(n-1) \{S_{n-2}\} +\frac{1}{3!}n(n-1)(n-2)\{S_{n-3}\} \ldots$

where $\{S_k\}$ is the set of permutations of length $k$. Now, we can find the number of $k$-cycles on the right-hand side. The expected number of $k$-cycles in $\{S_{n-i}\}$ is $1/k$ if $k\leq n-i$ and $0$ if $k > n-i$. If we make this replacement, and divide by the number of derangements, we find that the expected number of $k$-cycles is

$\frac{1}{k} \cdot \frac{1 -1 +1/2! -1/3! + \ldots \pm 1/(n-k)!}{1 - 1 + 1/2! - 1/3! +\ldots \pm 1/n!}$

For large $n$ and $k\leq n-\log{n}$, this is almost exactly $\frac{1}{k}$. For $k > n-\log{n}$, the expected contribution of the number of cycles from long cycles is quite small, so the expected number of cycles is roughly $\sum_{k=2}^n \frac{1}{k}$.