Marko Petkovšek: Preštevanje permutacij, ki ne vsebujejo prepovedanih vzorcev

Povzetek. Permutacija p dolžine n vsebuje permutacijo q dolžine m, če obstajajo indeksi i_1 < i_2 < ... < i_m, tako da za vse j < k velja:

          p(i_j) < p(i_k) <===> q(j) < q(k).

V zadnjih 25 letih se je zelo razvilo raziskovanje lastnosti in števila permutacij dolžine n, ki ne vsebujejo izbrane permutacije q, oziroma splošneje - lastnosti in števila permutacij dožine n, ki za i = 1, 2, ..., v vsebujejo natanko a_i nastopov permutacije q_i. Kljub temu je ostalo na tem področju še mnogo odprtih vprašanj. Na seminarju si bomo ogledali nekaj znanih rezultatov in nekaj odprtih problemov o številu s_n(q) vseh permutacij dolžine n, ki ne vsebujejo permutacije q, kakor tudi Klazar-Marcus-Tardosev dokaz domneve Stanleya in Wilfa, da za vsako permutacijo q obstaja konstanta c, tako da je s_n(q) <= c^n za vse n.