The teacher on probability theory leaned back in his chair and looked at the screen. The list of those who signed up is ready. The total number of people turned out to be \(n\). Only they are not in alphabetical order, but in a random order in which they came to the class.
“We need to sort them alphabetically,” the teacher thought, “I’ll go down in order from the top down, and if necessary I’ll rearrange the student’s name up in a suitable place. Each name should be rearranged no more than once”.
Prove that the mathematical expectation of the number of surnames that you do not have to rearrange is \(1 + 1/2 + 1/3 + \dots + 1/n\).