patrón de permutación
En matemáticas combinatorias e informática teórica , un patrón de permutación es una subpermutación de una permutación más larga . Cualquier permutación puede escribirse en notación de una línea como una secuencia de dígitos que representan el resultado de aplicar la permutación a la secuencia de dígitos 123...; por ejemplo, la secuencia de dígitos 213 representa la permutación de tres elementos que intercambian los elementos 1 y 2. Si π y σ son dos permutaciones representadas de esta manera (estos nombres de variables son estándar para permutaciones y no están relacionados con el número pi ), entonces π es se dice que contiene σ como patrónsi alguna subsecuencia de los dígitos de π tiene el mismo orden relativo que todos los dígitos de σ.
Por ejemplo, la permutación π contiene el patrón 213 siempre que π tenga tres dígitos x , y y z que aparecen dentro de π en el orden x ... y ... z pero cuyos valores están ordenados como y < x < z , lo mismo como el orden de los valores en la permutación 213. La permutación 32415 en cinco elementos contiene 213 como un patrón de varias maneras diferentes: 3··15, ··415, 32··5, 324·· y ·2·15 todos forman triples de dígitos con el mismo orden que 213. Cada una de las subsecuencias 315, 415, 325, 324 y 215 se denomina copia, instancia u ocurrenciadel patrón El hecho de que π contenga σ se escribe de manera más concisa como σ ≤ π. Si una permutación π no contiene un patrón σ, entonces se dice que π evita σ. La permutación 51342 evita 213; tiene 10 subsecuencias de tres dígitos, pero ninguna de estas 10 subsecuencias tiene el mismo orden que 213.
Se puede argumentar que Percy MacMahon ( 1915 ) fue el primero en demostrar un resultado en el campo con su estudio de "permutaciones de celosía". [1] En particular, MacMahon muestra que las permutaciones que se pueden dividir en dos subsecuencias decrecientes (es decir, las permutaciones que evitan 123) se cuentan mediante los números catalanes . [2]
Otro resultado histórico temprano en el campo es el teorema de Erdős-Szekeres ; en el lenguaje de patrones de permutación, el teorema establece que para cualquier número entero positivo a y b , cada permutación de longitud debe contener al menos el patrón o el patrón .
El estudio de los patrones de permutación comenzó en serio con la consideración de Donald Knuth sobre la clasificación por pilas en 1968. [3] Knuth demostró que la permutación π puede clasificarse por una pila si y solo si π evita 231, y que la pila clasificable las permutaciones son enumeradas por los números catalanes . [4] Knuth también planteó preguntas sobre la clasificación con deques . En particular, la pregunta de Knuth sobre cuántas permutaciones de n elementos se pueden obtener con el uso de un deque permanece abierta. [5] Poco después, Robert Tarjan ( 1972 ) investigó la clasificación por redes de pilas,[6] mientras que Vaughan Pratt ( 1973 ) mostró que la permutación π puede ser ordenada por un deque si y solo si para todo k , π evita 5,2,7,4,...,4 k +1,4 k − 2,3,4 k ,1 y 5,2,7,4,...,4 k +3,4 k ,1,4 k +2,3, y cada permutación que se puede obtener de cualquiera de estos intercambiando los dos últimos elementos o el 1 y el 2. [7] Debido a que esta colección de permutaciones es infinita (de hecho, es el primer ejemplo publicado de una anticadena infinitade permutaciones), no está inmediatamente claro cuánto tiempo lleva decidir si una permutación se puede ordenar por un deque. Rosenstiehl y Tarjan (1984) presentaron más tarde un algoritmo de tiempo lineal (en la longitud de π) que determina si π se puede ordenar mediante un deque. [8]
En su artículo, Pratt comentó que este orden de patrón de permutación “parece ser el único orden parcial de permutación que surge de una manera simple y natural” y concluye señalando que “desde un punto de vista abstracto”, el orden de patrón de permutación “es incluso más interesante que las redes que estábamos caracterizando”. [7]