20.500.12556/RUL-172552 Izogibanje vzorcem v permutacijah Pattern avoidance in permutations V teoriji permutacijskih vzorcev se preučuje vpliv prisotnosti in odsotnosti urejenih podzaporedij na strukturne lastnosti permutacij. V nalogi so predstavljene osnove teorije od temeljnih definicij do sodobnih rezultatov. Za vzorce dolžine 3 se dokaže, da vsi tvorijo en sam Wilfov razred, ki ga preštevajo Catalanova števila. Poseben poudarek je na vzorcih dolžine 4, pri čemer se obravnavajo klasifikacija Wilfovih razredov, odprt problem vzorca 1324 in Bónov dokaz zgornje meje. Na koncu je predstavljen Stanley-Wilfov izrek, ki pokaže, da število izogibajočih permutacij narašča kvečjemu eksponentno. Cilj naloge je predstavitev ključnih konceptov in rezultatov ter prikaz pomena tega področja v sodobni kombinatoriki. In the theory of permutation patterns, the influence of the presence and absence of ordered subsequences on the structural properties of permutations is studied. In the thesis, the foundations of the theory are presented from fundamental definitions to contemporary results. For patterns of length 3, it is proved that they all form a single Wilf class, which is enumerated by the Catalan numbers. Special emphasis is placed on patterns of length 4, wherein the classification of Wilf classes, the open problem of the pattern 1324, and Bóna’s proof of an upper bound are treated. Finally, the Stanley–Wilf theorem is presented, which shows that the number of avoiding permutations grows at most exponentially. The aim of the thesis is to present the key concepts and results and to demonstrate the significance of this area in contemporary combinatorics. permutacije vzorci v permutacijah izogibanje vzorcem Stanley-Wilfova domneva Marcus-Tardosov dokaz permutations permutation patterns pattern avoidance Stanley-Wilf conjecture Marcus-Tardos proof true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2025-09-08 14:10:01 2025-09-08 14:10:05 2025-09-15 08:34:54 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 38093 248874499 Jelenko_iglic_Luka_-_Izogibanje_vzorcem_v_permutacijah.pdf Jelenko_iglic_Luka_-_Izogibanje_vzorcem_v_permutacijah.pdf 1 8EED313CD40938A865D964525B0A487D 8d755c4ad004a49bedd67e968eafeb67e7bba3a9d569f0155e9ca909efeb6473 9b9610af-8cac-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=216389 Fakulteta za računalništvo in informatiko 0 0 0