En matemáticas combinatorias y en informática teórica , un patrón de permutación (clásico) 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 entradas que representan el resultado de aplicar la permutación a la secuencia 123...; por ejemplo, la secuencia 213 representa la permutación en tres elementos que intercambia los elementos 1 y 2. Si π y σ son dos permutaciones representadas de esta manera (estos nombres de variable son estándar para las permutaciones y no están relacionados con el número pi ), entonces se dice que π contiene a σ como patrón si alguna subsecuencia de las entradas de π tiene el mismo orden relativo que todas las entradas de σ.
Por ejemplo, la permutación π contiene el patrón 213 siempre que π tiene tres entradas x , y y z que aparecen dentro de π en el orden x ... y ... z pero cuyos valores están ordenados como y < x < z , el mismo que el orden de los valores en la permutación 213.
La permutación 32415 de cinco elementos contiene 213 como patrón de varias maneras diferentes: 3··15, ··415, 32··5, 324·· y ·2·15 forman triples de entradas con el mismo orden que 213. Nótese que las entradas no necesitan ser consecutivas. Cada una de las subsecuencias 315, 415, 325, 324 y 215 se denomina copia , instancia u ocurrencia del patrón. El hecho de que π contenga a σ se escribe de manera más concisa como σ ≤ π.
Si una permutación π no contiene un patrón σ, se dice que π evita σ. La permutación 51342 evita 213; tiene diez subsecuencias de tres entradas, pero ninguna de estas diez subsecuencias tiene el mismo orden que 213.
Se puede argumentar que Percy MacMahon (1915) fue el primero en demostrar un resultado en este campo con su estudio de las "permutaciones reticulares". [1] En particular, MacMahon muestra que las permutaciones que se pueden dividir en dos subsecuencias decrecientes (es decir, las permutaciones que evitan el 123) se cuentan mediante los números Catalan . [2]
Otro resultado histórico temprano en este campo es el teorema de Erdős-Szekeres ; en lenguaje de patrones de permutación, el teorema establece que para cualquier número entero positivo a y b, cada permutación de longitud al menos debe contener 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 ordenación por pila en 1968. [3] Knuth demostró que la permutación π puede ordenarse por una pila si y solo si π evita 231, y que las permutaciones ordenables por pila se enumeran mediante los números Catalan . [4] Knuth también planteó preguntas sobre la ordenació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 ordenación por redes de pilas, [6] mientras que Vaughan Pratt (1973) demostró que la permutación π puede ordenarse por una deque si y solo si para todo k , π evita 5,2,7,4,...,4k + 1,4k - 2,3,4k ,1, y 5,2,7,4,...,4k + 3,4k , 1,4k + 2,3, y cada permutación que pueda obtenerse 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 infinita de permutaciones), no está inmediatamente claro cuánto tiempo lleva decidir si una permutación puede ordenarse por una deque. Rosenstiehl y Tarjan (1984) presentaron posteriormente un algoritmo de tiempo lineal (en la longitud de π) que determina si π puede ordenarse mediante una deque. [8]
En su artículo, Pratt señaló que este orden de patrones de permutación “parece ser el único orden parcial de permutación que surge de una manera simple y natural” y concluyó señalando que “desde un punto de vista abstracto”, el orden de patrones de permutación “es incluso más interesante que las redes que estábamos caracterizando”. [7]
Un objetivo destacado en el estudio de los patrones de permutación es la enumeración de permutaciones que eviten una permutación fija (y normalmente corta) o un conjunto de permutaciones. Sea Av n (B) el conjunto de permutaciones de longitud n que evitan todas las permutaciones del conjunto B . (En el caso de que B sea un singleton, digamos { β }, se utiliza en su lugar la abreviatura Av n ( β ). Como se señaló anteriormente, MacMahon y Knuth demostraron que |Av n (123)| = |Av n (231)| = C n , el n º número de Catalan. Por tanto, se trata de clases combinatorias isomorfas .
Simion & Schmidt (1985) fue el primer artículo que se centró exclusivamente en la enumeración. Entre otros resultados, Simion y Schmidt contaron permutaciones pares e impares que evitaban un patrón de longitud tres, contaron permutaciones que evitaban dos patrones de longitud tres y dieron la primera prueba biyectiva de que las permutaciones que evitan 123 y 231 son equinumerosas. [9] Desde su artículo, se han dado muchas otras biyecciones; véase Claesson & Kitaev (2008) para una descripción general. [10]
En general, si |Av n ( β )| = |Av n ( σ )| para todo n , entonces se dice que β y σ son equivalentes de Wilf . Muchas equivalencias de Wilf se derivan del hecho trivial de que |Av n ( β )| = |Av n ( β −1 )| = |Av n ( β rev )| para todo n , donde β −1 denota el inverso de β y β rev denota el inverso de β . (Estas dos operaciones generan el grupo diedro D 8 con una acción natural sobre las matrices de permutación .) Sin embargo, también hay numerosos ejemplos de equivalencias de Wilf no triviales (como la que existe entre 123 y 231 ):
De estas dos equivalencias de Wilf y las simetrías inversa e inversa, se deduce que hay tres secuencias diferentes |Av n ( β )| donde β tiene una longitud cuatro:
A finales de los años 1980, Richard Stanley y Herbert Wilf conjeturaron que para cada permutación β , existe una constante K tal que |Av n ( β )| < K n . Esto se conoció como la conjetura de Stanley-Wilf hasta que fue demostrada por Adam Marcus y Gábor Tardos . [16]
Una clase cerrada , también conocida como clase patrón , clase de permutación o simplemente clase de permutaciones, es un desfase en el orden de los patrones de permutación. Cada clase puede definirse por las permutaciones mínimas que no se encuentran dentro de ella, su base . Por lo tanto, la base para las permutaciones ordenables por pila es {231}, mientras que la base para las permutaciones ordenables por deque es infinita. La función generadora de una clase es Σ x |π| donde la suma se toma sobre todas las permutaciones π en la clase.
Como el conjunto de permutaciones bajo el orden de contención forma un conjunto parcial , es natural preguntarse por su función de Möbius , un objetivo presentado explícitamente por primera vez por Wilf (2002). [17] El objetivo de tales investigaciones es encontrar una fórmula para la función de Möbius de un intervalo [σ, π] en el conjunto parcial de patrones de permutación que sea más eficiente que la definición recursiva ingenua. El primer resultado de este tipo fue establecido por Sagan y Vatter (2006), quienes dieron una fórmula para la función de Möbius de un intervalo de permutaciones en capas . [18] Más tarde, Burstein et al. (2011) generalizaron este resultado a intervalos de permutaciones separables . [19]
Se sabe que, asintóticamente, al menos el 39,95% de todas las permutaciones π de longitud n satisfacen μ(1, π)=0 (es decir, la función principal de Möbius es igual a cero), [20] pero para cada n existen permutaciones π tales que μ(1, π) es una función exponencial de n . [21]
Dada una permutación (llamada texto ) de longitud y otra permutación de longitud (llamada patrón ), el problema de coincidencia de patrones de permutación (PPM) pregunta si está contenido en . Cuando tanto y se consideran variables, se sabe que el problema es NP-completo , y el problema de contar el número de tales coincidencias es #P-completo . [22] Sin embargo, PPM se puede resolver en tiempo lineal cuando k es una constante. De hecho, Guillemot y Marx [23] demostraron que PPM se puede resolver en tiempo , lo que significa que es manejable con parámetros fijos con respecto a .
Existen varias variantes del problema PPM, como lo estudiaron Bruner y Lackner. [24] Por ejemplo, si se requiere que la coincidencia consista en entradas contiguas, entonces el problema se puede resolver en tiempo polinomial. [25] Se obtiene una variante natural diferente cuando el patrón se restringe a una clase de permutación adecuada . Este problema se conoce como -Patrón PPM y se demostró que se puede resolver en tiempo polinomial para permutaciones separables . [22] Más tarde, Jelínek y Kynčl [26] resolvieron completamente la complejidad de -Patrón PPM al demostrar que se puede resolver en tiempo polinomial cuando es igual a uno de 1, 12, 21, 132, 231, 312 o 213 y NP-completo en caso contrario.
Otra variante es cuando tanto el patrón como el texto están restringidos a una clase de permutación propia , en cuyo caso el problema se llama -PPM. Por ejemplo, Guillemot y Vialette [27] demostraron que -PPM podría resolverse en el tiempo. Albert , Lackner, Lackner y Vatter [28] más tarde redujeron esto a y demostraron que el mismo límite se cumple para la clase de permutaciones fusionadas sesgadas . Además, preguntaron si el problema -PPM puede resolverse en tiempo polinomial para cada clase de permutación propia fija . Esta pregunta fue respondida negativamente por Jelínek y Kynčl, quienes demostraron que -PPM es de hecho NP-completo. [26] Más tarde, Jelínek, Opler y Pekárek [29] demostraron que -PPM es NP-completo para cualquiera de longitud al menos 4 no simétrico a uno de 3412, 3142, 4213, 4123 o 41352.
Se dice que la permutación π es β- óptima si ninguna permutación de la misma longitud que π tiene más copias de β. En su discurso en la reunión SIAM sobre Matemáticas Discretas en 1992, Wilf definió la densidad de empaquetamiento de la permutación β de longitud k como
Un argumento inédito de Fred Galvin muestra que la cantidad dentro de este límite no es creciente para n ≥ k , y por lo tanto el límite existe. Cuando β es monótona, su densidad de empaquetamiento es claramente 1, y las densidades de empaquetamiento son invariantes bajo el grupo de simetrías generadas por inversa e inversa, por lo que para permutaciones de longitud tres, solo hay una densidad de empaquetamiento no trivial. Walter Stromquist (inédito) resolvió este caso al mostrar que la densidad de empaquetamiento de 132 es 2 √ 3 − 3 , aproximadamente 0,46410.
Para permutaciones β de longitud cuatro, hay (debido a simetrías) siete casos a considerar:
Para las tres permutaciones desconocidas, existen límites y conjeturas. Price (1997) utilizó un algoritmo de aproximación que sugiere que la densidad de empaquetamiento de 1324 es de alrededor de 0,244. [30] Birzhan Batkeyev (no publicado) construyó una familia de permutaciones que muestran que la densidad de empaquetamiento de 1342 es al menos el producto de las densidades de empaquetamiento de 132 y 1432, aproximadamente 0,19658. Se supone que esta es la densidad de empaquetamiento precisa de 1342. Presutti y Stromquist (2010) proporcionaron un límite inferior para la densidad de empaquetamiento de 2413. Este límite inferior, que se puede expresar en términos de una integral, es de aproximadamente 0,10474, y se supone que es la densidad de empaquetamiento real. [32]
Un k - superpatrón es una permutación que contiene todas las permutaciones de longitud k . Por ejemplo, 25314 es un 3-superpatrón porque contiene las 6 permutaciones de longitud 3. Se sabe que los k -superpatrones deben tener una longitud de al menos k 2 / e 2 , donde e ≈ 2,71828 es el número de Euler [33] y que existen k -superpatrones de longitud ⌈( k 2 + 1)/2⌉. [34] Se conjetura que este límite superior es el mejor posible, hasta términos de orden inferior. [35]
El tipo de patrón definido anteriormente, en el que las entradas no tienen por qué aparecer consecutivamente, se denomina patrón clásico (de permutación). Si se requiere que las entradas sean consecutivas, el patrón se denomina patrón consecutivo .
Existen varias formas en las que se ha generalizado la noción de "patrón". Por ejemplo, un patrón vincular es una permutación que contiene guiones que indican qué pares adyacentes de entradas no necesariamente deben ocurrir consecutivamente. Por ejemplo, la permutación 314265 tiene dos copias del patrón punteado 2−31−4, dado por las entradas 3426 y 3425. Para un patrón punteado β y cualquier permutación π, escribimos β(π) para el número de copias de β en π. Por lo tanto, el número de inversiones en π es 2−1(π), mientras que el número de descensos es 21(π). Yendo más lejos, el número de valles en π es 213(π) + 312(π), mientras que el número de picos es 231(π) + 132(π). Estos patrones fueron introducidos por Babson y Steingrímsson (2000), quienes demostraron que casi todas las estadísticas mahonianas conocidas podían expresarse en términos de permutaciones vinculares. [36] Por ejemplo, el índice mayor de π es igual a 1−32(π) + 2−31(π) + 3−21(π) + 21(π).
Otra generalización es la de un patrón barrado , en el que algunas de las entradas están barradas. Para que π evite el patrón barrado, β significa que cada conjunto de entradas de π que forman una copia de las entradas no barradas de β se puede extender para formar una copia de todas las entradas de β. West (1993) introdujo este tipo de patrones en su estudio de permutaciones que podrían ordenarse pasándolas dos veces a través de una pila. [37] (Tenga en cuenta que la definición de West de ordenar dos veces a través de una pila no es la misma que ordenar con dos pilas en serie). Otro ejemplo de patrones barrados se da en el trabajo de Bousquet-Mélou y Butler (2007), quienes demostraron que la variedad de Schubert correspondiente a π es localmente factorial si y solo si π evita 1324 y 21 3 54. [38]
Desde 2003 se celebra anualmente una conferencia sobre patrones de permutación:
Se han celebrado sesiones especiales de la Sociedad Americana de Matemáticas sobre patrones en permutaciones en las siguientes reuniones:
Otras reuniones de patrones de permutación:
Otros enlaces: