Preštevanje permutacij, ki ne vsebujejo prepovedanih vzorcev (Seminar DM)

Iz MaFiRaWiki

Preštevanje permutacij, ki ne vsebujejo prepovedanih vzorcev

Marko Petkovšek


Torek, 19. april 2011, od 10-12, Plemljev seminar, Jadranska 19


Povzetek:

Permutacija p dolžine n vsebuje permutacijo q dolžine m, če obstajajo indeksi i1 < i2 < ... < im, tako da za vse j < k velja:

         p(i_j) < p(i_k) \Longleftrightarrow 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 ai nastopov permutacije qi. 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 sn(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) \le c^n za vse n.


Glej tudi/See also


Seminar za diskretno matematiko

Osebna orodja