Función de estacionamiento

Las funciones de estacionamiento son una generalización de las permutaciones estudiadas en combinatoria , una rama de las matemáticas .

Una función de estacionamiento de longitud${\displaystyle n}$es una secuencia de${\displaystyle n}$enteros positivos, cada uno en el rango de 1 a${\displaystyle n}$, con la propiedad de que, para cada${\displaystyle i}$hasta la longitud de la secuencia, la secuencia contiene al menos${\displaystyle i}$valores que son como máximo${\displaystyle i}$. Es decir, debe contener al menos un 1, al menos dos valores que sean 1 o 2, al menos tres valores que sean 1, 2 o 3, etc. De forma equivalente, si la secuencia está ordenada , entonces para cada${\displaystyle i}$en el mismo rango, el${\displaystyle i}$El valor de la secuencia ordenada es como máximo${\displaystyle i}$. ^{[ 1 ]}

Por ejemplo, hay 16 funciones de estacionamiento de longitud tres:

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

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

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

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

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

(1,1,1).

El nombre se explica mediante el siguiente experimento mental . Una secuencia de${\displaystyle n}$conductores en automóviles viajan por una calle de sentido único teniendo${\displaystyle n}$espacios de estacionamiento, donde cada conductor tiene un espacio de estacionamiento preferido. Cada conductor viaja hasta llegar a su espacio preferido y luego estaciona en el primer espacio disponible. Una función de estacionamiento describe las preferencias para las cuales todos los autos pueden estacionar. ^{[ 1 ]} Por ejemplo, la función de estacionamiento (2,1,2,1) describe las preferencias para las cuales el primer y el tercer conductor prefieren el segundo espacio, mientras que los otros dos conductores prefieren el primero. El primer conductor estaciona en el espacio 2, el segundo en el espacio 1 y el tercero en el espacio 3 (porque el espacio 2 está ocupado). El cuarto conductor comienza a buscar un espacio libre en el espacio 1, pero no lo encuentra hasta el espacio 4; todos los espacios anteriores estaban ocupados. La secuencia (3,3,1,3) no es una función de estacionamiento: demasiados conductores prefieren el espacio 3, por lo que el último conductor comienza a buscar un espacio después de haber pasado el único espacio libre y no podrá estacionar. ^{[ 2 ]}

Las funciones de estacionamiento también tienen una aplicación más seria en el estudio de tablas hash basadas en sondeo lineal , una estrategia para colocar claves en una tabla hash que se asemeja mucho a la estrategia de estacionamiento unidireccional para automóviles. ^{[ 3 ]}

El número de funciones de estacionamiento de longitud${\displaystyle n}$es exactamente$${\displaystyle (n+1)^{n-1}.}$$Por ejemplo, para${\displaystyle n=3}$este número es${\displaystyle 4^{2}=16}$. ^{[ 2 ]}

John Riordan atribuye a Henry O. Pollak el siguiente argumento para esta fórmula. En una carretera circular de un solo sentido con${\displaystyle n+1}$espacios, cada uno de${\displaystyle n}$Los coches siempre podrán aparcar, independientemente de la preferencia que tenga cada conductor por su espacio de salida. Hay${\displaystyle (n+1)^{n}}$opciones para las preferencias, cada una de las cuales deja un espacio vacío. Todos los espacios son simétricos entre sí, por lo que por simetría, hay${\displaystyle (n+1)^{n-1}}$opciones para preferencias que dejan espacio${\displaystyle n+1}$como el espacio vacío. Estas opciones son exactamente las funciones de estacionamiento. Las funciones de estacionamiento también se pueden colocar en biyección con los árboles de expansión en un grafo completo con${\displaystyle n+1}$vértices, uno de los cuales se designa como la raíz. Esta biyección, junto con la fórmula de Cayley para el número de árboles de expansión, muestra nuevamente que hay${\displaystyle (n+1)^{n-1}}$funciones de estacionamiento. ^{[ 2 ]}

Numerosas investigaciones han estudiado el número de funciones de estacionamiento de una forma especial. Como caso especial muy simple, las funciones de estacionamiento que permiten que cada automóvil estacione en su lugar preferido son exactamente las permutaciones , contadas por los factoriales . Las funciones de estacionamiento que permiten que cada automóvil estacione en su lugar preferido o en el siguiente lugar se cuentan por los números de Bell ordenados . ^{[ 4 ]}