Código de Lehmer

En matemáticas , y en particular en combinatoria , el código de Lehmer es una forma específica de codificar cada permutación posible de una secuencia de n números. Es un ejemplo de un esquema para numerar permutaciones y una tabla de inversión .

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

El código

El código de Lehmer utiliza el hecho de que hay

n!=n\times (n-1)\times \cdots \times 2\times 1

permutaciones de una secuencia de n números. Si una permutación σ se especifica mediante la secuencia ( _σ₁, ..., σₙ ) de sus imágenes de 1, ..., n , entonces se codifica mediante una secuencia de n números, pero no todas estas 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 solo se permite un único valor fijo; cada secuencia de números elegida de estos conjuntos codifica una única permutación. Si bien se pueden definir varias codificaciones , el código de Lehmer tiene varias propiedades útiles adicionales; es la secuencia

L(\sigma )=(L(\sigma )_{1},\ldots ,L(\sigma )_{n})\quad {\text{donde}}\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 menores 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 denomina inversión de $σ, y$ L $(σ)$ i cuenta el número de inversiones ( _i , j ) con i fijo y j variable. De ello $se$ deduce que $L (σ) 1 + L (σ) 2 + \dots + L (σ) n$ es el número total de inversiones de σ , que también es el número de transposiciones adyacentes necesarias para transformar la permutación en la permutación identidad. Otras propiedades del código de Lehmer incluyen que el _ordenlexicográ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$ menor 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 la 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 un j fijo en lugar de un i fijo , contando inversiones con un valor menor fijo $σ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, contar inversiones con un valor menor fijo $σj$ $da como resultado$ la tabla de inversión de σ , que puede considerarse el código de Lehmer de la permutación inversa.

Codificación y decodificación

La forma habitual de demostrar que existen n ! permutaciones diferentes de n objetos consiste en observar que el primer objeto puede elegirse de $n$ maneras distintas, el siguiente de $n - 1$ maneras distintas (ya que está prohibido elegir el mismo número que el primero), el siguiente de $n - 2$ maneras distintas (porque ahora hay 2 valores prohibidos), y así sucesivamente. Al traducir esta libertad de elección en cada paso a un número, se obtiene un algoritmo de codificación que halla el código de Lehmer de una permutación dada. No es necesario suponer que los objetos permutados sean números, pero sí se requiere un ordenamiento total del conjunto de objetos. Dado que los códigos numéricos deben comenzar desde 0, el número apropiado para codificar cada objeto σ _i es el número de objetos disponibles en ese momento (por lo que no aparecen antes de la posición i ), pero que son menores que el objeto σ _i elegido. (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 efectivamente L ( σ ) _i .)

Este número para codificar cada objeto se puede encontrar mediante conteo directo, de varias maneras (contando directamente las inversiones o corrigiendo el número total de objetos menores que uno dado, que es su número de secuencia comenzando desde 0 en el conjunto, por aquellos que no están disponibles en su posición). Otro método que es in situ, pero no 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, corregir los elementos a su derecha restando 1 a todas las entradas (todavía) mayores que x (para reflejar el hecho de que el objeto correspondiente a x ya no está disponible). Concretamente, un código 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 se transforma sucesivamente

{\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 a 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 procedimiento anterior puede invertirse: para cada entrada x , en orden de derecha a izquierda, se corrigen los elementos a su derecha sumando 1 a todos aquellos (actualmente) mayores o iguales que x ; finalmente, se interpreta 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), 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 la combinatoria y la probabilidad

Independencia de rangos relativos

El código de Lehmer define una biyección del grupo simétrico S _n al producto cartesiano. $[n]\times [n-1]\times \cdots \times [2]\times [1]$ donde [ k ] designa el conjunto de k elementos. $\{0,1,\ldots ,k-1\}$ . 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 producto cartesiano .

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 (respectivamente, un máximo ) en el rango k si u _k es estrictamente menor (respectivamente, estrictamente mayor) 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. un máximo) en el rango k ", es decir, B(k) es el conjunto de las permutaciones $\scriptstyle \ {\mathfrak {S}}_{n}$ que exhiben un mínimo de derecha a izquierda (respectivamente, un máximo) en el rango k . Claramente tenemos

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

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

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

En efecto, como L(k) sigue la ley uniforme en $\scriptstyle \ [\![1,k]\!],$

\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 para la variable aleatoria de Bernoulli $1\!\!1_{B(k)}$ es

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

Por lo tanto, la función generadora de N _b es

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

(utilizando la notación factorial ascendente ), lo que nos permite recuperar la fórmula del producto para 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 la teoría de la decisión , la estadística y las 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 detenerse exactamente en el elemento k tal que σ(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 términos menos matemáticos: se entrevista a una serie de n candidatos uno tras otro. El entrevistador debe contratar al mejor candidato, pero debe tomar su decisión ("Contratar" o "No contratar") en el acto, sin entrevistar al siguiente candidato (y, por supuesto, sin entrevistar a todos los candidatos).

El entrevistador conoce la clasificación del k ^-ésimo solicitante; por lo tanto, al momento de tomar su k ^-ésima decisión, solo conoce los k primeros elementos del código de Lehmer, mientras que necesitaría conocerlos todos para tomar una decisión bien fundamentada. Para determinar las estrategias óptimas (es decir, la estrategia que maximiza la probabilidad de éxito), las propiedades estadísticas del código de Lehmer son cruciales.

Supuestamente, Johannes Kepler le reveló claramente este problema con su secretaria a un amigo suyo en un momento en que estaba tratando de decidirse a elegir entre once posibles novias como su segunda esposa. Su primer matrimonio había sido infeliz, ya que se había concertado sin consultarle, por lo que estaba muy preocupado por poder tomar la decisión correcta. ^{[ 3 ]}

Conceptos similares

También se han utilizado varias construcciones relacionadas. Una de ellas se suele denominar vector de inversión, por ejemplo, por Wolfram Alpha . Véase también Inversión (matemáticas discretas) § Vectores relacionados con la inversión .

Referencias

↑ Lehmer, DH (1960), "Enseñando trucos combinatorios a una computadora", Análisis combinatorio , Actas de simposios en matemáticas aplicadas, vol. 10, pp. 179–193 , doi : 10.1090/psapm/010/0113289 , ISBN 978-0-8218-1310-2, MR 0113289 {{citation}}: Incompatibilidad de ISBN/Fecha ( ayuda )
↑ Laisant, Charles-Ange (1888), "Sur la numération factorielle, application aux permutations" [ Sobre la numeración factorial, aplicación a las permutaciones ] , Bulletin de la Société Mathématique de France (en francés), 16 : 176– 183, doi : 10.24033/bsmf.378
↑ Ferguson, Thomas S. (agosto de 1989), "¿Quién resolvió el problema de la secretaria?" (PDF) , 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 "euleriano"" , Matemáticas Discretas e Informática Teórica (4): 101–108 , archivado del original el 16 de noviembre de 2004.
Knuth, Donald (1981), El arte de la programación informática , vol. 3, Reading: Addison-Wesley, págs . 12–13

[lehmer-1] Lehmer, DH (1960), "Enseñando trucos combinatorios a una computadora", Análisis combinatorio , Actas de simposios en matemáticas aplicadas, vol. 10, pp. 179–193 , doi : 10.1090/psapm/010/0113289 , ISBN 978-0-8218-1310-2, MR 0113289 {{citation}}: Incompatibilidad de ISBN/Fecha ( ayuda )

[laisant-2] Laisant, Charles-Ange (1888), "Sur la numération factorielle, application aux permutations" [ Sobre la numeración factorial, aplicación a las permutaciones ] , Bulletin de la Société Mathématique de France (en francés), 16 : 176– 183, doi : 10.24033/bsmf.378

[ferguson-3] Ferguson, Thomas S. (agosto de 1989), "¿Quién resolvió el problema de la secretaria?" (PDF) , Statistical Science , 4 (3): 282–289 , doi : 10.1214/ss/1177012493 , JSTOR 2245639

[ 1 ]

[ 2 ]

[ 3 ]