Výčty konkrétních permutačních tříd - Enumerations of specific permutation classes

Ve studii o permutační vzory, zde byl značný zájem o výčet konkrétních permutační třídy, zejména ty, které mají relativně málo základních prvků. Tato oblast studia přinesla neočekávané případy Wilfova ekvivalence, kde dvě zdánlivě nesouvisející permutační třídy mají stejný počet permutací každé délky.

Třídy vyhýbající se jednomu vzoru o délce 3

Existují dvě třídy symetrie a jedna Wilfova třída pro jednotlivé permutace délky tři.

Třídy vyhýbající se jednomu vzoru délky 4

Existuje sedm tříd symetrie a tři třídy Wilf pro jednotlivé permutace délky čtyři.

Žádný nerekurzivní vzorec počítající 1324 vyhýbání se permutacím není znám. Rekurzivní vzorec byl dán Marinov & Radoičić (2003) Efektivnější algoritmus využívající funkční rovnice dal Johansson & Nakamura (2014), který byl vylepšen o Conway & Guttmann (2015), a poté dále vylepšena o Conway, Guttmann & Zinn-Justin (2018) kteří uvádějí prvních 50 podmínek výčtu.Bevan a kol. (2017) poskytly dolní a horní mez pro růst této třídy.

Třídy vyhýbající se dvěma vzorům o délce 3

Existuje pět tříd symetrie a tři třídy Wilf, z nichž všechny byly vyjmenovány Simion & Schmidt (1985).

B	výčet sekvence Avn(B)	OEIS	typ sekvence
123, 321	1, 2, 4, 4, 0, 0, 0, 0, ...	n / a	konečný
213, 321	1, 2, 4, 7, 11, 16, 22, 29, ...	A000124	polynom, ${ displaystyle {n vyberte 2} +1}$
231, 321 132, 312 231, 312	1, 2, 4, 8, 16, 32, 64, 128, ...	A000079	Racionální např., ${ displaystyle 2 ^ {n-1}}$

Třídy se vyhýbají jednomu vzoru o délce 3 a jednom o délce 4

Existuje osmnáct tříd symetrie a devět Wilfových tříd, z nichž všechny byly vyjmenovány. Tyto výsledky viz Atkinson (1999) nebo West (1996).

Třídy vyhýbající se dvěma vzorům o délce 4

Existuje 56 tříd symetrie a 38 Wilf tříd ekvivalence. Pouze 3 z nich zůstávají bez výčtu a jejich generující funkce se domnívají, že žádné nevyhoví algebraická diferenciální rovnice (ADE) uživatelem Albert a kol. (2018); zejména by jejich domněnka znamenala, že tyto generující funkce nejsou D-konečný.

externí odkazy

The Databáze vyhýbání se permutačním vzorům, který udržuje Bridget Tenner, obsahuje podrobnosti o výčtu mnoha dalších tříd permutací s relativně malým počtem základních prvků.

Viz také

• Baxterova permutace
• Riffle shuffle permutace

Reference

• Albert, Michael H.; Starší, Murray; Rechnitzer, Andrew; Westcott, P .; Zabrocki, Mike (2006), „Na hranici Stanley-Wilf 4231 - vyhýbání se permutacím a domněnka Arratie“, Pokroky v aplikované matematice, 36 (2): 96–105, doi:10.1016 / j.aam.2005.05.007, PAN  2199982.
• Albert, Michael H.; Atkinson, M. D .; Brignall, Robert (2011), „Výčet permutací vyhýbajících se 2143 a 4231“ (PDF), Čistá matematika a aplikace, 22: 87–98, PAN  2924740.
• Albert, Michael H.; Atkinson, M. D .; Brignall, Robert (2012), "Výčet tří tříd vzoru pomocí monotónních tříd mřížky", Electronic Journal of Combinatorics, 19 (3): Papír 20, 34 stran, PAN  2967225.
• Albert, Michael H.; Atkinson, M. D .; Vatter, Vincent (2009), „Počítám 1324, 4231 - vyhýbání se permutacím“, Electronic Journal of Combinatorics, 16 (1): Papír 136, 9 stran, PAN  2577304.
• Albert, Michael H.; Atkinson, M. D .; Vatter, Vincent (2014), „Nafouknutí tříd geometrické mřížky: tři případové studie“ (PDF), Australasian Journal of Combinatorics, 58 (1): 27–47, PAN  3211768.
• Albert, Michael H.; Homberger, Cheyne; Pantone, Jay; Shar, Nathaniel; Vatter, Vincent (2018), „Generování permutací s omezenými kontejnery“, Journal of Combinatorial Theory, Series A, 157: 205–232, arXiv:1510.00269, doi:10.1016 / j.jcta.2018.02.006, PAN  3780412.
• Atkinson, M. D. (1998), "Permutace, které jsou spojením rostoucí a klesající posloupnosti", Electronic Journal of Combinatorics, 5: Papír 6, 13 stran, PAN  1490467.
• Atkinson, M. D. (1999), „Omezené permutace“, Diskrétní matematika, 195 (1–3): 27–38, doi:10.1016 / S0012-365X (98) 00162-9, PAN  1663866.
• Atkinson, M. D .; Sagan, Bruce E.; Vatter, Vincent (2012), „Počítání (3 + 1) - vyhýbání se permutacím“, European Journal of Combinatorics, 33: 49–61, doi:10.1016 / j.ejc.2011.06.006, PAN  2854630.
• Bevan, David (2015), „Permutace vyhýbající se 1324 a vzorům v Łukasiewiczových cestách“ J. London Math. Soc., 92 (1): 105–122, arXiv:1406.2890, doi:10.1112 / jlms / jdv020, PAN  3384507.
• Bevan, David (2016a), „Permutační třídy Av (1234 2341) a Av (1243 2314)“ (PDF), Australasian Journal of Combinatorics, 64 (1): 3–20, PAN  3426209.
• Bevan, David (2016b), „Permutační třída Av (4213 2143)“, Diskrétní matematika a teoretická informatika, 18 (2): 14 stran.
• Bevan, David; Brignall, Robert; Elvey Price, Andrew; Pantone, Jay (2017), Strukturální charakterizace Av (1324) a nové hranice její rychlosti růstu, arXiv:1711.10325, Bibcode:2017arXiv171110325B.
• Bloom, Jonathan; Vatter, Vincent (2016), „Dvě dálniční známky na umístění plné věže“ (PDF), Australasian Journal of Combinatorics, 64 (1): 77–87, PAN  3426214.
• Bóna, Miklósi (1997), „Přesný výčet 1342 vyhýbajících se permutací: úzké spojení se značenými stromy a rovinnými mapami“, Journal of Combinatorial Theory, Series A, 80 (2): 257–272, arXiv:matematika / 9702223, doi:10.1006 / jcta.1997.2800, PAN  1485138.
• Bóna, Miklósi (1998), "Třídy permutace rovnocenné hladké třídě", Electronic Journal of Combinatorics, 5: Papír 31, 12 stran, PAN  1626487.
• Bóna, Miklósi (2015), „Nový rekord pro 1324 vyhýbání se permutacím“, European Journal of Mathematics, 1 (1): 198–206, arXiv:1404.4033, doi:10.1007 / s40879-014-0020-6, PAN  3386234.
• Callan, David (2013a), Počet 1243, 2134 - vyhýbání se permutacím, arXiv:1303.3857, Bibcode:2013arXiv1303.3857C.
• Callan, David (2013b), Permutace vyhýbající se 4321 a 3241 mají algebraickou generující funkci, arXiv:1306.3193, Bibcode:2013arXiv1306.3193C.
• Conway, Andrew; Guttmann, Anthony (2015), „On 1324-avoiding permutations“, Pokroky v aplikované matematice, 64: 50–69, doi:10.1016 / j.aam.2014.12.004, PAN  3300327.
• Conway, Andrew; Guttmann, Anthony; Zinn-Justin, Paul (2018), „1324 - Avoiding Permutations Revisited“, Pokroky v aplikované matematice, 96: 312–333, arXiv:1709.01248, doi:10.1016 / j.aam.2018.01.002.
• Gessel, Ira M. (1990), „Symetrické funkce a P-rekurzivita“, Journal of Combinatorial Theory, Series A, 53 (2): 257–285, doi:10.1016 / 0097-3165 (90) 90060-A, PAN  1041448.
• Johansson, Fredrik; Nakamura, Brian (2014), „Použití funkčních rovnic k výčtu 1324 vyhýbání se permutacím“, Pokroky v aplikované matematice, 56: 20–34, arXiv:1309.7117, doi:10.1016 / j.aam.2014.01.006, PAN  3194205.
• Knuth, Donald E. (1968), Umění počítačového programování sv. 1, Boston: Addison-Wesley, ISBN  978-0-201-89683-1, PAN  0286317, OCLC  155842391.
• Kremer, Darla (2000), „Permutace se zakázanými posloupnostmi a zobecněným Schröderovým číslem“, Diskrétní matematika, 218 (1–3): 121–130, doi:10.1016 / S0012-365X (99) 00302-7, PAN  1754331.
• Kremer, Darla (2003), „Postscript:“ Permutace se zakázanými subsekvencemi a zobecněným Schröderovým číslem"", Diskrétní matematika, 270 (1–3): 333–334, doi:10.1016 / S0012-365X (03) 00124-9, PAN  1997910.
• Kremer, Darla; Shiu, Wai Chee (2003), „Matice konečných přechodů pro permutace vyhýbající se dvojicím vzorů délky čtyři“, Diskrétní matematika, 268 (1–3): 171–183, doi:10.1016 / S0012-365X (03) 00042-6, PAN  1983276.
• Le, Ian (2005), "Wilfovy třídy párů permutací délky 4", Electronic Journal of Combinatorics, 12: Papír 25, 27 stran, PAN  2156679.
• MacMahon, Percy A. (1916), Kombinovaná analýza, Londýn: Cambridge University Press, PAN  0141605.
• Marinov, Darko; Radoičić, Radoš (2003), „Počítám 1324 - vyhýbání se obměnám“, Electronic Journal of Combinatorics, 9 (2): Papír 13, 9 stran, PAN  2028282.
• Horník, Sam (2016), Výčet několika tříd dva ku čtyřem, arXiv:1610.01908, Bibcode:2016arXiv161001908M.
• Horník, Sam; Pantone, Jay (2018), Dokončení strukturální analýzy tříd permutace 2x4, arXiv:1802.00483, Bibcode:2018arXiv180200483M.
• Pantone, Jay (2017), „Výčet permutací vyhýbajících se 3124 a 4312“, Annals of Combinatorics, 21 (2): 293–315, arXiv:1309.0832, doi:10.1007 / s00026-017-0352-2.
• Simion, Rodica; Schmidt, Frank W. (1985), „Omezené permutace“, European Journal of Combinatorics, 6 (4): 383–406, doi:10.1016 / s0195-6698 (85) 80052-4, PAN  0829358.
• Vatter, Vincent (2012), „Hledání pravidelných kódování pro třídy permutace“, Journal of Symbolic Computation, 47 (3): 259–265, arXiv:0911.2683, doi:10.1016 / j.jsc.2011.11.002, PAN  2869320.
• West, Julian (1996), „Generování stromů a zakázané sekvence“, Diskrétní matematika, 157 (1–3): 363–374, doi:10.1016 / S0012-365X (96) 83023-8, PAN  1417303.