Permutacja scalona skośnie

W teorii wzorców permutacji permutacja połączona skośnie jest permutacją , którą można podzielić na sekwencję rosnącą i sekwencję malejącą. Zostały one po raz pierwszy zbadane przez Stankovą (1994) i nadane im przez Atkinsona (1998) .

Charakteryzacja

Dwie najmniejsze permutacje, których nie można podzielić na ciąg rosnący i malejący, to 3412 i 2143. Stankova (1994) jako pierwszy ustalił, że permutacja scalona skośnie może być również równoważnie zdefiniowana jako permutacja, która unika dwóch wzorców 3412 i 2143.

Permutacja jest scalona skośnie wtedy i tylko wtedy, gdy powiązany z nią wykres permutacji jest grafem podzielonym , wykresem, który można podzielić na klikę (odpowiadającą malejącej podsekwencji) i niezależny zbiór (odpowiadający rosnącej podsekwencji). Dwa zabronione wzorce dla permutacji połączonych skośnie, 3412 i 2143, odpowiadają dwóm z trzech zabronionych indukowanych podgrafów dla grafów podzielonych odpowiednio cykl czterech wierzchołków i wykres z dwiema rozłącznymi krawędziami. Trzeci zakazany podgraf indukowany, cykl pięciu wierzchołków, nie może istnieć w grafie permutacyjnym (zob. Kézdy, Snevily i Wang (1996) ).

Wyliczenie

Dla ${\ Displaystyle n = 1,2,3, \ kropki}$ liczba permutacji o długości połączonych skośnie wynosi ${\ displaystyle n}$

1, 2, 6, 22, 86, 340, 1340, 5254, 20518, 79932, 311028, 1209916, 4707964, 18330728, ... (sekwencja A029759 w OEIS ) .

Atkinson (1998) jako pierwszy wykazał, że funkcja generująca tych liczb jest

{\ Displaystyle {\ Frac {1-3x} {(1-2x) {\ sqrt {1-4x}}}}}

z czego wynika, że liczba permutacji połączonych skośnie o długości jest dana wzorem ${\ displaystyle n}$

{\ Displaystyle {\ binom {2n} {n}} \ suma _ {m = 0} ^ {n-1} 2 ^{nm-1}{\binom {2m}{m}}}

i że liczby te są zgodne z relacją powtarzalności

{\ Displaystyle P_ {n} = {\ Frac {(9n-8) P_ {n-1} - (26n-46) P_ {n-2} + (24n-60) P_ {n-3}} {n }}.}

Inne wyprowadzenie funkcji generującej dla permutacji skośnych zostało podane przez Alberta i Vattera (2013) .

Złożoność obliczeniowa

Testowanie, czy jedna permutacja jest wzorcem w innej, można skutecznie rozwiązać, gdy większa z dwóch permutacji zostanie scalona skośnie, jak wykazali Albert i in. (2016) .

Albert, Michał ; Vatter, Vincent (2013), „Generowanie i wyliczanie 321-unikających i skośnych prostych permutacji” , Electronic Journal of Combinatorics , 20 (2): Paper 44, 11 s., MR 3084586 .

Albert, Michał ; Lackner, Marie-Louise; Lackner, Martin; Vatter, Vincent (2016), „Złożoność dopasowywania wzorców dla permutacji unikających 321 i połączonych skośnie” , Wzory permutacji 2015, Matematyka dyskretna i informatyka teoretyczna , 18 (2): P11:1–17, arXiv : 1510.06051 , Bibcode : 2015arXiv151006051A , MR 3597961 .

Atkinson, MD (1998), „Permutacje, które są sumą podsekwencji rosnącej i malejącej” , Electronic Journal of Combinatorics , 5 : RP6: 1–13, MR 1490467 . Zobacz także załączony komentarz Volkera Strehla.

Kézdy, André E.; Snevily, Hunter S.; Wang, Chi (1996), „Podział permutacji na rosnące i malejące podsekwencje”, Journal of Combinatorial Theory , Seria A , 73 (2): 353–359, doi : 10.1016 / S0097-3165 (96) 80012-4 , MR 1370138

Sloane, NJA (red.). „Sekwencja A029759” . Encyklopedia on-line sekwencji liczb całkowitych . Fundacja OIS.

Stankova, Zvezdelina E. (1994), „Zakazane podciągi”, Matematyka dyskretna , 132 (1–3): 291–316, doi : 10.1016/0012-365X(94)90242-9 , MR 1297387 . Zobacz w szczególności Twierdzenie 2.9, s. 303–304.