Permutacja Stirlinga
W matematyce kombinatorycznej permutacja Stirlinga rzędu k jest permutacją zbioru wielokrotnego 1, 1, 2, 2, ..., k , k (z dwiema kopiami każdej wartości od 1 do k ) z dodatkową właściwością, że dla każda wartość i pojawiająca się w permutacji, wartości między dwiema kopiami i są większe niż i . Na przykład 15 permutacji Stirlinga trzeciego rzędu to
- 1,1,2,2,3,3; 1,2,2,1,3,3; 2,2,1,1,3,3;
- 1,1,2,3,3,2; 1,2,2,3,3,1; 2,2,1,3,3,1;
- 1,1,3,3,2,2; 1,2,3,3,2,1; 2,2,3,3,1,1;
- 1,3,3,1,2,2; 1,3,3,2,2,1; 2,3,3,2,1,1;
- 3,3,1,1,2,2; 3,3,1,2,2,1; 3,3,2,2,1,1.
Liczba permutacji Stirlinga rzędu k jest określona przez podwójną silnię (2 k - 1) !!. Permutacje Stirlinga zostały wprowadzone przez Gessela i Stanleya (1978) w celu wykazania, że pewne liczby (liczby permutacji Stirlinga ze stałą liczbą spadków) są nieujemne. Wybrali tę nazwę ze względu na związek z pewnymi wielomianami zdefiniowanymi na podstawie liczb Stirlinga , które z kolei zostały nazwane na cześć XVIII-wiecznego szkockiego matematyka Jamesa Stirlinga .
Permutacji Stirlinga można użyć do opisania sekwencji, za pomocą których można skonstruować ukorzeniony platan z k krawędziami, dodając liście jeden po drugim do drzewa. Bo jeśli krawędzie są ponumerowane według kolejności, w jakiej zostały wstawione, to sekwencja liczb w wycieczce Eulera po drzewie (utworzona przez podwojenie krawędzi drzewa i przechodzenie przez dzieci każdego węzła w kolejności od lewej do prawej) jest permutacją Stirlinga. I odwrotnie, każda permutacja Stirlinga opisuje sekwencję konstrukcji drzewa, w której następna krawędź bliżej korzenia od krawędzi oznaczonej i jest tą, której para wartości najbardziej otacza parę wartości i w permutacji.
Permutacje Stirlinga zostały uogólnione na permutacje zbioru wielokrotnego z więcej niż dwiema kopiami każdej wartości. Naukowcy zbadali również liczbę permutacji Stirlinga, które unikają pewnych wzorców.
Zobacz też
- Parowanie Langforda , inny typ permutacji tego samego multisetu