Name Drawing Puzzle
You're asking for the expected number of cycles in a random permutation with uniform distribution over the symmetric group $S_n$ (with $n=20$). To calculate this, we can calculate the expected number of cycles a single element represents, and multiply by the number $n$ of elements. To find the number of permutations in which element $a$ is in a cycle of length $k$, imagine the $n$ elements in a row, with $a$ at the front, and a separator after the first $k$ elements. If we fill the rest of the row with any of the $(n-1)!$ permutations of the remaining $n-1$ elements, we can regard the resulting row as representing a permutation in which the first $k$ elements form a cycle containing $a$, and the remaining $n-k$ elements stand for a permutation of those elements. This establishes a bijection between the $(n-1)!$ ways of filling the row and the permutations in which $a$ is in a cycle of length $k$. Thus, for every $k$ between $1$ and $n$, there are $(n-1)!$ permutations in which $a$ is in a cycle of length $k$. Being in a cycle of length $k$, the element $a$ contributes $1/k$ cycles to the total number of cycles. Thus, since each permutation has probability $1/n!$ of occurring, the expected number of cycles is
$$n\sum_{k=1}^n(n-1)!\frac1k\frac1{n!}=\sum_{k=1}^n\frac1k=H_n\;,$$
the $n$-th harmonic number.
What you’re asking for is the average number of cycles in a random permutation of $[n]$ in the case $n=20$. (Here $[n]=\{1,\dots,n\}$.
Let $h(n)$ be the average number of cycles in a random permutation of $[n]$; I claim that $h$ satisfies the recurrence $$h(n)=\frac{n-1}nh(n-1)+\frac1n\Big(h(n-1)+1\Big)\;.\tag{1}$$
Proof: Let $\pi$ be any permutation of $\{2,3,\dots,n\}$ written in cycle form. Say that the entries in $\pi$ from left to right, ignoring parentheses, are $\pi_1,\dots,\pi_{n-1}$. Now insert $1$ into $\pi$ in one of the following two ways.
- To the left of $\pi_1$ as $(1)$, forming a cycle of its own.
- Immediately after one of the $\pi_k$, $k=1,\dots,n-1$, in the same cycle as $\pi_k$.
Every permutation of $[n]$ can be uniquely obtained in this way from a unique permutation $\pi$ of $\{2,\dots,n-1\}$.
The average number of cycles of a random permutation of $\{2,\dots,n-1\}$ is of course $h(n-1)$. The recurrence $(1)$ is now an immediate consequence of the fact that operation (1) above increases the number of cycles by $1$ and accounts for $\frac1n$ of all cases, while operation (2) leaves the number of cycles unchanged and accounts for the remaining $\frac{n-1}n$ cases. $\dashv$
Now rewrite $(1)$ as $$h(n)=h(n-1)+\frac1n$$ and note that $h(1)=1$. Then $h(2)=1+\frac12$, $h(3)=h(2)+\frac13=1+\frac12+\frac13$, and an easy induction verifies that in general $$h(n)=H_n=\sum_{k=1}^n\frac1k\;,$$ the $n$-th harmonic number. It is known that $$H_n=\ln n+\gamma+\epsilon_n\;,$$ where $\gamma\approx 0.5772$ is the Euler-Mascheroni constant and $\epsilon\sim\frac1{2n}$.
Added: $H_{20}=\dfrac{55835135}{15519504}\approx 3.59774$. The numerator is taken from A001008 at OEIS and the denominator from A002805.