Permutacja warstwowa

W matematyce permutacji permutacja warstwowa to permutacja, która odwraca ciągłe bloki elementów. Równoważnie, jest to bezpośrednia suma malejących permutacji.

Jedną z wcześniejszych prac ustalających znaczenie permutacji warstwowych była Bóna (1999) , w której ustanowiono hipotezę Stanleya-Wilfa dla klas permutacji zakazujących permutacji warstwowej, zanim hipoteza została udowodniona bardziej ogólnie.

Przykład

Na przykład permutacje warstwowe o długości cztery, z odwróconymi blokami oddzielonymi spacjami, to osiem permutacji

1 2 3 4

1 2 43

1 32 4

1 432

21 3 4

21

43 321 4

4321

Charakteryzacja za pomocą zakazanych wzorców

Warstwowe permutacje można również równoważnie opisać jako permutacje, które nie zawierają wzorców permutacji 231 lub 312. Oznacza to, że żadne trzy elementy w permutacji (niezależnie od tego, czy są one następujące po sobie) nie mają takiego samego uporządkowania jak którakolwiek z tych zabronionych trójek.

Wyliczenie

Warstwowa permutacja liczb od do ${$ $\ displaystyle n}$ może być jednoznacznie opisana przez podzbiór liczb od ${\ displaystyle 1}$ do ${\ displaystyle n-1},$ są pierwszy element w odwróconym bloku. (Liczba $elementem w odwróconym bloku, więc jest$ w tym opisie). Ponieważ istnieje ${\ displaystyle 2 ^ {n-1}}$ $} }$ liczb od do $displaystyle n-1}$ ${\$ , istnieją również warstwowe permutacje długości ${\ displaystyle 2 ^ {n-1$ .

Warstwowe permutacje są odpowiednikami Wilfa dla innych klas permutacji, co oznacza, że liczba permutacji każdej długości jest taka sama. Na przykład permutacje Gilbreath są liczone przez tę samą funkcję ${\ Displaystyle 2 ^ {n-1}}$ .

superwzory

Najkrótszy superwzorzec permutacji warstwowych o długości $sobie$ jest permutacją warstwową. $w celu posortowania$ długość to liczba sortująca , liczba porównań potrzebnych do przez wstawianie binarne elementów Dla ${\ Displaystyle n = 1,2,3, \ kropki}$ liczby te są

1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, ... (sekwencja A001855 w OEIS )

i generalnie są one określone wzorem

{\ Displaystyle (n + 1) {\ bigl \ lceil} \ log _ {2} (n+1){\bigr \rceil}-2^{\left\lceil \log _{2}(n+1)\right\rceil}+1.}

Powiązane klasy permutacji

Każda permutacja warstwowa jest inwolucją . Są to dokładnie 231 unikające inwolucje i dokładnie 312 unikające inwolucje.

Warstwowe permutacje są podzbiorem permutacji z możliwością sortowania w stosie , które zabraniają wzorca 231, ale nie wzorca 312 . sumy skośne.