Wzór permutacji

W matematyce kombinatorycznej i informatyce teoretycznej wzór permutacji jest podpermutacją dłuższej permutacji . Dowolna permutacja może być zapisana w notacji jednowierszowej jako ciąg cyfr reprezentujący wynik zastosowania permutacji do ciągu cyfr 123...; na przykład sekwencja cyfr 213 reprezentuje permutację na trzech elementach, która zamienia elementy 1 i 2. Jeśli π i σ są dwiema permutacjami przedstawionymi w ten sposób (te nazwy zmiennych są standardowe dla permutacji i nie mają związku z liczbą pi ), to mówi się, że π zawiera σ jako wzorzec , jeśli jakiś podsekwencja cyfr π ma ten sam porządek względny, co wszystkie cyfry σ.

Na przykład permutacja π zawiera wzorzec 213, ilekroć π ma trzy cyfry x , y i z , które pojawiają się w obrębie π w kolejności x ... y ... z , ale których wartości są uporządkowane jako y < x < z , tak samo jak uporządkowanie wartości w permutacji 213. Permutacja 32415 na pięciu elementach zawiera 213 jako wzorzec na kilka różnych sposobów: 3··15, ··415, 3 2··5, 324·· i ·2·15 wszystkie tworzą trójki cyfr o takiej samej kolejności jak 213. Każdy z podciągów 315, 415, 325, 324 i 215 jest nazywany kopia, instancja lub wystąpienie wzorca. Fakt, że π zawiera σ, jest zapisywany bardziej zwięźle jako σ ≤ π. Jeśli permutacja π nie zawiera wzorca σ, to mówi się, że π unika σ. Permutacja 51342 omija 213; ma 10 podsekwencji po trzy cyfry, ale żaden z tych 10 podsekwencji nie ma takiej samej kolejności jak 213.

Wczesne wyniki

Można stwierdzić, że Percy MacMahon ( 1915 ) był pierwszym, który udowodnił wynik w tej dziedzinie, badając „permutacje kratowe”. W szczególności MacMahon pokazuje, że permutacje, które można podzielić na dwa malejące podciągi (tj. permutacje unikające 123) są liczone liczbami katalońskimi .

Innym wczesnym przełomowym wynikiem w tej dziedzinie jest twierdzenie Erdősa – Szekeresa ; w języku wzorców permutacji twierdzenie stwierdza, że dla dowolnych dodatnich liczb całkowitych aib każda permutacja o długości co najmniej ( $b-1) + 1}$ musi zawierać wzór ${\ Displaystyle 1,2,3, \ kropki, a}$ lub wzór ${\ Displaystyle b, b-1, \ kropki, 2,1}$ .

Początki informatyki

Badanie wzorców permutacji rozpoczęło się na poważnie wraz z rozważeniem sortowania stosów przez Donalda Knutha w 1968 r. Knuth wykazał, że permutację π można posortować według stosu wtedy i tylko wtedy, gdy π unika 231, a permutacje możliwe do sortowania w stosach są wyliczane przez liczby katalońskie . Knuth zadał również pytania dotyczące sortowania za pomocą deques . W szczególności otwarte pozostaje pytanie Knutha, ile permutacji n elementów można uzyskać za pomocą deque. Wkrótce potem Robert Tarjan ( 1972 ) badali sortowanie według sieci stosów, podczas gdy Vaughan Pratt ( 1973 ) wykazał, że permutację π można posortować według deque wtedy i tylko wtedy, gdy dla wszystkich k π unika 5,2,7,4,...,4 k +1,4 k −2,3,4 k ,1 i 5,2,7,4,...,4 k +3,4 k ,1,4 k +2,3 i każdą permutację, którą można uzyskać z któregokolwiek z nich, zamieniając ostatnie dwa elementy lub 1 i 2. Ponieważ ten zbiór permutacji jest nieskończony (w rzeczywistości jest to pierwszy opublikowany przykład nieskończonego antyłańcucha permutacji), nie jest od razu jasne, ile czasu zajmuje podjęcie decyzji, czy permutację można posortować według deque . Rosenstiehl i Tarjan (1984) przedstawili później liniowy (o długości π) algorytm czasu, który określa, czy π można posortować według deque.

W swoim artykule Pratt zauważył, że ten porządek wzorców permutacji „wydaje się być jedynym częściowym porządkiem permutacji, który powstaje w prosty i naturalny sposób” i konkluduje, zauważając, że „z abstrakcyjnego punktu widzenia” porządek wzorców permutacji „jest jeszcze bardziej interesujący niż sieci, które charakteryzowaliśmy”.

Pochodzenie wyliczeniowe

Ważnym celem w badaniu wzorców permutacji jest wyliczanie permutacji, unikając stałej (i zazwyczaj krótkiej) permutacji lub zestawu permutacji. Niech Av _n (B) oznacza zbiór permutacji o długości n , które unikają wszystkich permutacji w zbiorze B (w przypadku, gdy B jest singletonem, powiedzmy β , zamiast tego używany jest skrót Av _n ( β )). Jak wspomniano powyżej, MacMahon i Knuth wykazali, że | Avn ₍ 123)| = | Avn ₍ 231)| = C _n , n - ta liczba katalońska. Zatem są to izomorficzne klasy kombinatoryczne .

Simion i Schmidt (1985) byli pierwszym artykułem skupiającym się wyłącznie na wyliczaniu. Wśród innych wyników Simion i Schmidt policzyli parzyste i nieparzyste permutacje unikając wzorca o długości trzy, policzyli permutacje unikając dwóch wzorców o długości trzy i podali pierwszy bijektywny dowód, że permutacje unikające 123 i 231 są równoliczne. Od czasu ich artykułu podano wiele innych bijekcji, patrz przegląd Claesson i Kitaev (2008) .

Ogólnie rzecz biorąc, jeśli | Av _n ( β )| = | Av _n ( σ )| dla wszystkich n , to mówi się, że β i σ są równoważne Wilfowi . Wiele odpowiedników Wilfa wynika z trywialnego faktu, że | Av _n ( β )| = | Av _n ( β ⁻¹ )| = | Av _n ( β ^obr )| dla wszystkich n , gdzie β ⁻¹ oznacza odwrotność β i β ^rev oznacza odwrotność β . (Te dwie operacje generują grupę dwuścienną D ₈ z naturalnym działaniem na macierze permutacji ). Istnieje jednak również wiele przykładów nietrywialnych równoważności Wilfa (takich jak między 123 a 231 ):

Stankova (1994) udowodnił, że permutacje 1342 i 2413 są równoważne Wilfowi.
Stankova i West (2002) udowodnili, że dla dowolnej permutacji β permutacje 231 ⊕ β i 312 ⊕ β są równoważne Wilfa, gdzie ⊕ oznacza operację sumy bezpośredniej .
Backelin, West & Xin (2007) udowodnili, że dla dowolnej permutacji β i dowolnej dodatniej liczby całkowitej m permutacje 12.. m ⊕ β i m ...21 ⊕ β są równoważne Wilfowi.

Z tych dwóch równoważności Wilfa oraz odwrotnej i odwrotnej symetrii wynika, że istnieją trzy różne sekwencje | Av _n ( β )| gdzie β ma długość cztery:

β	sekwencja wyliczająca Av _n ( β )	Odniesienie do OEIS	dokładne odniesienie do wyliczenia
1342	1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, ...	A022558	Bona (1997)
1234	1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, ...	A005802	Gessel (1990)
1324	1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, ...	A061552	niewymienione

Pod koniec lat 80. Richard Stanley i Herbert Wilf przypuszczali, że dla każdej permutacji β istnieje pewna stała K taka, że | Av _n ( β )| < K ⁿ . Było to znane jako hipoteza Stanleya-Wilfa, dopóki nie zostało udowodnione przez Adama Marcusa i Gábora Tardosa .

Zajęcia zamknięte

Klasa zamknięta , znana również jako klasa wzorców , klasa permutacji lub po prostu klasa permutacji, jest zaburzeniem kolejności wzorców permutacji. Każda klasa może być zdefiniowana przez minimalne permutacje, które nie leżą wewnątrz niej, jej podstawy . Zatem podstawą dla permutacji z możliwością sortowania w stosie jest {231}, podczas gdy podstawa dla permutacji z możliwością sortowania deque jest nieskończona. Funkcją generującą dla klasy jest Σ x ^|π| gdzie suma jest przejmowana przez wszystkie permutacje π w klasie.

Funkcja Möbiusa

Ponieważ zbiór permutacji w ramach nakazu powstrzymywania tworzy poset, naturalne jest pytanie o jego funkcję Möbiusa , cel po raz pierwszy wyraźnie przedstawiony przez Wilfa (2002) . Celem takich badań jest znalezienie wzoru na funkcję Möbiusa przedziału [σ, π] we wzorcu permutacji poseset, który jest bardziej wydajny niż naiwna definicja rekurencyjna. Pierwszy taki wynik został ustalony przez Sagana i Vattera (2006) , którzy podali wzór na funkcję Möbiusa przedziału permutacji warstwowych . Później Burstein i in. (2011) uogólnił ten wynik na przedziały rozdzielnych permutacji .

Wiadomo, że asymptotycznie co najmniej 39,95% wszystkich permutacji π o długości n spełnia μ(1, π)=0 (czyli główna funkcja Möbiusa jest równa zeru), ale dla każdego n istnieją permutacje π takie, że μ(1, π) jest funkcją wykładniczą n .

Złożoność obliczeniowa

pod uwagę permutację (zwaną $tekstem$ $)$ o długości $\ displaystyle \ tau}$ permutację $)$ $,$ ( wzorem problem dopasowania wzorca permutacji (PPM) pyta , czy jest zawarty w ${$ . Kiedy zarówno ${\ displaystyle n},$ jak i ${\ displaystyle k}$ są traktowane jako zmienne, problem jest znany jako NP-zupełny , a problem zliczania liczby takich dopasowań to #P-zupełny . Jednak PPM można rozwiązać w czasie liniowym, gdy k jest stałą. Rzeczywiście, Guillemot i Marx $PPM$ można rozwiązać w czasie , rozwiązać ustalonymi w odniesieniu do ${\ displaystyle k}$ .

Istnieje kilka wariantów problemu PPM, zgodnie z badaniem przeprowadzonym przez Brunera i Lacknera. Na przykład, jeśli dopasowanie ma składać się z ciągłych wpisów, problem można rozwiązać w czasie wielomianowym.

$, jak i$ $są$ ograniczone do odpowiedniej klasy permutacji , w którym to przypadku problem nazywa się -PPM. $_$ $,$ że można _ Alberta $skośnie$ Lackner i Vatter obniżyli później to do ta sama granica obowiązuje dla klasy permutacji połączonych Następnie zapytali, czy $\ displaystyle {\ mathcal {C}}}$ ${$ można rozwiązać w czasie wielomianowym dla każdej ustalonej właściwej klasy permutacji do .

Gęstości upakowania

Mówimy, że permutacja π jest β- optymalna , jeśli żadna permutacja o tej samej długości co π nie ma większej liczby kopii β. W swoim przemówieniu na spotkaniu SIAM dotyczącym matematyki dyskretnej w 1992 r. Wilf zdefiniował gęstość upakowania permutacji β o długości k jako

{\ Displaystyle \ lim _ {n \ rightarrow \ infty} {\ Frac {{\ tekst {liczba kopii}} \ beta {\ tekst {w a}} \ beta {\ tekst {-optymalna permutacja długości}} n} {\ Displaystyle {n \ wybierz k}}}.}

Nieopublikowany argument Freda Galvina pokazuje, że wielkość wewnątrz tej granicy nie rośnie dla n ≥ k , a więc granica istnieje. Gdy β jest monotoniczne, jego gęstość upakowania wynosi wyraźnie 1, a gęstości upakowania są niezmienne w grupie symetrii generowanych przez odwrotność i odwrotność, więc dla permutacji o długości trzech istnieje tylko jedna nietrywialna gęstość upakowania. Walter Stromquist (nieopublikowany) rozstrzygnął ten przypadek, pokazując, że gęstość upakowania 132 wynosi 2 √ 3 - 3, w przybliżeniu 0,46410.

W przypadku permutacji β o długości cztery istnieje (ze względu na symetrie) siedem przypadków do rozważenia:

β	gęstość upakowania	odniesienie
1234	1	trywialny
1432	pierwiastek z x ³ - 12 x ² + 156 x - 64 ≅ 0,42357	Cena (1997)
2143	⅜ = 0,375	Cena (1997)
1243	⅜ = 0,375	Alberta i in. (2002)
1324	przypuszczalnie ≅ 0,244
1342	przypuszczalnie ≅ 0,19658
2413	przypuszczalnie ≅ 0,10474

Dla trzech nieznanych permutacji istnieją granice i przypuszczenia. Price (1997) zastosował algorytm przybliżenia, który sugeruje, że gęstość upakowania 1324 wynosi około 0,244. Birzhan Batkeyev (nieopublikowany) skonstruował rodzinę permutacji pokazującą, że gęstość upakowania 1342 jest co najmniej iloczynem gęstości upakowania 132 i 1432, w przybliżeniu 0,19658. Przypuszcza się, że jest to dokładna gęstość upakowania wynosząca 1342. Presutti i Stromquist (2010) podali dolną granicę gęstości upakowania wynoszącą 2413. Ta dolna granica, którą można wyrazić jako całkę, wynosi około 0,10474 i przypuszcza się, że jest to rzeczywista gęstość upakowania.

superwzory

K - superwzorzec to permutacja zawierająca wszystkie permutacje o długości k . Na przykład 25314 jest 3-superwzorem, ponieważ zawiera wszystkie 6 permutacji o długości 3. Wiadomo, że k -superwzorce muszą mieć długość co najmniej k ² / e ² , gdzie e ≈ 2,71828 to liczba Eulera , i że istnieje k -superwzorce o długości ⌈( k ² + 1)/2⌉. Przypuszcza się, że ta górna granica jest najlepsza z możliwych, aż do warunków niższego rzędu.

Uogólnienia

Istnieje kilka sposobów uogólnienia pojęcia „wzorca”. Na przykład wzór winkularny to permutacja zawierająca kreski wskazujące wpisy, które nie muszą występować kolejno (w definicji normalnego wzorca żadne wpisy nie muszą występować kolejno). Na przykład permutacja 314265 ma dwie kopie przerywanego wzoru 2-31-4, podanego przez wpisy 3426 i 3425. Dla przerywanego wzoru β i dowolnej permutacji π piszemy β(π) dla liczby kopii β w π. Zatem liczba inwersji w π wynosi 2-1(π), podczas gdy liczba spadków wynosi 21(π). Idąc dalej liczba dolin w π wynosi 213 (π) + 312 (π), podczas gdy liczba pików wynosi 231 (π) + 132 (π). Wzorce te zostały wprowadzone przez Babsona i Steingrímssona (2000) , którzy wykazali, że prawie wszystkie znane statystyki mahońskie można wyrazić za pomocą permutacji winorośli. Na przykład główny indeks π jest równy 1-32(π) + 2-31(π) + 3-21(π) + 21(π).

Innym uogólnieniem jest wzór z kreskami , w którym niektóre wpisy są przekreślone. Dla π uniknięcie wzorca z kreskami β oznacza, że każdy zestaw wpisów π, które tworzą kopię wpisów bez kresek z β, można rozszerzyć, tworząc kopię wszystkich wpisów z β. West (1993) wprowadził tego typu wzorce w swoich badaniach nad permutacjami, które można było sortować, przepuszczając je dwukrotnie przez stos. (Zauważ, że definicja Westa dotycząca dwukrotnego sortowania stosu nie jest tym samym, co sortowanie z dwoma stosami w szeregu.) Inny przykład wzorców z kreskami występuje w pracy Bousquet-Mélou i Butler (2007) , który wykazał, że rozmaitość Schuberta odpowiadająca π jest lokalnie silnią wtedy i tylko wtedy, gdy π unika 1324 i 21 3 54.

Linki zewnętrzne

Konferencja na temat wzorców permutacji odbywa się corocznie od 2003 roku :

Permutation Patterns 2003 , 10–14 lutego 2003, University of Otago , Dunedin, Nowa Zelandia.
Permutation Patterns 2004 , 5–9 lipca 2004, Malaspina University-College , Nanaimo, Kolumbia Brytyjska, Kanada.
Permutation Patterns 2005 , 7–11 marca 2005, University of Florida , Gainesville, Floryda, USA.
Permutation Patterns 2006 , 12-16 czerwca 2006, Uniwersytet w Reykjavíku , Reykjavík, Islandia.
Permutation Patterns 2007 , 11–15 czerwca 2007, University of St. Andrews , St. Andrews, Szkocja.
Permutation Patterns 2008 , 16–20 czerwca 2008, University of Otago , Dunedin, Nowa Zelandia.
Permutation Patterns 2009 , 13–17 lipca 2009, Università di Firenze , Florencja, Włochy.
Permutation Patterns 2010 , 9–13 sierpnia 2010, Dartmouth College , Hanower, New Hampshire, USA.
Permutation Patterns 2011 , 20–24 czerwca 2011, California Polytechnic State University , San Luis Obispo, Kalifornia, USA.
Permutation Patterns 2012 , 11–15 czerwca 2012, University of Strathclyde , Glasgow, Szkocja.
Permutation Patterns 2013 , 1–5 lipca 2013, Université Paris Diderot , Paryż, Francja.
Permutation Patterns 2014 , 7–11 lipca 2014 r., East Tennessee State University , Johnson City, Tennessee, USA.
Permutation Patterns 2015 , 15–19 czerwca 2015 r., De Morgan House , Londyn, Anglia.
Permutation Patterns 2016 , 27 czerwca – 1 lipca 2016, Howard University , Waszyngton, DC, USA.
Permutation Patterns 2017 , 26–30 czerwca 2017, Uniwersytet w Reykjaviku , Reykjavík, Islandia.
Permutation Patterns 2018 , 9–13 lipca 2018, Dartmouth College , Hanower, New Hampshire, USA.
Permutation Patterns 2019 , 17–21 czerwca 2019, Universität Zürich , Zurych, Szwajcaria.
Wirtualne warsztaty Permutation Patterns 2020 , 30 czerwca – 1 lipca 2020 r., organizowane przez Uniwersytet Valparaiso , Valparaiso, Indiana, USA.
Wirtualne warsztaty Permutation Patterns 2021 , 15–16 czerwca 2021 r., zorganizowane przez University of Strathclyde , Glasgow, Szkocja.
Permutation Patterns 2022 , 20-24 czerwca 2022, Valparaiso University , Valparaiso, Indiana, USA.
Permutation Patterns 2023 , 3-7 lipca 2023, Uniwersytet Burgundii , Dijon, Francja.

Amerykańskiego Towarzystwa Matematycznego dotyczące wzorców w permutacjach odbyły się na następujących spotkaniach:

Jesienne spotkanie sekcji wschodniej , 22–23 września 2012 r., Rochester Institute of Technology , Rochester, NY.
Wspólne spotkania matematyczne , 12 stycznia 2013 r., San Diego, Kalifornia.
Centralne jesienne spotkanie sekcji , 20–21 września 2014 r., Uniwersytet Wisconsin-Eau Claire , Eau Claire, WI.
Wiosenne posiedzenie Sekcji Wschodniej , 7–8 marca 2015 r., Uniwersytet Georgetown , Waszyngton, DC.

Inne spotkania wzorców permutacji:

Warsztaty dotyczące wzorców permutacji , 29 maja – 3 czerwca 2005 r., Uniwersytet w Hajfie , Hajfa, Izrael.
Unikanie wzorców i sortowanie genomu , 14-19 lutego 2016 r., Schloss Dagstuhl , Wadern, Niemcy.
Genomics, Pattern Uniqueance, and Statistical Mechanics , 4-9 listopada 2018 r., Schloss Dagstuhl , Wadern, Niemcy.
Unikanie wzorców, Statistical Mechanics and Computational Complexity , 19-24 marca 2023 r., Schloss Dagstuhl , Wadern, Niemcy.

Inne linki:

PermLab: oprogramowanie do wzorców permutacji , utrzymywane przez Michaela Alberta .
Baza danych unikania wzorców permutacji , prowadzona przez Bridget Tenner.
PermPAL: The Permutation Pattern Unikanie Library , baza danych algorytmicznie wyprowadzonych twierdzeń o klasach permutacji, prowadzona przez Christiana Beana, Émile Nadeau, Jaya Pantone i Henninga Ulfarssona.