Expected value of circles in case of Christmas gifting in a class Let's suppose there is a class of n children, where everyone gives a present to somebody, and it is possible to give a gift to yourself. During the event, the first child stands up, and passes his or her present to somebody, who is then the next one to give. If the person getting the gift already gave away his/her gift there is a circle, and someone who still hasn't given is the next to give. I am wondering about the expected number of such circles.
To be more specific, let us have a permutation of n different elements, and generate a random permutation of the same elements. We write these two permutations under one another, and start from the first permutation's first element. We go to the element that is under this one (the first from the second permutation), and we search it in the first permutation. Then we go to the element under this one, and search that element too. When we get to the starting element, that is one circle, and then we start again from the first unvisited element of the first permutation.
It seems like the expected value is the sum of 1 / k, where k goes from 1 to n. (I got this idea when I was learning about the cycle crossover operator in genetic algorithms, it is the same procedure.)
 A: You are correct, the average number of cycles of a random permutation of $n$ elements is $1+\frac12+\dots+\frac1n$. 
Consider this method for choosing a random permutation. Number the people $1$ to $n$. Have person 1 give a gift to a random person. Next, the receiver of that gift randomly gives a present to one of the $n-1$ people who hasn't received a gift, and so on. This continues until a cycle is completed by someone giving a present to person 1. Then, a new cycle is begun by the smallest index person without a gift randomly giving a present to someone.
At the $i^\text{th}$ step, the current person will have $n-i+1$ people they can give a present to, and exactly one of these people leads to the creation of a new cycle. For example, the first person creates a cycle if they give a gift to themself, which happens with probability $\frac1n$. Therefore, the probability that the $i^\text{th}$ person creates a cycle is $\frac1{n-i+1}$, so the expected number of cycles is $\sum_{i=1}^n \frac1{n-i+1}=\sum_{i=1}^n\frac1i$.
A: Another way to see that the average number of cycles is $1 + \frac12 + \dots + \frac1n$ is to prove something stronger: the average number of cycles of length $k$ is $\frac1k$. 
To see this, we first count the possible cycles of length $k$. There are $\binom nk \cdot (k-1)!$ ways to choose a cycle: we choose $k$ elements out of $n$, and then arrange them cyclically in $(k-1)!$ ways. (That is, we can write the elements down in $k!$ orders, and if we say that each element goes to the next and then the $k^{\text{th}}$ goes back to the first, then there are $k$ different orders that represent each cycle.)
Then we multiply $\binom nk \cdot (k-1)!$, the number of cycles, by the probability that each shows up in a random permutation. This is $\frac1n \cdot \frac1{n-1} \cdot \dots \cdot \frac1{n-k+1}$: the probabilities that each element is mapped to the right next element, multiplied together. Simplifying $$\binom nk \cdot (k-1)! \cdot \frac1n \cdot \frac1{n-1} \cdot \dots \cdot \frac1{n-k+1} = \frac{n!}{k!(n-k)!} \cdot (k-1)! \cdot \frac{(n-k)!}{n!}$$ gives $\frac1k$.
In particular:


*

*for $k=1$, we conclude that the average number of fixed points in a random permutation is $\frac1k = 1$.

*for $k > \frac n2$, there can be only one cycle of length $k$, so $\frac1k$ is the probability that there is a cycle of length $k$.

