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 entradas que representan el resultado de aplicar la permutación a la secuencia 123...; por ejemplo, la secuencia 213 representa la permutación de tres elementos que intercambia 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 se dice π contener σ 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 π tenga 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 como el orden de los valores en la permutación 213. La permutación 32415 en cinco elementos contiene 213 como patrón de varias maneras diferentes: 3··15, ··415, 32··5, 324·· y ·2·15 todos forman tripletas de entradas con el mismo orden que 213. 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 σ 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 entradas, pero ninguna de estas 10 subsecuencias tiene el mismo orden que 213.

primeros resultados

Se puede argumentar que Percy MacMahon  (1915) fue el primero en demostrar un resultado en el 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 123) se cuentan mediante los números catalanes . ^[2]

Otro resultado histórico en este 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 . ${\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 clasificación de pilas en 1968. ^[3] Knuth demostró que la permutación π puede ordenarse mediante una pila si y sólo si π evita 231, y que la ordenable por pila las permutaciones se enumeran mediante 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) demostró que la permutación π puede ordenarse mediante una deque si y sólo 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 toda permutación que se pueda 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 la primera publicada ejemplo de una anticadena infinita de permutaciones), no está inmediatamente claro cuánto tiempo lleva decidir si una permutación puede ordenarse por un deque. Rosenstiehl y Tarjan (1984) presentaron más tarde un algoritmo de tiempo lineal (en la longitud de π) que determina si π puede ordenarse 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 la permutación que surge de una manera simple y natural" y concluye señalando que "desde un punto de vista abstracto", el orden del patrón de permutación "es incluso más interesantes que las redes que estábamos caracterizando”. ^[7]

Orígenes enumerativos

Un objetivo destacado en el estudio de patrones de permutación es la enumeración de permutaciones evitando una permutación fija (y típicamente corta) o un conjunto de permutaciones. Sea Av _n (B) el conjunto de permutaciones de longitud n que evitan todas las permutaciones en el conjunto B (en el caso de que B sea un singleton, digamos β , en su lugar se utiliza la abreviatura Av _n ( β )). Como se señaló anteriormente, MacMahon y Knuth demostraron que |Av _n (123)| = |Av _n (231)| = C _n , el enésimo número catalán. Por tanto, se trata de clases combinatorias isomórficas .

Simion y Schmidt (1985) fueron el primer artículo que se centró únicamente en la enumeración. Entre otros resultados, Simion y Schmidt contaron permutaciones pares e impares evitando un patrón de longitud tres, contaron permutaciones evitando 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; ver un estudio en Claesson y Kitaev (2008). ^[10]

En general, si |Av _n ( β )| = |Av _norte ( σ )| para todo n , entonces se dice que β y σ son equivalentes de Wilf . Muchas equivalencias de Wilf surgen del hecho trivial de que |Av _n ( β )| = |Av _norte ( β ⁻¹ )| = |Av _norte ( β ^rev )| para todo n , donde β ⁻¹ denota la inversa de β y β ^rev denota la inversa de β . (Estas dos operaciones generan el grupo diédrico 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 se encuentra 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 longitud cuatro:

A finales de la década de 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 . ^[dieciséis]

clases cerradas

Una clase cerrada , también conocida como clase de patrón , clase de permutación o simplemente clase de permutaciones, es una alteración en el orden del patrón de permutación. Cada clase puede definirse por las permutaciones mínimas que no se encuentran dentro de ella, su base . Por 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 de todas las permutaciones π en la clase.

función de moebius

Como el conjunto de permutaciones bajo el orden de contención forma un poset , es natural preguntarse acerca de 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 patrón de permutación poset 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] Posteriormente, 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 ambos y se consideran variables, se sabe que el problema es NP-completo y el problema de contar el número de 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 el 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 del PPM, según lo estudiado por 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 -Pattern 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- completar de otra manera. ${\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 adecuada , en cuyo caso el problema se llama -PPM. Por ejemplo, Guillemot y Vialette ^[27] demostraron que -PPM podría resolverse a tiempo. Albert , Lackner, Lackner y Vatter ^[28] posteriormente redujeron esto a y demostraron que el mismo límite se aplica a la clase de permutaciones fusionadas sesgadamente . Además, preguntaron si el problema -PPM se puede resolver en tiempo polinomial para cada clase de permutación adecuada fija . Jelínek y Kynčl respondieron negativamente a esta pregunta y demostraron que -PPM es, de hecho, NP-completo. ^[26] Posteriormente, Jelínek et al. ^[29] mostraron 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 embalaje

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 aumenta para n ≥ k , por lo que el límite existe. Cuando β es monótono, su densidad de empaquetamiento es claramente 1, y las densidades de empaquetamiento son invariantes bajo el grupo de simetrías generadas por inverso y reverso, por lo que para permutaciones de longitud tres, solo hay una densidad de empaquetamiento no trivial. Walter Stromquist (inédito) resolvió este caso demostrando que la densidad de empaquetamiento de 132 es 2 √ 3  − 3, aproximadamente 0,46410.

Para permutaciones β de longitud cuatro, hay (debido a las 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 (inédito) 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 conjetura 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 puede expresarse en términos de una integral, es aproximadamente 0,10474 y se conjetura que es Sea la verdadera densidad de empaquetamiento. ^[32]

Superpatrones

Un k - superpatrón es una permutación que contiene todas las permutaciones de longitud k . Por ejemplo, 25314 es un superpatrón de 3 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

Hay varias formas en 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 las entradas que no necesitan ocurrir consecutivamente (en la definición de patrón normal, no es necesario que las entradas ocurran consecutivamente). Por ejemplo, la permutación 314265 tiene dos copias del patrón discontinuo 2-31-4, dado por las entradas 3426 y 3425. Para un patrón discontinuo β y cualquier permutación π, escribimos β(π) para el número de copias de β en π. Así, 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 del 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 podían ordenarse pasándolas dos veces por una pila. ^[37] (Tenga en cuenta que la definición de West de clasificar dos veces a través de una pila no es lo mismo que ordenar con dos pilas en serie). Otro ejemplo de patrones barrados ocurre en el trabajo de Bousquet-Mélou & Butler (2007), quienes demostraron que la La variedad de Schubert correspondiente a π es localmente factorial si y sólo 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, SEÑOR  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, calificó como M49 en la primera impresión y M48 en la segunda.
6. Tarjan, Robert (1972), "Clasificación 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), "Cálculo de permutaciones con colas de dos extremos. Pilas paralelas y colas paralelas", Proc. Quinto Simposio Anual 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 planos y permutaciones ordenables por pila", Journal of Algorithms , 5 (3): 375–390, doi :10.1016/0196-6774(84)90018-X, SEÑOR  0756164.
9. Simión, Rodica ; Schmidt, Frank W. (1985), "Permutaciones restringidas", European Journal of Combinatorics , 6 (4): 383–406, doi : 10.1016/s0195-6698(85)80052-4 , SEÑOR  0829358.
10. Claesson, Anders; Kitaev, Sergey (2008), "Clasificación de biyecciones entre 321 y 132, evitando permutaciones" (PDF) , Séminaire Lotharingien de Combinatoire , 60 : B60d, 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 , SEÑOR  1297387.
12. Stanková, 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; Oeste, Julián; Xin, Guoce (2007), "Equivalencia de Wilf para clases únicas", Avances en Matemáticas Aplicadas , 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 1342: un vínculo estrecho con árboles etiquetados y mapas planos", Journal of Combinatorial Theory , Serie A, 80 (2): 257–272, arXiv : math/9702223 , doi :10.1006/jcta.1997.2800, SEÑOR  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 , Señor  1041448.
16. Marco, Adán; 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 poset de composición", Journal of Algebraic Combinatorics , 24 (2): 117–136, arXiv : math/0507485 , doi :10.1007/s10801-006-0017-4, SEÑOR  2259013, S2CID  11283347.
19. Burstein, Alejandro; 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 permutaciones de Möbius" (PDF) , Mathematika , 65 (4): 1074–1092, Arxiv : 1810.05449 , doi : 10.1112/s0025579319000251, Mr  3992365, S2cid  5336631818
21. Marchant, David (2020), "Permutaciones de 2413 globos y el crecimiento de la función de Möbius", Electronic Journal of Combinatorics , 27 (1): P1.7, arXiv : 1812.05064 , doi : 10.37236/8554
22. Bose, Prosenjit ; Buss, Jonathan F.; Lubiw, Anna (marzo de 1998), "Coincidencia de patrones para permutaciones", Cartas de procesamiento de información , 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. S2CID  1846959.
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 coincidencia de patrones de permutación consecutiva", Cartas de procesamiento de información , 113 (12): 430–433, doi :10.1016/j.ipl.2013.03.015
26. Jelínek, Vít; Kynčl, enero (2017). "Dureza de la coincidencia 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), "Coincidencia de patrones para permutaciones que evitan 321", Algoritmos y Computación , Lecture Notes in Computer Science, vol. 5878, págs. 1064–1073, arXiv : 1511.01770 , doi : 10.1007/978-3-642-10631-6_107
28. Alberto, Michael ; Lackner, Marie-Louise; Lackner, Martín; Vatter, Vincent (2016), "La complejidad de la coincidencia de patrones para permutaciones fusionadas y que evitan 321", Matemáticas discretas e informática 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 , Ph.D. tesis, Universidad de Pensilvania.
31. Alberto, Michael H .; Atkinson, Doctor en Medicina; Handley, CC; Holton, DA; Stromquist, W. (2002), "Sobre las densidades de empaquetamiento de permutaciones", Electronic Journal of Combinatorics , 9 : artículo de investigación 5, 20 págs, doi : 10.37236/1622 , MR  1887086.
32. Presutti, Cathleen Battiste; Stromquist, Walter (2010), "Tasas de embalaje de medidas y una conjetura para la densidad de embalaje de 2413", en Linton, Steve; Ruškuc, Nik; Vatter, Vincent (eds.), Patrones de permutación , London Math. Soc. Notas de conferencias, vol. 376, Cambridge University Press, págs. 287–316, doi :10.1017/CBO9780511902499.015.
33. Arratia, Richard (1999), "Sobre la conjetura de Stanley-Wilf para el número de permutaciones que evitan un patrón determinado", Electronic Journal of Combinatorics , 6 : N1, 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 clasificación de las estadísticas mahonianas", Séminaire Lotharingien de Combinatoire , 44 : Artículo de investigación B44b, 18 págs., MR  1758852.
37. West, Julian (1993), "Clasificar dos veces en una pila", Informática teórica , 117 (1–2): 303–313, doi : 10.1016/0304-3975(93)90321-J , MR  1235186.
38. Bousquet-Mélou, Mireille ; Butler, Steve (2007), "Permutaciones similares a bosques", 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. Permutation Patterns 2003, 10 al 14 de febrero de 2003, Universidad de Otago , Dunedin, Nueva Zelanda.
2. Permutation Patterns 2004, 5 al 9 de julio de 2004, Malaspina University-College , Nanaimo, Columbia Británica, Canadá.
3. Permutation Patterns 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. Permutation Patterns 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. Permutation Patterns 2011, 20 al 24 de junio de 2011, Universidad Estatal Politécnica 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. Permutation Patterns 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. Permutation Patterns 2015, 15 al 19 de junio de 2015, De Morgan House, Londres, Inglaterra.
14. Patrones de permutación 2016, del 27 de junio al 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 Permutation Patterns 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 Permutation Patterns 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 American Mathematical Society sobre patrones en permutaciones en las siguientes reuniones:

• Reunión seccional del este de otoño, 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 central de otoño, 20 y 21 de septiembre de 2014, Universidad de Wisconsin-Eau Claire , Eau Claire, WI.
• Reunión seccional de primavera del Este, 7 al 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 al 3 de junio de 2005, Universidad de Haifa , Haifa, Israel.
• Evitación de patrones y clasificación del genoma, 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 para evitar patrones de permutación, mantenida por Bridget Tenner.
• PermPAL: Biblioteca para evitar patrones de permutación, 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.