¿Cuántas colocaciones finales son posibles si el líder cambió 0...5 veces?

Question

Seis competidores A-F participar en la contrarreloj ciclista. La carrera consiste en recorrer varias decenas de kilómetros lo más rápidamente posible. Siguiendo las reglas de este evento deportivo, los competidores salen de uno en uno, a intervalos regulares. Llamemos líder al ciclista que ha recorrido todo el trayecto y que en este momento va en cabeza (por lo que ha hecho el mejor tiempo hasta el momento). La colocación final es la lista que se obtiene al clasificar a los ciclistas según los puestos finales que ocuparon en la carrera. Cuántas colocaciones finales hay en las que:

• A) el líder no cambió desde el principio;
• B) el líder cambió 2 veces;
• C) el líder cambió 3 veces;s
• D) el líder cambió 4 veces;
• E)el líder cambió 5 veces;

Creo que la clave es entender la mecánica del liderazgo. Además no esperan a que el anterior termine así que por ejemplo B puede terminar antes que A. Entonces A ya no puede tomar el liderazgo. Los subproblemas A y E son triviales, A es sólo 5 y E es 1, si no me equivoco.

EDIt: Tengo más información, las respuestas para 3 cambios y 4 cambios son 85 y 15 respectivamente. Buscando una manera que no sea bruteforcing ella.

Answer 1

Tienes razón en cuanto a la A. El primer corredor tiene que ir delante, pero los demás pueden ir en cualquier orden.

Para B, cualquiera de los corredores, excepto A, puede ser el ganador final. Si B es el ganador final, los demás pueden terminar en cualquier orden, por lo que hay $5!$ . Si C es el ganador final, B no puede vencer a A, por lo que hay $\frac 12 \cdot 5!$ . Si D es el ganador final, B y C no pueden vencer a A, por lo que hay $\frac 13 \cdot 5!$ . Si E es el ganador final, $\frac 14\cdot 5!$ y si F es el ganador final, $\frac 15 \cdot 5!$ para un total de $\frac {137}{60}\cdot 120=274$ . $\frac {137}{60}=H_5$ El quinto número armónico .

Para la C hay que fijarse en los dos pilotos que toman la delantera. Al igual que en B, los corredores anteriores al primero en tomar la delantera no pueden vencer a A. Ahora los corredores entre el primero en tomar la delantera y el eventual ganador pueden vencer a A, pero no al líder provisional.

Answer 2

Etiquetar a los jinetes $1,2,\ldots,n$ según su orden de salida. Sus posiciones finales determinan una permutación $\pi=r_1r_2\ldots r_n$ de $[n]$ , donde $r_1$ es el ganador, $r_2$ tiene el segundo mejor tiempo, y así sucesivamente. En $k\in[n]$ dicen que $r_k$ es un mínimo de izquierda a derecha si $r_i>r_k$ para $i<k$ . Si $r_1r_2\ldots r_n$ tiene $m$ mínimos de izquierda a derecha, el liderazgo cambió de manos $m-1$ tiempos.

Por ejemplo, los mínimos de izquierda a derecha de la permutación $463512$ de $[6]$ son $4$ , $3$ y $1$ . El liderazgo cambió de manos primero de $1$ a $3$ y luego de $3$ a $4$ .

Si los mínimos de izquierda a derecha son $r_{k_1}=r_1,r_{k_2},\ldots,r_{k_m}$ , insertar $m$ pares de paréntesis para obtener

$$(r_{k_1}\ldots r_{k_2-1})(r_{k_2}\ldots r_{{k_3}-1})\ldots(r_{k_m}\ldots r_n)\tag{1}$$

e interpretar $(1)$ como una permutación $\varphi(\pi)$ en notación de ciclo. Es bien conocido y fácil de ver que el mapa $\varphi:S_n\to S_n$ es una biyección: dada una permutación $\pi\in S_n$ en notación de ciclo, gire cada ciclo para llevar el elemento más pequeño al frente, ordene los ciclos en orden descendente de elementos más pequeños y elimine los paréntesis para obtener $\varphi^{-1}(\pi)$ . Por lo tanto, el número de resultados en los que el liderazgo cambió de manos $k$ veces es el número de permutaciones de $[n]$ con $k+1$ ciclos.

Esto viene dado por $n\brack{k+1}$ , a Número Stirling del primer tipo . Estos no tienen una forma cerrada agradable, pero satisfacen una bonita recurrencia:

$${{n+1}\brack k}=n{n\brack k}+{n\brack{k-1}}$$

para $k>0$ con valores iniciales ${0\brack 0}=1$ y ${n\brack 0}={0\brack n}=0$ para $n>0$ .

Para el presente caso con $n=6$ tenemos

$${6\brack 1}=120,{6\brack 2}=274,{6\brack 3}=225,{6\brack 4}=85,{6\brack 5}=15,{6\brack 6}=1\,.$$

En resumen, $n\brack k$ es el número de resultados posibles cuando hay $n$ jinetes, $k$ de los cuales son líderes en algún momento de la contrarreloj; este es el número de resultados posibles para $n$ los jinetes cuando el liderazgo cambia de manos $k-1$ tiempos.