código lehmer

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 un ejemplo de un esquema para permutaciones de numeración y es un ejemplo de tabla de inversión .

El código Lehmer recibe su nombre en referencia a Derrick Henry Lehmer , pero el código se conocía al menos desde 1888. ^{[1] [2]}

El código

El código Lehmer aprovecha el hecho de que existen

${\displaystyle n!=n\times (n-1)\times \cdots \times 2\times 1}$

permutaciones de una secuencia de n números. Si una permutación σ está especificada por la secuencia ( σ ₁ , ..., σ _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 usarse 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 cual sólo se dispone de un único valor fijo. 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

${\displaystyle L(\sigma )=(L(\sigma )_{1},\ldots ,L(\sigma )_{n})\quad {\text{where}}\quad L(\sigma )_{i}=\#\{j>i:\sigma _{j}<\sigma _{i}\},}$

en otras palabras, el término L ( σ ) _i cuenta el número de términos en ( σ ₁ , ..., σ _n ) a la derecha de σ _i que son más pequeños que él, un número entre 0 y n − i , permitiendo 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 . Se deduce que L ( σ ) ₁ + L ( σ ) ₂ + … + 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 identidad. . Otras propiedades del código Lehmer incluyen que el orden lexicográfico de las codificaciones de dos permutaciones es el mismo que el de sus secuencias ( σ ₁ , ..., σ _n ), que cualquier valor 0 en el código representa un derecho a mínimo izquierdo 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 igualmente significa un máximo de derecha a izquierda, y que el código de Lehmer de σ coincide con el Representación del sistema numérico factorial de su posición en la lista de permutaciones de n en orden lexicográfico (numerando las posiciones a partir de 0).

Se pueden obtener variaciones de esta codificación contando inversiones ( i , j ) para j fijo en lugar de i fijo , contando inversiones con un valor fijo más pequeño σ _j en lugar de un índice i más pequeño , 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, contar inversiones con un valor fijo más pequeño σ _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 maneras diferentes, el siguiente objeto de n − 1 maneras diferentes (porque está prohibido elegir el mismo número que el primero), el siguiente de n − 2 maneras 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 que encuentra el código de Lehmer de una permutación dada. No es necesario suponer que los objetos permutados sean números, pero sí 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 (para que no aparezcan 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 demuestra que este número es de hecho L ( σ ) _i .)

Este número para codificar cada objeto se puede encontrar contando directamente, de varias maneras (contando directamente inversiones, o corrigiendo el número total de objetos menores que uno determinado, que es su número de secuencia a partir de 0 en el conjunto, por los que están no disponible en su posición). Otro método que existe, pero que no es realmente más eficiente, es comenzar con la permutación de {0, 1, ... n − 1 } obtenida representando 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 a x 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 transformados sucesivamente

${\displaystyle {\begin{matrix}\mathbf {1} &5&0&6&3&4&2\\1&\mathbf {4} &0&5&2&3&1\\1&4&\mathbf {0} &4&2&3&1\\1&4&0&\mathbf {3} &1&2&0\\1&4&0&3&\mathbf {1} &2&0\\1&4&0&3&1&\mathbf {1} &0\\1&4&0&3&1&1&\mathbf {0} \\\end{matrix}}}$

donde la última línea es el código 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 se puede invertir: 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 sumar 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 . ${\displaystyle [n]\times [n-1]\times \cdots \times [2]\times [1]}$ ${\displaystyle \{0,1,\ldots ,k-1\}}$

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 (resp. máximo ) en el rango k si u _k es estrictamente más pequeño (resp. 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 permutaciones que exhiben un Mínimo a la izquierda (resp. máximo) en el rango k . claramente tenemos ${\displaystyle \scriptstyle \ {\mathfrak {S}}_{n}}$

${\displaystyle \{\omega \in B(k)\}\Leftrightarrow \{L(k,\omega )=0\}\quad {\text{and}}\quad \{\omega \in H(k)\}\Leftrightarrow \{L(k,\omega )=k-1\}.}$

Por lo tanto, el número N _b (ω) (resp. N _h (ω) ) de mínimo de derecha a izquierda (resp. máximo) para la permutación ω se puede escribir como una suma de variables aleatorias independientes de Bernoulli, cada una con un parámetro respectivo de 1/k :

${\displaystyle N_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{B(k)}\quad {\text{and}}\quad N_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{H(k)}.}$

De hecho, como L(k) sigue la ley uniforme sobre ${\displaystyle \scriptstyle \ [\![1,k]\!],}$

${\displaystyle \mathbb {P} (B(k))=\mathbb {P} (L(k)=0)=\mathbb {P} (H(k))=\mathbb {P} (L(k)=k-1)={\tfrac {1}{k}}.}$

La función generadora de la variable aleatoria de Bernoulli es ${\displaystyle 1\!\!1_{B(k)}}$

${\displaystyle G_{k}(s)={\frac {k-1+s}{k}},}$

por lo tanto la función generadora de N _b es

${\displaystyle G(s)=\prod _{k=1}^{n}G_{k}(s)\ =\ {\frac {s^{\overline {n}}}{n!}}}$

(usando la notación factorial ascendente ), que nos permite recuperar la fórmula producto de la función generadora de los números de Stirling de primera especie (sin signo).

El problema de la secretaria

Este es un problema de parada óptima, un clásico en teoría de la decisión, estadística y probabilidades aplicadas, donde una permutación aleatoria se revela gradualmente a través de los primeros elementos de su código Lehmer, y donde el objetivo es detenerse 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: se entrevista a una serie de n candidatos, 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 siguiente solicitante (y a fortiori sin entrevistar a todos los solicitantes).

Por lo tanto, el entrevistador conoce el rango del k ^-ésimo solicitante, por lo tanto, en el momento de tomar su k ^-ésima decisión, el entrevistador conoce sólo los k primeros elementos del código Lehmer, mientras que necesitaría conocerlos todos para tomar una decisió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 Lehmer son cruciales.

Al parecer, Johannes Kepler expuso claramente este problema de secretaria a un amigo suyo en un momento en el que intentaba tomar una decisión y elegir a una de once posibles novias como su segunda esposa. Su primer matrimonio había sido infeliz, ya que se había concertado sin que él mismo fuera consultado, por lo que le preocupaba mucho poder tomar la decisión correcta. ^[3]

Conceptos similares

Se utilizan dos vectores similares. Uno de ellos es a menudo llamado vector de inversión, por ejemplo por Wolfram Alpha . Véase también Inversión (matemáticas discretas) § Vectores relacionados con la inversión .

• Portal de matemáticas

Referencias

1. Lehmer, DH (1960), "Enseñanza de trucos combinatorios a una computadora", Proc. Simposios. Aplica. Matemáticas. Análisis combinatorio, Amer. Matemáticas. Soc. , 10 : 179-193
2. 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
3. Ferguson, Thomas S. (1989), "¿Quién resolvió el problema de la secretaria?", Statistical Science , 4 (3): 282–289, doi : 10.1214/ss/1177012493 , JSTOR  2245639

Bibliografía

• Mantaci, Roberto; Rakotondrajao, Fanja (2001), "Una representación de permutación que sabe lo que significa" eulerian "", Matemáticas discretas e informática teórica (4): 101–108, archivado desde el original el 16 de noviembre de 2004
• Knuth, Don (1981), El arte de la programación informática , vol. 3, lectura: Addison-Wesley, págs. 12-13