Problem with Exercise 5.2-2 about clrs HOT 3 CLOSED

I think the solution is already take these cases into account.

Here I replace your k with i for clear explanation according to the parameters I used in the solution.

The first candidate hired must have index = 1, and here you say that it's rank is i (where i = 3). If we directly hire the candidate with index = 2 and its rank is n (where n is the highest), this is one of the condition that

Let E_i be the event in which candidate 1 has rank i (where i = 3).

Since n = 6, the candidates with 3 < rank < 6 (i.e., rank = 4 & 5) must be interviewed after candidate with rank = 6 (We don't care about where candidates with rank 1 and rank 2 are). And the probability is calculated by:

S[All events of the order of the candidates with rank 4, rank 5 and rank 6] = {645, 654, 465, 456, 546, 564}

P[candidates with rank 4 and rank 5 are both after rank 6] = 2 / 6 = 1 / 3.

I think you are confused because you think that there are no candidates between candidate 1 (rank = i) and candidate 2 (rank = n), but this condition is still in the the cases. We mainly focus on one thing: all candidates with "i < rank < n" must be interviewed after the one who has the highest rank n.

Is this clear for you?

from clrs.

thanks for your answer I'll study it as soon I have time.

from clrs.

After review, the solution is actually right, it is just another way to see things. I tried a solution more combinatory but far less efficient even if I get the same result

   @Test
    public void hireTwiceTestMethod1() {

        double total = 0;
        //for each rank for the candidate 1 [ 1, n [
        for (int i = 1; i <= n - 1; i++) {
            //for each number of candidates with a rank < i, checked before the candidate with rank n 
            for (int b = 0; b <= i - 1; b++) {
               //here we have a number of arrangements  of b candidates with rank < i 
               //multiplied by the number of of arrangements of candidates after the one with rank n
               //so after the rank n is hired you can have candidates with rank < i and all the ones with rank  > i
                total += (factorial(i - 1) / factorial(i - 1 - b)) * factorial(n - b - 2);
            }
        } 

        double rs = total / factorial(n);

        System.out.println(rs);
    }

the result is the same than with this procedure from the official solution manual

   @Test
    public void hireTwiceTestMethod2() {

        double rs = nThHarmonicNumber(n - 1) / n;

        System.out.println(rs);
    }

other procedures

    public static double factorial(double n) {

        if (n <= 1) {
            return 1;
        }

        return n * factorial(n - 1);
    }

    public static double nThHarmonicNumber(double n){

        double total = 0;

        while( n >= 1 ){

            total += 1.0 / n;

            n --;
        }

        return total;
    }

from clrs.