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 base. Esta área de estudio ha revelado casos inesperados de equivalencia de Wilf , donde dos clases de permutación aparentemente no relacionadas tienen el mismo número de permutaciones de cada longitud.

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

Existen 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 permutaciones que eviten 1324. Marinov y Radoičić (2003) dieron una fórmula recursiva . Johansson y Nakamura (2014) dieron un algoritmo más eficiente que utiliza ecuaciones funcionales , el cual fue mejorado por Conway y Guttmann (2015) , y luego mejorado aún más por Conway, Guttmann y Zinn-Justin (2018), quienes dan los primeros 50 términos de la enumeración. Bevan et al. (2020) actualmente tienen los mejores límites inferiores y superiores rigurosamente establecidos para la tasa de crecimiento de esta clase, habiendo establecido que esta tasa de crecimiento se encuentra en el intervalo [10.271, 13.5].

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

Existen dieciocho clases de simetría y nueve clases de Wilf, todas ellas enumeradas. Para más información sobre estos resultados, véase Atkinson (1999) o West (1996) .

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

Los mapas de calor de cada una de las clases no finitas se muestran a la derecha, según Albert et al. (2024) . Se utiliza la simetría lexicográfica mínima para cada clase, y las clases están ordenadas lexicográficamente. Para crear cada mapa de calor, se muestrearon uniformemente al azar un millón de permutaciones de longitud 300 de la clase. El color del punto${\displaystyle (i,j)}$representa cuántas permutaciones tienen valor${\displaystyle j}$en el índice${\displaystyle i}$Las versiones de mayor resolución se pueden obtener en PermPal .

• permutación de Baxter
• permutación de barajado en cascada

• Albert, Michael H.; Elder, Murray; Rechnitzer, Andrew; Westcott, P.; Zabrocki, Mike (2006), "Sobre el límite de Stanley - Wilf de permutaciones que evitan 4231 y una conjetura de Arratia", Advances in Applied Mathematics , 36 (2): 96–105 , arXiv : math/0502504 , 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ótonas" , 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), "Contando 1324, 4231 permutaciones que evitan" , 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. ; Bean, Christian; Claesson, Anders; Nadeau, Émile; Pantone, Jay; Ulfarsson, Henning (2024), "Exploración combinatoria: un marco algorítmico para la enumeración", arXiv : 2202.07715 [ math.CO ].
• 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 R6: Artículo 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), "Conteo de permutaciones que evitan (3+1)", 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 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) 1309: 14 pp, arXiv : 1510.06328 , doi : 10.46298/dmtcs.1309.
• Bevan, David ; Brignall, Robert; Elvey Price, Andrew; Pantone, Jay (2020), "Una caracterización estructural de Av(1324) y nuevos límites para su tasa de crecimiento", European Journal of Combinatorics , 88 103115: 1– 29, arXiv : 1711.10325 , doi : 10.1016/j.ejc.2020.103115.
• Bloom, Jonathan; Vatter, Vincent (2016), "Dos viñetas sobre colocaciones completas de torres" (PDF) , Australasian Journal of Combinatorics , 64 (1): 77–87 , MR 3426214 .
• Bóna, Miklós (1997), "Enumeración exacta de permutaciones que evitan 1342: un vínculo estrecho con árboles etiquetados y mapas planares", Journal of Combinatorial Theory, Series 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 R31: Artículo 31, 12 pp, doi : 10.37236/1369 , MR 1626487 .
• Bóna, Miklós (2015), "Un nuevo récord para permutaciones que evitan 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 5287, arXiv : 1303.3857 , doi : 10.46298/dmtcs.5287.
• Callan, David (2013b), "Las permutaciones que evitan 4321 y 3241 tienen una función generadora algebraica", Discrete Mathematics & Theoretical Computer Science 5286, arXiv : 1306.3193 , doi : 10.46298/dmtcs.5286.
• Conway, Andrew; Guttmann, Anthony (2015), "Sobre permutaciones que evitan 1324", 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-avoiding permutations revisited", 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 recursividad P", 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 permutaciones que evitan 1324", 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", Matemáticas Discretas , 218 ( 1–3 ): 121–130 , doi : 10.1016/S0012-365X(99)00302-7 , MR 1754331 .
• Kremer, Darla (2003), "Postscript: "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", Matemáticas Discretas , 268 ( 1–3 ): 171–183 , doi : 10.1016/S0012-365X(03)00042-6 , MR 1983276 .
• Le, Ian (2005), "Clases de Wilf de pares de permutaciones de longitud 4" , Electronic Journal of Combinatorics , 12 R25: Artículo 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 [ math.CO ].
• Miner, Sam; Pantone, Jay (2018), "Completando el análisis estructural de las clases de permutación 2x4", arXiv : 1802.00483 [ math.CO ].
• Pantone, Jay (2017), "La enumeración de permutaciones que evitan 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 (2006), "Árboles generadores con etiquetas finitas y permutaciones restringidas", Journal of Symbolic Computation , 41 (5): 559– 572, arXiv : math/0309238 , doi : 10.1016/j.jsc.2005.10.003 , MR 2209164 .
• Vatter, Vincent (2012), "Finding regular insertion encodings for permutation classes", 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", Matemáticas Discretas , 157 ( 1–3 ): 363–374 , doi : 10.1016/S0012-365X(96)83023-8 , MR 1417303 .

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 permutaciones con relativamente pocos elementos base.