In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you hire exactly one time? What is the probability that you hire exactly \(n\) times?

There are \(n!\) possible candidate orders to consider. If we perform only one hire, this means that the best candidate was in the first position which represents \((n-1)!\) of these possible orders. The probability of this happening is therefore \(\frac{(n-1)!}{n!} = \frac{1}{n}\).

If we perform \(n\) hires, this means that the candidates were in increasing order which represents just one of these possible orders. The probability of this happening is therefore \(\frac{1}{n!}\).