Patrón de permutación

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 , lo 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.

Primeros resultados

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 . ${\displaystyle (a-1)(b-1)+1}$ ${\displaystyle 1,2,3,\dots ,a}$ ${\displaystyle b,b-1,\dots ,2,1}$

Orígenes de la informática

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 patrón 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 patrón de permutación “es incluso más interesante que las redes que estábamos caracterizando”. ^[7]

Orígenes enumerativos

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 ( β ⁻¹ )| = |Av _n ( β ^rev )| para todo n , donde β ⁻¹ denota la inversa de β y β ^rev denota la inversa de β . (Estas dos operaciones generan el grupo diedro D ₈ 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 ):

• Stankova (1994) demostró que las permutaciones 1342 y 2413 son equivalentes a Wilf. ^[11]
• Stankova y West (2002) demostraron que para cualquier permutación β , las permutaciones 231 ⊕ β y 312 ⊕ β son equivalentes a Wilf, donde ⊕ denota la operación de suma directa . ^[12]
• Backelin, West y Xin (2007) demostraron que para cualquier permutación β y cualquier entero positivo m , las permutaciones 12.. m ⊕ β y m ...21 ⊕  β son equivalentes a Wilf. ^[13]

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 ⁿ . Esto se conoció como la conjetura de Stanley-Wilf hasta que fue demostrada por Adam Marcus y Gábor Tardos . ^[16]

Clases cerradas

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.

Función de Möbius

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]

Complejidad computacional

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 . ${\displaystyle \tau }$ ${\displaystyle n}$ ${\displaystyle \pi }$ ${\displaystyle k}$ ${\displaystyle \pi }$ ${\displaystyle \tau }$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle 2^{O(k^{2}\log k)}\cdot n}$ ${\displaystyle k}$

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. ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mbox{Av}}(\sigma )}$ ${\displaystyle \sigma }$

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. ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mbox{Av}}(321)}$ ${\displaystyle O(k^{2}n^{6})}$ ${\displaystyle O(kn)}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mbox{Av}}(4321)}$ ${\displaystyle {\mbox{Av}}(\sigma )}$ ${\displaystyle \sigma }$

Densidades de empaquetamiento

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

${\displaystyle \lim _{n\rightarrow \infty }{\frac {{\text{number of copies of }}\beta {\text{ in a }}\beta {\text{-optimal permutation of length }}n}{\displaystyle {n \choose k}}}.}$

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]

Superpatrones

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 ² / e ² , donde e  ≈ 2,71828 es el número de Euler ^[33] y que existen k -superpatrones de longitud ⌈( k ²  + 1)/2⌉. ^[34] Se conjetura que este límite superior es el mejor posible, hasta términos de orden inferior. ^[35]

Generalizaciones

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]

Referencias

1. MacMahon, Percy A. (1915), Análisis combinatorio , Londres: Cambridge University Press, Volumen I, Sección III, Capítulo V.
2. MacMahon (1915), artículos 97 y 98.
3. Knuth, Donald E. (1968), El arte de la programación informática, vol. 1 , Boston: Addison-Wesley, ISBN 0-201-89683-4, MR  0286317, OCLC  155842391.
4. Knuth (1968), Sección 2.2.1, Ejercicios 4 y 5.
5. Knuth (1968), Sección 2.2.1, Ejercicio 13, calificado como M49 en la primera impresión y M48 en la segunda.
6. Tarjan, Robert (1972), "Ordenamiento mediante redes de colas y pilas", Journal of the ACM , 19 (2): 341–346, doi : 10.1145/321694.321704 , MR  0298803, S2CID  13608929.
7. Pratt, Vaughan R. (1973), "Computing permutations with double-ended queues. Parallel stacks and parallel queues", Proc. Quinto Simposio Anual de la ACM sobre Teoría de la Computación (Austin, Texas, 1973) , págs. 268–277, doi : 10.1145/800125.804058 , MR  0489115, S2CID  15740957.
8. Rosenstiehl, Pierre ; Tarjan, Robert (1984), "Códigos de Gauss, gráficos hamiltonianos planares y permutaciones ordenables por pila", Journal of Algorithms , 5 (3): 375–390, doi :10.1016/0196-6774(84)90018-X, MR  0756164.
9. Simion, Rodica ; Schmidt, Frank W. (1985), "Permutaciones restringidas", European Journal of Combinatorics , 6 (4): 383–406, doi : 10.1016/s0195-6698(85)80052-4 , MR  0829358.
10. Claesson, Anders; Kitaev, Sergey (2008), "Clasificación de biyecciones entre permutaciones que evitan 321 y 132", Séminaire Lotharingien de Combinatoire , 60 : B60d, 30pp, arXiv : 0805.1325 , MR  2465405.
11. Stankova, Zvezdelina (1994), "Subsecuencias prohibidas", Matemáticas discretas , 132 (1–3): 291–316, doi : 10.1016/0012-365X(94)90242-9 , MR  1297387.
12. Stankova, Zvezdelina; West, Julian (2002), "Una nueva clase de permutaciones equivalentes a Wilf", Journal of Algebraic Combinatorics , 15 (3): 271–290, arXiv : math/0103152 , doi :10.1023/A:1015016625432, MR  1900628, S2CID  13921676.
13. Backelin, Jörgen; West, Julian; Xin, Guoce (2007), "Equivalencia de Wilf para clases singleton", Advances in Applied Mathematics , 38 (2): 133–149, doi : 10.1016/j.aam.2004.11.006 , MR  2290807.
14. Bóna, Miklós (1997), "Enumeración exacta de permutaciones que evitan el número 1342: un vínculo estrecho con árboles etiquetados y mapas planares", Journal of Combinatorial Theory , Serie A, 80 (2): 257–272, arXiv : math/9702223 , doi :10.1006/jcta.1997.2800, MR  1485138, S2CID  18352890.
15. Gessel, Ira M. (1990), "Funciones simétricas y P -recursividad", Journal of Combinatorial Theory , Serie A, 53 (2): 257–285, doi : 10.1016/0097-3165(90)90060-A , MR  1041448.
16. Marcus, Adam; Tardos, Gábor (2004), "Matrices de permutación excluidas y la conjetura de Stanley-Wilf", Journal of Combinatorial Theory , Serie A, 107 (1): 153–160, doi : 10.1016/j.jcta.2004.04.002 , MR  2063960.
17. Wilf, Herbert (2002), "Patrones de permutaciones", Matemáticas discretas , 257 (2): 575–583, doi : 10.1016/S0012-365X(02)00515-0 , MR  1935750.
18. Sagan, Bruce ; Vatter, Vince (2006), "La función de Möbius de un conjunto de elementos compuestos", Journal of Algebraic Combinatorics , 24 (2): 117–136, arXiv : math/0507485 , doi :10.1007/s10801-006-0017-4, MR  2259013, S2CID  11283347.
19. Burstein, Alexander; Jelinek, Vit; Jelinkova, Eva; Steingrimsson, Einar (2011), "La función de Möbius de permutaciones separables y descomponibles", Journal of Combinatorial Theory , Serie A, 118 (1): 2346–2364, doi : 10.1016/j.jcta.2011.06.002 , MR  2834180, S2CID  13978488.
20. Brignall, Robert; Jelínek, Vit; Kynčl, Jan; Marchant, David (2019), "Ceros de la función de Möbius de permutaciones" (PDF) , Mathematika , 65 (4): 1074–1092, arXiv : 1810.05449 , doi :10.1112/S0025579319000251, MR  3992365, S2CID  53366318
21. Marchant, David (2020), "Permutaciones de 2413 globos y el crecimiento de la función de Möbius", Electronic Journal of Combinatorics , 27 (1): Artículo P1.7, 18 pp, arXiv : 1812.05064 , doi : 10.37236/8554
22. Bose, Prosenjit ; Buss, Jonathan F.; Lubiw, Anna (marzo de 1998), "Coincidencia de patrones para permutaciones", Information Processing Letters , 65 (5): 277–283, doi :10.1016/S0020-0190(97)00209-3
23. Guillemot, Sylvain; Marx, Daniel (2014). "Encontrar pequeños patrones en permutaciones en tiempo lineal". Actas del vigésimo quinto simposio anual ACM-SIAM sobre algoritmos discretos : 20. arXiv : 1307.3073 . doi :10.1137/1.9781611973402.7. ISBN . 978-1-61197-338-9.S2CID1846959  .​
24. Bruner, Marie-Louise; Lackner, Martin (2013), "El panorama computacional de los patrones de permutación", Matemáticas puras y aplicaciones , 24 (2): 83–101, arXiv : 1301.0340
25. Kubica, M.; Kulczyński, T.; Radoszewski, J.; Rytter, W.; Waleń, T. (2013), "Un algoritmo de tiempo lineal para la correspondencia de patrones de permutación consecutiva", Information Processing Letters , 113 (12): 430–433, doi :10.1016/j.ipl.2013.03.015
26. Jelínek, Vít; Kynčl, Jan (2017). "Dureza de la correspondencia de patrones de permutación". Actas del vigésimo octavo simposio anual ACM-SIAM sobre algoritmos discretos, SODA 2017, Barcelona, ​​España, Hotel Porta Fira, 16-19 de enero . SIAM. págs. 378–396. arXiv : 1608.00529 . doi :10.1137/1.9781611974782.24.
27. Guillemot, Sylvain; Vialette, Stéphane (2009), "Correspondencia de patrones para permutaciones que evitan el 321", Algorithms and Computation , Lecture Notes in Computer Science, vol. 5878, págs. 1064–1073, arXiv : 1511.01770 , doi :10.1007/978-3-642-10631-6_107, ISBN 978-3-642-10630-9
28. Albert, Michael ; Lackner, Marie-Louise; Lackner, Martin; Vatter, Vincent (2016), "La complejidad de la coincidencia de patrones para permutaciones que evitan el 321 y fusionadas por sesgo", Matemáticas discretas y ciencias de la computación teórica , 18 (2), arXiv : 1510.06051 , doi :10.46298/dmtcs.1308, S2CID  5827603
29. Jelínek, Vít; Opler, Mical; Pekárek, Jakub (2021). "Cuadrículas de permutaciones y dureza de la coincidencia de patrones". 46.º Simposio internacional sobre fundamentos matemáticos de la informática, MFCS 2021, 23 al 27 de agosto de 2021, Tallin, Estonia . Schloss Dagstuhl - Leibniz-Zentrum für Informatik. págs. 65:1–65:22. arXiv : 2107.10897 . doi : 10.4230/LIPIcs.MFCS.2021.65 .
30. Price, Alkes (1997), Densidades de empaquetamiento de patrones en capas, tesis doctoral, Universidad de Pensilvania, ProQuest  304421853.
31. Albert, Michael H. ; Atkinson, MD; Handley, CC; Holton, DA; Stromquist, W. (2002), "Sobre las densidades de empaquetamiento de las permutaciones", Electronic Journal of Combinatorics , 9 : Artículo R5, 20 pp, doi : 10.37236/1622 , MR  1887086.
32. Presutti, Cathleen Battiste; Stromquist, Walter (2010), "Tasas de empaquetamiento de medidas y una conjetura para la densidad de empaquetamiento de 2413", en Linton, Steve; Ruškuc, Nik; Vatter, Vincent (eds.), Patrones de permutación , London Math. Soc. Lecture Notes, vol. 376, Cambridge University Press, págs. 287–316, doi :10.1017/CBO9780511902499.015, ISBN 978-0-521-72834-8.
33. Arratia, Richard (1999), "Sobre la conjetura de Stanley-Wilf para el número de permutaciones que evitan un patrón dado", Electronic Journal of Combinatorics , 6 : Artículo N1, 4 pp, doi : 10.37236/1477 , MR  1710623.
34. Engen, Michael; Vatter, Vincent (2021), "Contiene todas las permutaciones", American Mathematical Monthly , 128 (1): 4–24, arXiv : 1810.08252 , doi : 10.1080/00029890.2021.1835384
35. Eriksson, Henrik; Eriksson, Kimmo; Linusson, Svante; Wästlund, Johan (2007), "Embalaje denso de patrones en una permutación", Annals of Combinatorics , 11 (3–4): 459–470, doi :10.1007/s00026-007-0329-7, MR  2376116, S2CID  2021533.
36. Babson, Erik; Steingrímsson, Einar (2000), "Patrones de permutación generalizados y una clasificación de las estadísticas mahonianas", Séminaire Lotharingien de Combinatoire , 44 : Artículo de investigación B44b, 18 pp, MR  1758852.
37. West, Julian (1993), "Ordenar dos veces a través de una pila", Theoretical Computer Science , 117 (1–2): 303–313, doi : 10.1016/0304-3975(93)90321-J , MR  1235186.
38. Bousquet-Mélou, Mireille ; Butler, Steve (2007), "Permutaciones tipo bosque", Annals of Combinatorics , 11 (3–4): 335–354, arXiv : math/0603617 , doi :10.1007/s00026-007-0322-1, MR  2376109, S2CID  31236417.

Enlaces externos

Desde 2003 se celebra anualmente una conferencia sobre patrones de permutación:

1. Patrones de permutación 2003, 10 al 14 de febrero de 2003, Universidad de Otago , Dunedin, Nueva Zelanda.
2. Patrones de permutación 2004, 5 al 9 de julio de 2004, Malaspina University-College , Nanaimo, Columbia Británica, Canadá.
3. Patrones de permutación 2005, 7 al 11 de marzo de 2005, Universidad de Florida , Gainesville, Florida, EE. UU.
4. Permutation Patterns 2006, 12 al 16 de junio de 2006, Universidad de Reykjavík , Reykjavík, Islandia.
5. Patrones de permutación 2007, 11 al 15 de junio de 2007, Universidad de St. Andrews , St. Andrews, Escocia.
6. Patrones de permutación 2008, 16 al 20 de junio de 2008, Universidad de Otago , Dunedin, Nueva Zelanda.
7. Permutation Patterns 2009, 13 al 17 de julio de 2009, Università di Firenze , Florencia, Italia.
8. Patrones de permutación 2010, 9 al 13 de agosto de 2010, Dartmouth College , Hanover, New Hampshire, EE. UU.
9. Patrones de permutación 2011, 20 al 24 de junio de 2011, Universidad Politécnica Estatal de California , San Luis Obispo, California, EE. UU.
10. Patrones de permutación 2012, 11 al 15 de junio de 2012, Universidad de Strathclyde , Glasgow, Escocia.
11. Patrones de permutación 2013, 1 al 5 de julio de 2013, Université Paris Diderot , París, Francia.
12. Patrones de permutación 2014, 7 al 11 de julio de 2014, East Tennessee State University , Johnson City, Tennessee, EE. UU.
13. Patrones de permutación 2015, 15 al 19 de junio de 2015, De Morgan House, Londres, Inglaterra.
14. Patrones de permutación 2016, 27 de junio–1 de julio de 2016, Universidad Howard , Washington, DC, EE. UU.
15. Permutation Patterns 2017, 26 al 30 de junio de 2017, Universidad de Reykjavík , Reykjavík, Islandia.
16. Patrones de permutación 2018, 9 al 13 de julio de 2018, Dartmouth College , Hanover, New Hampshire, EE. UU.
17. Patrones de permutación 2019, 17 al 21 de junio de 2019, Universität Zürich , Zürich, Suiza.
18. Taller virtual sobre patrones de permutación 2020, del 30 de junio al 1 de julio de 2020, organizado por la Universidad de Valparaíso , Valparaíso, Indiana, EE. UU.
19. Taller virtual sobre patrones de permutación 2021, del 15 al 16 de junio de 2021, organizado por la Universidad de Strathclyde , Glasgow, Escocia.
20. Patrones de Permutación 2022, 20 al 24 de junio de 2022, Universidad de Valparaíso , Valparaíso, Indiana, EE. UU.
21. Patrones de permutación 2023, 3 al 7 de julio de 2023, Universidad de Borgoña , Dijon, Francia.

Se han celebrado sesiones especiales de la Sociedad Americana de Matemáticas sobre patrones en permutaciones en las siguientes reuniones:

• Reunión seccional de otoño del este, 22 y 23 de septiembre de 2012, Instituto de Tecnología de Rochester , Rochester, Nueva York.
• Reuniones conjuntas de matemáticas, 12 de enero de 2013, San Diego, CA.
• Reunión seccional de otoño central, 20 y 21 de septiembre de 2014, Universidad de Wisconsin-Eau Claire , Eau Claire, WI.
• Reunión seccional de primavera del Este, 7 y 8 de marzo de 2015, Universidad de Georgetown , Washington, DC.

Otras reuniones de patrones de permutación:

• Taller sobre patrones de permutación, 29 de mayo–3 de junio de 2005, Universidad de Haifa , Haifa, Israel.
• Evitación de patrones y clasificación del genoma, del 14 al 19 de febrero de 2016, Schloss Dagstuhl , Wadern, Alemania.
• Genómica, evitación de patrones y mecánica estadística, 4 al 9 de noviembre de 2018, Schloss Dagstuhl , Wadern, Alemania.
• Evitación de patrones, mecánica estadística y complejidad computacional, 19 al 24 de marzo de 2023, Schloss Dagstuhl , Wadern, Alemania.

Otros enlaces:

• PermLab: software para patrones de permutación, mantenido por Michael Albert .
• Base de datos de evitación de patrones de permutación, mantenida por Bridget Tenner.
• PermPAL: The Permutation Pattern Avoidance Library, una base de datos de teoremas derivados algorítmicamente sobre clases de permutación, mantenida por Christian Bean, Émile Nadeau, Jay Pantone y Henning Ulfarsson.