Enumeraciones de clases de permutación específicas

En el estudio de los patrones de permutación , ha habido un interés considerable en enumerar clases de permutación específicas , especialmente aquellas con relativamente pocos elementos de base. Esta área de estudio ha revelado casos inesperados de equivalencia de Wilf , donde dos clases de permutación aparentemente no relacionadas tienen la misma cantidad de permutaciones de cada longitud.

Clases que evitan un patrón de longitud 3

Hay dos clases de simetría y una única clase Wilf para permutaciones simples de longitud tres.

Clases que evitan un patrón de longitud 4

Hay siete clases de simetría y tres clases de Wilf para permutaciones simples de longitud cuatro.

No se conoce ninguna fórmula no recursiva que cuente 1324 permutaciones que eviten la enumeración. Marinov y Radoičić (2003) dieron una fórmula recursiva. Johansson y Nakamura (2014) dieron un algoritmo más eficiente que utiliza ecuaciones funcionales, que fue mejorado por Conway y Guttmann (2015) y luego mejorado por Conway, Guttmann y Zinn-Justin (2018), quienes dan los primeros 50 términos de la enumeración. Bevan et al. (2017) han proporcionado límites inferiores y superiores para el crecimiento de esta clase.

Clases que evitan dos patrones de longitud 3

Hay cinco clases de simetría y tres clases de Wilf, todas las cuales fueron enumeradas en Simion y Schmidt (1985).

Clases que evitan un patrón de longitud 3 y uno de longitud 4

Hay dieciocho clases de simetría y nueve clases de Wilf, todas ellas enumeradas. Para consultar estos resultados, véase Atkinson (1999) o West (1996).

Clases que evitan dos patrones de longitud 4

Mapas de calor de clases evitando dos patrones de longitud 4.

Existen 56 clases de simetría y 38 clases de equivalencia de Wilf. Solo 3 de ellas permanecen sin enumerar, y Albert et al. (2018) conjeturan que sus funciones generadoras no satisfacen ninguna ecuación diferencial algebraica (ADE); en particular, su conjetura implicaría que estas funciones generadoras no son D-finitas .

A la derecha se muestran los mapas de calor de cada una de las clases no finitas. Se utiliza la simetría mínima lexicográfica para cada clase y las clases están ordenadas en orden lexicográfico. Para crear cada mapa de calor, se tomaron muestras aleatorias y uniformes de un millón de permutaciones de longitud 300 de la clase. El color del punto representa cuántas permutaciones tienen valor en el índice . Se pueden obtener versiones de mayor resolución en PermPal ${\displaystyle (i,j)}$ ${\displaystyle j}$ ${\displaystyle i}$

Véase también

• Permutación de Baxter
• Permutación aleatoria de riffles

Referencias

• Albert, Michael H. ; Elder, Murray; Rechnitzer, Andrew; Westcott, P.; Zabrocki, Mike (2006), "Sobre el límite de Stanley-Wilf de 4231: evitando permutaciones y una conjetura de Arratia", Advances in Applied Mathematics , 36 (2): 96–105, doi : 10.1016/j.aam.2005.05.007 , hdl : 10453/98769 , MR  2199982.
• Albert, Michael H. ; Atkinson, MD; Brignall, Robert (2011), "La enumeración de permutaciones evitando 2143 y 4231" (PDF) , Matemáticas puras y aplicaciones , 22 : 87–98, arXiv : 1108.0989 , MR  2924740.
• Albert, Michael H. ; Atkinson, MD; Brignall, Robert (2012), "La enumeración de tres clases de patrones utilizando clases de cuadrícula monótona", Electronic Journal of Combinatorics , 19 (3): Artículo 20, 34 pp, doi : 10.37236/2442 , MR  2967225.
• Albert, Michael H. ; Atkinson, MD; Vatter, Vincent (2009), "Contar 1324, 4231: evitar permutaciones", Electronic Journal of Combinatorics , 16 (1): Artículo 136, 9 pp, arXiv : 1102.5568 , doi :10.37236/225, MR  2577304.
• Albert, Michael H. ; Atkinson, MD; Vatter, Vincent (2014), "Inflaciones de clases de cuadrículas geométricas: tres estudios de caso" (PDF) , Australasian Journal of Combinatorics , 58 (1): 27–47, MR  3211768.
• Albert, Michael H. ; Homberger, Cheyne; Pantone, Jay; Shar, Nathaniel; Vatter, Vincent (2018), "Generación de permutaciones con contenedores restringidos", Journal of Combinatorial Theory, Serie A , 157 : 205–232, arXiv : 1510.00269 , doi :10.1016/j.jcta.2018.02.006, MR  3780412.
• Atkinson, MD (1998), "Permutaciones que son la unión de una subsecuencia creciente y una decreciente", Electronic Journal of Combinatorics , 5 : Documento 6, 13 pp, doi : 10.37236/1344 , MR  1490467.
• Atkinson, MD (1999), "Permutaciones restringidas", Matemáticas discretas , 195 (1–3): 27–38, doi :10.1016/S0012-365X(98)00162-9, MR  1663866.
• Atkinson, MD; Sagan, Bruce E .; Vatter, Vincent (2012), "Contar (3+1) - evitar permutaciones", European Journal of Combinatorics , 33 : 49–61, doi : 10.1016/j.ejc.2011.06.006 , MR  2854630.
• Bevan, David (2015), "Permutaciones que evitan 1324 y patrones en los caminos de Łukasiewicz", J. London Math. Soc. , 92 (1): 105–122, arXiv : 1406.2890 , doi :10.1112/jlms/jdv020, MR  3384507.
• Bevan, David (2016a), "Las clases de permutación Av(1234,2341) y Av(1243,2314)" (PDF) , Australasian Journal of Combinatorics , 64 (1): 3–20, MR  3426209.
• Bevan, David (2016b), "La clase de permutación Av(4213,2143)", Matemáticas discretas y ciencias de la computación teórica , 18 (2): 14 pp, arXiv : 1510.06328 , doi :10.46298/dmtcs.1309.
• Bevan, David ; Brignall, Robert; Elvey Price, Andrew; Pantone, Jay (2017), Una caracterización estructural de Av(1324) y nuevos límites para su tasa de crecimiento , arXiv : 1711.10325 , Bibcode :2017arXiv171110325B.
• Bloom, Jonathan; Vatter, Vincent (2016), "Dos viñetas sobre la colocación de torres completas" (PDF) , Australasian Journal of Combinatorics , 64 (1): 77–87, MR  3426214.
• Bóna, Miklós (1997), "Enumeración exacta de permutaciones que evitan el error 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.
• Bóna, Miklós (1998), "Las clases de permutación equinumerosas a la clase suave", Electronic Journal of Combinatorics , 5 : Paper 31, 12 pp, doi : 10.37236/1369 , MR  1626487.
• Bóna, Miklós (2015), "Un nuevo récord para permutaciones que evitan el número 1324", European Journal of Mathematics , 1 (1): 198–206, arXiv : 1404.4033 , doi :10.1007/s40879-014-0020-6, MR  3386234.
• Callan, David (2013a), "El número de permutaciones que evitan {1243, 2134}", Matemáticas discretas y ciencias de la computación teórica , arXiv : 1303.3857 , Bibcode :2013arXiv1303.3857C, doi :10.46298/dmtcs.5287.
• Callan, David (2013b), "Las permutaciones que evitan 4321 y 3241 tienen una función generadora algebraica", Matemáticas discretas y ciencias de la computación teórica , arXiv : 1306.3193 , Bibcode :2013arXiv1306.3193C, doi :10.46298/dmtcs.5286.
• Conway, Andrew; Guttmann, Anthony (2015), "Sobre 1324: cómo evitar las permutaciones", Advances in Applied Mathematics , 64 : 50–69, doi :10.1016/j.aam.2014.12.004, MR  3300327.
• Conway, Andrew; Guttmann, Anthony; Zinn-Justin, Paul (2018), "1324: una revisión de la evitación de permutaciones", Advances in Applied Mathematics , 96 : 312–333, arXiv : 1709.01248 , doi :10.1016/j.aam.2018.01.002.
• 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.
• Johansson, Fredrik; Nakamura, Brian (2014), "Uso de ecuaciones funcionales para enumerar 1324, evitando permutaciones", Advances in Applied Mathematics , 56 : 20–34, arXiv : 1309.7117 , doi :10.1016/j.aam.2014.01.006, MR  3194205.
• Knuth, Donald E. (1968), El arte de la programación informática, vol. 1 , Boston: Addison-Wesley, ISBN 978-0-201-89683-1, MR  0286317, OCLC  155842391.
• Kremer, Darla (2000), "Permutaciones con subsecuencias prohibidas y un número de Schröder generalizado", Discrete Mathematics , 218 (1–3): 121–130, doi :10.1016/S0012-365X(99)00302-7, MR  1754331.
• Kremer, Darla (2003), "Posdata: "Permutaciones con subsecuencias prohibidas y un número de Schröder generalizado"", Matemáticas discretas , 270 (1–3): 333–334, doi :10.1016/S0012-365X(03)00124-9, MR  1997910.
• Kremer, Darla; Shiu, Wai Chee (2003), "Matrices de transición finitas para permutaciones que evitan pares de patrones de longitud cuatro", Discrete Mathematics , 268 (1–3): 171–183, doi :10.1016/S0012-365X(03)00042-6, MR  1983276.
• Le, Ian (2005), "Clases Wilf de pares de permutaciones de longitud 4", Electronic Journal of Combinatorics , 12 : Documento 25, 27 pp, doi : 10.37236/1922 , MR  2156679.
• MacMahon, Percy A. (1916), Análisis combinatorio , Londres: Cambridge University Press, MR  0141605.
• Marinov, Darko; Radoičić, Radoš (2003), "Contando 1324: evitando permutaciones", Electronic Journal of Combinatorics , 9 (2): Documento 13, 9 págs, doi : 10.37236/1685 , MR  2028282.
• Miner, Sam (2016), Enumeración de varias clases de dos por cuatro , arXiv : 1610.01908 , Bibcode :2016arXiv161001908M.
• Miner, Sam; Pantone, Jay (2018), Completando el análisis estructural de las clases de permutación 2x4 , arXiv : 1802.00483 , Bibcode :2018arXiv180200483M.
• Pantone, Jay (2017), "La enumeración de permutaciones evitando 3124 y 4312", Annals of Combinatorics , 21 (2): 293–315, arXiv : 1309.0832 , doi :10.1007/s00026-017-0352-2.
• 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.
• Vatter, Vincent (2012), "Encontrar codificaciones de inserción regulares para clases de permutación", Journal of Symbolic Computation , 47 (3): 259–265, arXiv : 0911.2683 , doi :10.1016/j.jsc.2011.11.002, MR  2869320.
• West, Julian (1996), "Generación de árboles y subsecuencias prohibidas", Discrete Mathematics , 157 (1–3): 363–374, doi :10.1016/S0012-365X(96)83023-8, MR  1417303.

Enlaces externos

La base de datos de evitación de patrones de permutación, mantenida por Bridget Tenner , contiene detalles de la enumeración de muchas otras clases de permutación con relativamente pocos elementos base.