Función “parking”

Estudiamos hoy un tema de Combinatoria, que la teníamos un poco abandonada. Se trata de la función “parking”, o arreglos de aparcamiento. El planteamiento es el siguiente:

Imaginemos un aparcamiento de una empresa, situado en una calle estrecha, en la que no es posible dar marcha atrás, y que contiene n aparcamientos, que numeraremos de 1 a n. Podemos pensar que es el inicio de una jornada de trabajo y que suelen aparcar en ella siempre los mismos n coches.

Puede ocurrir que cada coche tenga preferencia por un determinado aparcamiento. Si llega y está libre, lo ocupa, y si no, como no puede retroceder, ocupa el siguiente que esté libre. Esto hace que no todas las preferencias de los coches sean viables. Unamos en un mismo conjunto ordenado las preferencias de los conductores. Por ejemplo, si n = 3, el conjunto ordenado (2, 1, 1)  es viable, porque el primer coche ocuparía el aparcamiento 2, su preferido. El segundo iría al 1, y el tercero, aunque prefiere el 1, ha de irse al 3, pero aparca.

El arreglo (2, 3, 2) no es válido, ya que el primer coche aparca en el 2, el segundo en el 3, pero el tercero, encuentra ocupado su preferido 2 y también el siguiente, y no puede aparcar. Vemos que una hipótesis poco creíble es que cada conductor se dirige a su aparcamiento preferido ignorando los anteriores.

Imaginemos que su empecinamiento le costaría volver a intentarlo y esta vez ocupar el 1 aunque no fuera su preferido, pero esas son las reglas de este juego.

Simulación

Hemos preparado una hoja de cálculo muy simple para que experimentes qué preferencias son válidas. La tienes alojada en la dirección

http://www.hojamat.es/blog/parking.xlsm

Basta escribir en ella dichas preferencias, ajusta el retardo en segundos para ver bien el proceso, y rellenar las preferencias. Al pulsar los botones “Vaciar parking” e “Intento”, se desarrollará, con el retardo que desees, el proceso de aparcamiento.

En la imagen puedes ver el final del proceso con unas preferencias válidas.

Todos los coches han podido aparcar.

En esta otra imagen hemos creado unas preferencias no válidas.

La plaza tercera se ha quedado vacía y el coche G no ha podido aparcar.

Llamamos coches afortunados (“lucky car”) a aquellos vehículos que aparcan donde ellos prefirieron previamente. En el ejemplo de la imagen son afortunados A, B, C, D, E y F. Si las preferencias se repiten, sólo serán afortunados algunos de los coches pretendientes a una plaza. Se llama salto (“jump”) al número de plazas que ha de desplazarse un coche si no logra su plaza preferida. Es evidente que los afortunados presentan un salto igual a cero.

Criterio de validez

Se puede razonar que una función parking es válida si se pueden ordenar las preferencias en orden creciente, y entonces, cada una de ellas es menor o igual que su número de orden. En caso contrario, si una preferencia fuera mayor, se dejaría una plaza vacía aunque entraran todos los coches, por lo que alguno de ellos quedaría fuera. En el anterior ejemplo (2, 3, 2) ordenamos de forma creciente (2, 2, 3) y observamos que no hay forma de llenar la plaza número 1, que quedaría vacía. Por el contrario, si en el orden creciente no se sobrepasa el número de orden, como en (1, 3, 1), o en orden creciente (1, 1, 3),  sea cual sea el orden de entrada, siempre habrá plaza para todos. Si el orden creciente es válido, cualquier permutación del mismo también lo será.

Con esta condición, no es difícil escribir todas las funciones válidas en su forma ordenada creciente. En el caso de 3 serían

(1, 1, 1) (1, 1, 2) (1, 1, 3) (1, 2, 2) (1, 2, 3)

Ahora le aplicamos a cada una las permutaciones posibles, con lo que nos dará
1+3+3+3+6=16 funciones válidas distintas. Coincide este resultado con la expresión

 En este caso (3+1)^(3-1)=4²=16. Se puede demostrar, mediante teoría de grafos, que esta expresión es válida. En esta dirección puedes leer un esbozo de demostración

http://www-math.mit.edu/~rstan/transparencies/parking.pdf

La idea consiste en añadir otra plaza más de aparcamiento, la n+1 que dejamos vacía, y permitir a los coches otro intento. De esta forma todos aparcarán, aunque se puedan dejar una plaza vacía. El número de opciones ahora será (n+1) elementos para n plazas. El número de funciones es, por tanto, (n+1)ⁿ. Si sometemos al proceso a una traslación módulo n+1, sólo será función válida aquella que deje vacía la plaza n+1. Dividimos y queda (n+1)ⁿ.

Generación de resultados

Las funciones parking ordenadas se pueden obtener mediante construcción directa, ya que sólo hay que tener cuidado de no sobrepasar del índice i en el término a(i). Para valores de n mayores hemos usado nuestra hoja de cálculo Cartesius (no publicada en este momento). Por ejemplo, en la imagen puedes observar las 14 funciones ordenadas para n=4.

Para n=5 resultarían 42 arreglos. En general, el número de funciónes parking ordenadas coincide con los números de Catalan:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,… (http://oeis.org/A000108).

Como tales, se pueden generar con la fórmula

Por ejemplo, C(4)=1/5C(8,4)=70/5=14