En matemáticas y en particular en combinatoria , el código de Lehmer es una forma particular de codificar cada posible permutación de una secuencia de n números. Es una instancia de un esquema para numerar permutaciones y es un ejemplo de una tabla de inversión .
El código de Lehmer se nombra en referencia a Derrick Henry Lehmer , pero el código se conocía desde 1888 al menos. [1] [2]
El código
El código de Lehmer hace uso del hecho de que existen
permutaciones de una secuencia de n números. Si una permutación σ está especificada por la secuencia ( σ 1 ,…, σ n ) de sus imágenes de 1,…, n , entonces está codificada por una secuencia de n números, pero no todas esas secuencias son válidas ya que cada número debe ser utilizado solo una vez. Por el contrario, las codificaciones consideradas aquí eligen el primer número de un conjunto de n valores, el siguiente número de un conjunto fijo de n - 1 valores, y así sucesivamente, disminuyendo el número de posibilidades hasta el último número para el que sólo un único valor fijo es permitido; cada secuencia de números elegidos de estos conjuntos codifica una única permutación. Si bien se pueden definir varias codificaciones , el código Lehmer tiene varias propiedades útiles adicionales; es la secuencia
en otras palabras, el término L ( σ ) i cuenta el número de términos en ( σ 1 ,…, σ n ) a la derecha de σ i que son más pequeños que él, un número entre 0 y n - i , teniendo en cuenta n + 1 - i valores diferentes.
Un par de índices ( i , j ) con i < j y σ i > σ j se llama inversión de σ , y L ( σ ) i cuenta el número de inversiones ( i , j ) con i fijo y variable j . De ello se deduce que L ( σ ) 1 + L ( σ ) 2 +… + L ( σ ) n es el número total de inversiones de σ , que también es el número de transposiciones adyacentes que se necesitan para transformar la permutación en la permutación de identidad. . Otras propiedades del código de Lehmer incluyen que el orden lexicográfico de las codificaciones de dos permutaciones es el mismo que el de sus secuencias ( σ 1 ,…, σ n ), que cualquier valor 0 en el código representa un mínimo de derecha a izquierda. en la permutación (es decir, un σ i más pequeño que cualquier σ j a su derecha), y un valor n - i en la posición i significa de manera similar un máximo de derecha a izquierda, y que el código de Lehmer de σ coincide con el número factorial representación del sistema de su posición en la lista de permutaciones de n en orden lexicográfico (numerando las posiciones empezando por 0).
Las variaciones de esta codificación se pueden obtener contando inversiones ( i , j ) para j fijo en lugar de i fijo , contando inversiones con un valor fijo menor σ j en lugar de un índice menor i , o contando no inversiones en lugar de inversiones; si bien esto no produce un tipo de codificación fundamentalmente diferente, algunas propiedades de la codificación cambiarán en consecuencia. En particular, contando las inversiones con un valor fijo menor σ j da la tabla de inversión de σ , que puede verse como el código de Lehmer de la permutación inversa.
Codificación y decodificación
La forma habitual de demostrar que hay n ! diferentes permutaciones de n objetos es observar que el primer objeto se puede elegir de n formas diferentes, el siguiente objeto de n - 1 formas diferentes (porque está prohibido elegir el mismo número que el primero), el siguiente de n - 2 formas diferentes (porque ahora hay 2 valores prohibidos), y así sucesivamente. Al traducir esta libertad de elección en cada paso en un número, se obtiene un algoritmo de codificación, uno que encuentra el código de Lehmer de una permutación dada. No es necesario suponer que los objetos permutados sean números, pero es necesario un ordenamiento total del conjunto de objetos. Dado que los números de código deben comenzar desde 0, el número apropiado para codificar cada objeto σ i es el número de objetos que estaban disponibles en ese punto (por lo que no ocurren antes de la posición i ), pero que son más pequeños que el objeto σ De hecho, elegí. (Inevitablemente, tales objetos deben aparecer en alguna posición j > i , y ( i , j ) será una inversión, lo que muestra que este número es de hecho L ( σ ) i .)
Este número para codificar cada objeto se puede encontrar contando directamente, de varias formas (contando directamente las inversiones, o corrigiendo el número total de objetos más pequeños que uno dado, que es su número de secuencia comenzando desde 0 en el conjunto, por aquellos que son no disponible en su posición). Otro método que existe, pero no es realmente más eficiente, es comenzar con la permutación de {0, 1, ... n - 1 } obtenida al representar cada objeto por su número de secuencia mencionado, y luego para cada entrada x , en orden de izquierda a derecha, corrija los elementos a su derecha restando 1 de todas las entradas (aún) mayores que x (para reflejar el hecho de que el objeto correspondiente ax ya no está disponible). Concretamente, un código de Lehmer para la permutación B, F, A, G, D, E, C de letras, ordenadas alfabéticamente, daría primero la lista de números de secuencia 1,5,0,6,3,4,2, que es sucesivamente transformado
donde la última línea es el código de Lehmer (en cada línea se resta 1 de las entradas más grandes a la derecha del elemento en negrita para formar la siguiente línea).
Para decodificar un código Lehmer en una permutación de un conjunto dado, el último procedimiento puede invertirse: para cada entrada x , en orden de derecha a izquierda, corrija los elementos a su derecha sumando 1 a todos aquellos (actualmente) mayores que o igual ax ; finalmente interprete la permutación resultante de {0, 1,… n - 1 } como números de secuencia (lo que equivale a agregar 1 a cada entrada si se busca una permutación de {1, 2,… n }). Alternativamente, las entradas del código Lehmer pueden procesarse de izquierda a derecha e interpretarse como un número que determina la siguiente elección de un elemento como se indicó anteriormente; esto requiere mantener una lista de elementos disponibles, de la cual se elimina cada elemento elegido. En el ejemplo, esto significaría elegir el elemento 1 de {A, B, C, D, E, F, G} (que es B) y luego el elemento 4 de {A, C, D, E, F, G} (que es F), luego el elemento 0 de {A, C, D, E, G} (dando A) y así sucesivamente, reconstruyendo la secuencia B, F, A, G, D, E, C.
Aplicaciones a combinatoria y probabilidades
Independencia de rangos relativos
El código de Lehmer define una biyección del grupo simétrico S n al producto cartesiano, donde [ k ] designa el conjunto de elementos k. Como consecuencia, bajo la distribución uniforme en S n , el componente L ( σ ) i define una variable aleatoria distribuida uniformemente en [ n - i ] , y estas variables aleatorias son mutuamente independientes , porque son proyecciones sobre diferentes factores de un cartesiano. producto .
Número de mínimos y máximos de derecha a izquierda
Definición: En una secuencia u = (u k ) 1≤k≤n , hay un mínimo de derecha a izquierda (o máximo ) en el rango k si u k es estrictamente más pequeño (o estrictamente más grande) que cada elemento u i con i> k , es decir, a su derecha.
Sea B (k) (resp. H (k) ) el evento "hay un mínimo de derecha a izquierda (resp. Máximo) en el rango k ", es decir, B (k) es el conjunto de las permutacionesque exhiben un mínimo de derecha a izquierda (resp. máximo) en el rango k . Claramente tenemos
Por lo tanto, el número N b (ω) (resp. N h (ω) ) del mínimo de derecha a izquierda (resp. Máximo) para la permutación ω se puede escribir como una suma de variables aleatorias de Bernoulli independientes , cada una con un parámetro respectivo de 1 / k:
De hecho, dado que L (k) sigue la ley uniforme sobre
La función generadora de la variable aleatoria de Bernoulli es
por lo tanto, la función generadora de N b es
(utilizando la notación factorial ascendente ), que nos permite recuperar la fórmula del producto para la función generadora de los números de Stirling de primer tipo (sin signo).
El problema de la secretaria
Este es un problema de parada óptima, un clásico en la teoría de decisiones, estadística y probabilidades aplicadas, donde una permutación aleatoria se revela gradualmente a través de los primeros elementos de su código de Lehmer, y donde el objetivo es parar exactamente en el elemento k como σ ( k) = n, mientras que la única información disponible (los k primeros valores del código de Lehmer) no es suficiente para calcular σ (k).
En palabras menos matemáticas: una serie de n candidatos son entrevistados uno tras otro. El entrevistador debe contratar al mejor solicitante, pero debe tomar su decisión (“Contratar” o “No contratar”) en el acto, sin entrevistar al próximo solicitante (y a fortiori sin entrevistar a todos los solicitantes).
El entrevistador conoce así el rango del k- ésimo solicitante, por lo tanto, en el momento de tomar su k- ésima decisión, el entrevistador conoce solo los k primeros elementos del código de Lehmer, mientras que necesitaría conocerlos todos para realizar una evaluación bien informada. decisión. Para determinar las estrategias óptimas (es decir, la estrategia que maximiza la probabilidad de ganar), las propiedades estadísticas del código de Lehmer son cruciales.
Al parecer, Johannes Kepler expuso claramente este problema de secretaria a un amigo suyo en un momento en que estaba tratando de tomar una decisión y elegir a una de las once posibles novias como su segunda esposa. Su primer matrimonio había sido infeliz, habiendo sido concertado sin que él mismo fuera consultado, por lo que estaba muy preocupado de poder tomar la decisión correcta. [3] [4]
Conceptos similares
Se utilizan dos vectores similares. Uno de ellos a menudo se denomina vector de inversión, por ejemplo, por Wolfram Alpha . Consulte también Inversión (matemáticas discretas) § Vectores relacionados con la inversión .
Referencias
- ^ Lehmer, DH (1960), "Enseñar trucos combinatorios a una computadora", Proc. Simpos. Apl. Matemáticas. Análisis combinatorio, Amer. Matemáticas. Soc. , 10 : 179-193
- ^ Laisant, Charles-Ange (1888), "Sur la numération factorielle, application aux permutations" , Bulletin de la Société Mathématique de France (en francés), 16 : 176-183
- ^ Ferguson, Thomas S. (1989), "Who resolvió el problema de la secretaria?", Statistical Science , 4 (3): 282-289, doi : 10.1214 / ss / 1177012493 , JSTOR 2245639
- ^ http://www.math.upenn.edu/~ted/210F10/References/Secretary.pdf
Bibliografía
- Mantaci, Roberto; Rakotondrajao, Fanja (2001), "Una representación de permutación que sabe lo que significa" euleriano "" , Matemáticas discretas y ciencias informáticas teóricas (4): 101-108, archivado desde el original el 16 de noviembre de 2004
- Knuth, Don (1981), El arte de la programación informática , 3 , Lectura: Addison-Wesley, págs. 12-13