Hiring problem is discussed in section 5.1 and 5.2 of the CLRS and I'm referring this for exercise solutions.
However, for Exercise question 5.2-2 my solution deviates from the one given in the reference and mine seems be correct. I am still not satisfied with the reasoning of my solution though. Here it goes.
The Question: In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you hire exactly twice?
My solution: 1. First candidate is always going to be hired so all we have to do is to calculate the probability that only one candidate is hired from the remaining n - 1 candidates. So I divided it into n - 1 cases where like
case 1: If the second candidate is hired. (other than the first one only)
case 2: If the third candidate is hired.
and so on..
Now the probability of case 1:
1(anyone will be hired) * 1/2(the probability of this being more than the first) * 2/3(probability of this not being the highest till now) * 3/4 * 4/5 * 5/6.... * (n-1)/n = 1/n
Similarly for case 2: 1 * 1/2 * 1/3(must be highest till now) *1/4... * (n - 1)/n = 1/2n
case 3: 1/3n and n-1 th case : 1/(n-1)*n
so my answer is
1/n * (1 + 1/2 + 1/3 + 1/4... 1/(n-1))
but the solutions pdf mentions
(2^n - n - 1)/n!
My solution seems correct for n == 3 where the answer should be 3/6. So can anyone please validate this approach and guide me if this is wrong.