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 básicos. 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.
Clases evitando un patrón de longitud 3
Hay dos clases de simetría y una única clase de Wilf para permutaciones simples de longitud tres.
β | secuencia que enumera Av n (β) | OEIS | tipo de secuencia | referencia de enumeración exacta |
---|---|---|---|---|
123 | 1, 2, 5, 14, 42, 132, 429, 1430, ... | A000108 | algebraicos (no racionales) gf números catalanes | MacMahon (1916) Knuth (1968) |
Clases evitando un patrón de longitud 4
Hay siete clases de simetría y tres clases de Wilf para permutaciones simples de longitud cuatro.
β | secuencia que enumera Av n (β) | OEIS | tipo de secuencia | referencia de enumeración exacta |
---|---|---|---|---|
1342 | 1, 2, 6, 23, 103, 512, 2740, 15485, ... | A022558 | gf algebraico (no racional) | Bóna (1997) |
1234 | 1, 2, 6, 23, 103, 513, 2761, 15767, ... | A005802 | gf holonómico (no algebraico) | Gessel (1990) |
1324 | 1, 2, 6, 23, 103, 513, 2762, 15793, ... | A061552 |
No se conoce ninguna fórmula no recursiva que cuente 1324 que eviten las permutaciones. Marinov y Radoičić (2003) dieron una fórmula recursiva . Johansson y Nakamura (2014) proporcionaron 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 y col. (2017) han proporcionado límites inferior y superior para el crecimiento de esta clase.
Clases evitando 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) .
B | secuencia que enumera Av n (B) | OEIS | tipo de secuencia |
---|---|---|---|
123, 321 | 1, 2, 4, 4, 0, 0, 0, 0, ... | n / A | finito |
213, 321 | 1, 2, 4, 7, 11, 16, 22, 29, ... | A000124 | polinomio, |
1, 2, 4, 8, 16, 32, 64, 128, ... | A000079 | novia racional , |
Clases evitando un patrón de longitud 3 y uno de longitud 4
Hay dieciocho clases de simetría y nueve clases de Wilf, todas las cuales se han enumerado. Para conocer estos resultados, consulte Atkinson (1999) o West (1996) .
B | secuencia que enumera Av n (B) | OEIS | tipo de secuencia |
---|---|---|---|
321, 1234 | 1, 2, 5, 13, 25, 25, 0, 0, ... | n / A | finito |
321, 2134 | 1, 2, 5, 13, 30, 61, 112, 190, ... | A116699 | polinomio |
132, 4321 | 1, 2, 5, 13, 31, 66, 127, 225, ... | A116701 | polinomio |
321, 1324 | 1, 2, 5, 13, 32, 72, 148, 281, ... | A179257 | polinomio |
321, 1342 | 1, 2, 5, 13, 32, 74, 163, 347, ... | A116702 | novia racional |
321, 2143 | 1, 2, 5, 13, 33, 80, 185, 411, ... | A088921 | novia racional |
132, 4312 | 1, 2, 5, 13, 33, 81, 193, 449, ... | A005183 | novia racional |
132, 3214 | 1, 2, 5, 13, 33, 82, 202, 497, ... | A116703 | novia racional |
321, 2341321 | 1, 2, 5, 13, 34, 89, 233, 610, ... | A001519 | gf racional , números de Fibonacci alternativos |
Clases evitando dos patrones de longitud 4
Hay 56 clases de simetría y 38 clases de equivalencia de Wilf. Sólo 3 de estos permanecen sin enumerar, y sus funciones generadoras se conjeturan que no satisfacen ninguna ecuación diferencial algebraica (ADE) por Albert et al. (2018) ; en particular, su conjetura implicaría que estas funciones generadoras no son D-finitas .
B | secuencia que enumera Av n (B) | OEIS | tipo de secuencia | referencia de enumeración exacta | la codificación de inserción es regular |
---|---|---|---|---|---|
4321, 1234 | 1, 2, 6, 22, 86, 306, 882, 1764, ... | A206736 | finito | Teorema de Erdős-Szekeres | ✔ |
4312, 1234 | 1, 2, 6, 22, 86, 321, 1085, 3266, ... | A116705 | polinomio | Kremer y Shiu (2003) | ✔ |
4321, 3124 | 1, 2, 6, 22, 86, 330, 1198, 4087, ... | A116708 | novia racional | Kremer y Shiu (2003) | ✔ |
4312, 2134 | 1, 2, 6, 22, 86, 330, 1206, 4174, ... | A116706 | novia racional | Kremer y Shiu (2003) | ✔ |
4321, 1324 | 1, 2, 6, 22, 86, 332, 1217, 4140, ... | A165524 | polinomio | Vatter (2012) | ✔ |
4321, 2143 | 1, 2, 6, 22, 86, 333, 1235, 4339, ... | A165525 | novia racional | Albert, Atkinson y Brignall (2012) | |
4312, 1324 | 1, 2, 6, 22, 86, 335, 1266, 4598, ... | A165526 | novia racional | Albert, Atkinson y Brignall (2012) | |
4231, 2143 | 1, 2, 6, 22, 86, 335, 1271, 4680, ... | A165527 | novia racional | Albert, Atkinson y Brignall (2011) | |
4231, 1324 | 1, 2, 6, 22, 86, 336, 1282, 4758, ... | A165528 | novia racional | Albert, Atkinson y Vatter (2009) | |
4213, 2341 | 1, 2, 6, 22, 86, 336, 1290, 4870, ... | A116709 | novia racional | Kremer y Shiu (2003) | ✔ |
4312, 2143 | 1, 2, 6, 22, 86, 337, 1295, 4854, ... | A165529 | novia racional | Albert, Atkinson y Brignall (2012) | |
4213, 1243 | 1, 2, 6, 22, 86, 337, 1299, 4910, ... | A116710 | novia racional | Kremer y Shiu (2003) | ✔ |
4321, 3142 | 1, 2, 6, 22, 86, 338, 1314, 5046, ... | A165530 | novia racional | Vatter (2012) | ✔ |
4213, 1342 | 1, 2, 6, 22, 86, 338, 1318, 5106, ... | A116707 | novia racional | Kremer y Shiu (2003) | ✔ |
4312, 2341 | 1, 2, 6, 22, 86, 338, 1318, 5110, ... | A116704 | novia racional | Kremer y Shiu (2003) | ✔ |
3412, 2143 | 1, 2, 6, 22, 86, 340, 1340, 5254, ... | A029759 | gf algebraico (no racional) | Atkinson (1998) | |
4321, 4123 | 1, 2, 6, 22, 86, 342, 1366, 5462, ... | A047849 | novia racional | Kremer y Shiu (2003) | Cierto para los primeros tres |
4123, 2341 | 1, 2, 6, 22, 87, 348, 1374, 5335, ... | A165531 | gf algebraico (no racional) | Atkinson, Sagan y Vatter (2012) | |
4231, 3214 | 1, 2, 6, 22, 87, 352, 1428, 5768, ... | A165532 | gf algebraico (no racional) | Minero (2016) | |
4213, 1432 | 1, 2, 6, 22, 87, 352, 1434, 5861, ... | A165533 | gf algebraico (no racional) | Minero (2016) | |
4312, 3421 | 1, 2, 6, 22, 87, 354, 1459, 6056, ... | A164651 | gf algebraico (no racional) | Le (2005) estableció la equivalencia de Wilf; Callan (2013a) determinó la enumeración. | |
4312, 3124 | 1, 2, 6, 22, 88, 363, 1507, 6241, ... | A165534 | gf algebraico (no racional) | Pantone (2017) | |
4231, 3124 | 1, 2, 6, 22, 88, 363, 1508, 6255, ... | A165535 | gf algebraico (no racional) | Albert, Atkinson y Vatter (2014) | |
4312, 3214 | 1, 2, 6, 22, 88, 365, 1540, 6568, ... | A165536 | gf algebraico (no racional) | Minero (2016) | |
4231, 3412 | 1, 2, 6, 22, 88, 366, 1552, 6652, ... | A032351 | gf algebraico (no racional) | Bóna (1998) | |
4213, 2143 | 1, 2, 6, 22, 88, 366, 1556, 6720, ... | A165537 | gf algebraico (no racional) | Bevan (2016b) | |
4312, 3142 | 1, 2, 6, 22, 88, 367, 1568, 6810, ... | A165538 | gf algebraico (no racional) | Albert, Atkinson y Vatter (2014) | |
4213, 3421 | 1, 2, 6, 22, 88, 367, 1571, 6861, ... | A165539 | gf algebraico (no racional) | Bevan (2016a) | |
4213, 3412 | 1, 2, 6, 22, 88, 368, 1584, 6968, ... | A109033 | gf algebraico (no racional) | Le (2005) | |
4321, 3214 | 1, 2, 6, 22, 89, 376, 1611, 6901, ... | A165540 | gf algebraico (no racional) | Bevan (2016a) | |
4213, 3142 | 1, 2, 6, 22, 89, 379, 1664, 7460, ... | A165541 | gf algebraico (no racional) | Albert, Atkinson y Vatter (2014) | |
4231, 4123 | 1, 2, 6, 22, 89, 380, 1677, 7566, ... | A165542 | conjeturado que no satisface ningún ADE , ver Albert et al. (2018) | ||
4321, 4213 | 1, 2, 6, 22, 89, 380, 1678, 7584, ... | A165543 | gf algebraico (no racional) | Callan (2013b) ; véase también Bloom y Vatter (2016) | |
4123, 3412 | 1, 2, 6, 22, 89, 381, 1696, 7781, ... | A165544 | gf algebraico (no racional) | Minero y Pantone (2018) | |
4312, 4123 | 1, 2, 6, 22, 89, 382, 1711, 7922, ... | A165545 | conjeturado que no satisface ningún ADE , ver Albert et al. (2018) | ||
4321, 4312 | 1, 2, 6, 22, 90, 394, 1806, 8558, ... | A006318 | Números de Schröder algebraicos (no racionales) gf | Kremer (2000) , Kremer (2003) | |
3412, 2413 | 1, 2, 6, 22, 90, 395, 1823, 8741, ... | A165546 | gf algebraico (no racional) | Minero y Pantone (2018) | |
4321, 4231 | 1, 2, 6, 22, 90, 396, 1837, 8864, ... | A053617 | conjeturado que no satisface ningún ADE , ver Albert et al. (2018) |
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 básicos.
Ver también
- Permutación de Baxter
- Permutación de riffle shuffle
Referencias
- Albert, Michael H .; Anciano, Murray; Rechnitzer, Andrew; Westcott, P .; Zabrocki, Mike (2006), "En 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 , MR 2199982.
- Albert, Michael H .; Atkinson, MD; Brignall, Robert (2011), "La enumeración de permutaciones que evitan 2143 y 4231" (PDF) , Pure Mathematics and Applications , 22 : 87–98, MR 2924740.
- Albert, Michael H .; Atkinson, MD; Brignall, Robert (2012), "La enumeración de tres clases de patrones usando clases de cuadrícula monótona" , Electronic Journal of Combinatorics , 19 (3): Paper 20, 34 pp, doi : 10.37236 / 2442 , MR 2967225.
- Albert, Michael H .; Atkinson, MD; Vatter, Vincent (2009), "Contando 1324, 4231-evitando permutaciones" , Electronic Journal of Combinatorics , 16 (1): Paper 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ícula geométrica: 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 decreciente" , Electronic Journal of Combinatorics , 5 : Paper 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), "Counting (3 + 1) -avoiding permutations", 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 Ł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 e informática teórica , 18 (2): 14 págs..
- Bevan, David ; Brignall, Robert; Elvey Price, Andrew; Pantone, Jay (2017), Una caracterización estructural de Av (1324) y nuevos límites en su tasa de crecimiento , arXiv : 1711.10325 , Bibcode : 2017arXiv171110325B.
- Bloom, Jonathan; Vatter, Vincent (2016), "Dos viñetas sobre ubicaciones 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 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 , MR 1485138.
- Bóna, Miklós (1998), "Las clases de permutación equinumerables a la clase suave" , Revista Electrónica de Combinatoria , 5 : Documento 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 1243, 2134-evitando , arXiv : 1303.3857 , Bibcode : 2013arXiv1303.3857C.
- Callan, David (2013b), Las permutaciones que evitan 4321 y 3241 tienen una función generadora algebraica , arXiv : 1306.3193 , Bibcode : 2013arXiv1306.3193C.
- Conway, Andrew; Guttmann, Anthony (2015), "Sobre 1324-evitar permutaciones", Avances en matemáticas aplicadas , 64 : 50–69, doi : 10.1016 / j.aam.2014.12.004 , MR 3300327.
- Conway, Andrew; Guttmann, Anthony; Zinn-Justin, Paul (2018), "1324-evitando permutaciones revisitadas", 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 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), "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 , Señor 1997910.
- Kremer, Darla; Shiu, Wai Chee (2003), "Matrices de transición finitas para permutaciones que evitan pares de patrones de cuatro longitudes", Matemáticas discretas , 268 (1-3): 171-183, doi : 10.1016 / S0012-365X (03) 00042-6 , Señor 1983276.
- Le, Ian (2005), "Clases Wilf de pares de permutaciones de longitud 4" , Electronic Journal of Combinatorics , 12 : Paper 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 pp, doi : 10.37236 / 1685 , MR 2028282.
- Miner, Sam (2016), Enumeración de varias clases de dos por cuatro , arXiv : 1610.01908 , Bibcode : 2016arXiv161001908M.
- Minero, 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", Matemáticas discretas , 157 (1-3): 363-374, doi : 10.1016 / S0012-365X (96) 83023-8 , MR 1417303.