permutacje

Permutacje to uporządkowane rozmieszczenia elementów danego zbioru, w których każdy element pojawia się dokładnie raz. Formalnie permutacja zbioru X o n elementach jest bijekcją f: X → X. Zbiór wszystkich permutacji X tworzy grupę zwaną grupą symetryczną, oznaczaną S_n. Grupa ta jest zamknięta względem składania funkcji, zawiera permutację identycznościową i każdej permutacji odpowiada odwrotność.

Dla przykładu zbiór {1, 2, 3} ma 3! = 6 permutacji: 123, 132, 213, 231, 312, 321. Liczba ta rośnie szybciej niż liniowo wraz z liczbą elementów i stanowi podstawową miarę liczby możliwych porządków.

Notacja permutacji najczęściej spotyka się w dwóch formach. W notacji jednowierszowej zapisuje się obraz każdego elementu, np. f = [f(1) f(2) f(3)]. W notacji cyklicznej zapisuje się cyklami, np. (1 2 3) oznacza, że 1→2, 2→3, 3→1, pozostawiając inne elementy nietknięte. Rozkład na cykle pozwala na łatwe opisanie struktury permutacji; każda permutacja jest unikalnie wyrażalna jako zestaw cykli.

Własności obejmują m.in. składanie permutacji, identyczność, odwrotność i fakt, że każda permutacja ma określony porządek (najmniejsza dodatnia liczba k taka, że p^k jest identycznością). Transpozycja, czyli zamiana dwóch elementów, stanowi podstawowy generator między innymi stronami grupy.

Zastosowania obejmują rachunek prawdopodobieństwa, sortowanie, kodowanie i analizy kombinatoryczne. W teorii grup permutacje tworzą fundamenty grupy symetrycznej S_n i badają własności struktur permutacyjnych.