En efecto, es posible encontrar el numerador en $p_i(k)$ contando las permutaciones, como se indica a continuación. Estas no suman $1$ para $\sum_{k=1}^n p_i(k)$ porque al cambiar el valor de $k$ en realidad estás modificando tu estrategia, y no hay ninguna razón para que las probabilidades de éxito de las diferentes estrategias sumen $1$ .
Es más fácil ver por qué el autor concluyó que $p_3(2)=\frac36$ observando los posibles ordenamientos que podrían haber tomado los tres candidatos: $$\begin{matrix} \text{Candidate order} & \text{Chosen candidate for k=2}\\ x_1,x_2,x_3 & x_3 \\ x_1,x_3,x_2 & x_2 \\ x_2,x_1,x_3 & x_1 \\ x_2,x_3,x_1 & x_1 \\ x_3,x_1,x_2 & x_1 \\ x_3,x_2,x_1 & x_2 \end{matrix}$$
Ahora es evidente que 3 de los 6 posibles órdenes candidatos dieron como resultado la elección óptima de $x_1$ . Sé que inspeccionar todos los casos puede parecer una respuesta poco satisfactoria, así que ahora derivaré la fórmula general para $p_n(k)$ que espero que proporcione un poco más de información.
A partir de ahora voy a referirme a los candidatos utilizando números (para que $1$ representa el mejor candidato) ya que es más fácil para mí ordenar los números $1,...,n$ que ordenar a los candidatos $x_1,...,x_n$ .
Observamos que si el candidato $2$ fue en la primera $k-1$ pero el candidato $1$ no lo fuera, entonces tendríamos garantizada la elección del candidato $1$ . Así que cualquier pedido que tenga $2$ en la primera $k-1$ posiciones pero no $1$ dará lugar a la elección óptima. El número de maneras en que el candidato $2$ puede estar en la primera $k-1$ sin candidato $1$ estar ahí es ${n-2\choose k-2}(k-1)!$ . Esto se obtiene eligiendo primero qué $k-2$ candidatos estarán en la primera $k-1$ con el candidato $2$ y luego elegir un orden para todos ellos. Después de elegir y ordenar adecuadamente la primera $k-1$ , tenemos que ordenar el resto de $n-k+1$ que, naturalmente, se realiza mediante $(n-k+1)!$ . Por lo tanto, el número total de vías para el candidato $2$ para estar entre los primeros $k-1$ candidatos, pero no candidatos $1$ es
$$(k-1)!{n-2\choose k-2}(n-k+1)!$$
De nuevo, todas estas ordenaciones dan como resultado la elección óptima.
Ahora bien, observamos que si ni $1$ ni $2$ estaban en la primera $k-1$ pero $3$ era, sólo haríamos la elección óptima si $1$ vino antes que $2$ en el siguiente $n-k+1$ números. El número de formas de $3$ para estar en la primera $k-1$ pero no $1$ o $2$ es $(k-1)!{n-3\choose k-2}$ mientras que el número de formas de $1$ para presentarse ante $2$ en el siguiente $n-k+1$ números es $(n-k+1)!\over2$ , dándonos $$(k-1)!{n-3\choose k-2}(n-k+1)!\over2$$ tales ordenamientos. Y, como es de esperar, el número de formas de $4$ para estar en la primera $k-1$ candidatos, pero no $1,2$ o $3$ y para $1$ para presentarse ante $2$ y $3$ en el siguiente $n-k+1$ es
$$(k-1)!{n-4\choose k-2}(n-k+1)!\over 3$$
Lo que estamos haciendo es considerar los casos en los que el mejor candidato en la primera $k-1$ es $t$ y encontrar el número de ordenamientos para cada caso que dan como resultado la elección óptima. Si hacemos esto para todos los candidatos $t$ entonces habremos considerado todos los casos posibles y tendremos el número total de ordenamientos que dan como resultado la elección óptima.
De este modo, se obtiene una fórmula general para $p_n(k)$ :
$$p_n(k)=\cases{\frac{(n-1)!}{n!} &for k=1\\\ \frac1{n!}\sum_{j=1}^{n-1}(k-1)!{{n-j-1\choose k-2}(n-k+1)!\over j}&for k>1}$$
Para $p_4(k)$ obtenemos $$\begin{matrix} k & 1 & 2 & 3 & 4 \\ p_4(k) & \frac {6}{24} & \frac {11}{24} & \frac {10}{24} & \frac {6}{24} \end{matrix}$$
Y para $p_5(k)$ obtenemos $$\begin{matrix} k & 1 & 2 & 3 & 4 & 5\\ p_5(k) & \frac {24}{120} & \frac {50}{120} & \frac {52}{120} & \frac {42}{120} & \frac {24}{120} \end{matrix}$$
ambas coinciden con las soluciones conocidas escritas en su pregunta anterior.
