Permutacje

Zbiór S_n wszystkich wzajemnie jednoznacznych funkcji odwzorowujących zbiór n-elementowy na siebie. Wzajemnie jednoznaczne odwzorowanie f : X $\rightarrow$ X nazywamy permutacją zbioru X. Jeśli X = {1, 2,..., n}, to permutacja f odpowiada sposobowi ustawienia jego elementów w ciąg (bez powtórzeń) (f (1), f (2),..., f (n)). Odwrotnie, każde takie ustawienie w ciąg określa wzajemnie jednoznaczną funkcję f: f (x) to jest x-ty wyraz ciągu. Na przykład ciąg (1, 2,..., n) w naturalnej kolejności odpowiada funkcji tożsamościowej f (x) = x. Często wygodnie jest zapisywać permutacje f za pomocą tabelki funkcji f:

f = $$\left(\vphantom{ \begin{array}{cccc} 1 & 2 & \ldots & n f(1) & f(2) & f(3) & f(4) \end{array} }\right.$$$$\begin{array}{cccc} 1 & 2 & \ldots & n f(1) & f(2) & f(3) & f(4) \end{array}$$$$\left.\vphantom{ \begin{array}{cccc} 1 & 2 & \ldots & n f(1) & f(2) & f(3) & f(4) \end{array} }\right)$$

Jeśli górny wiersz tabelki jest w naturalnej kolejności, to dolny jest ciągiem, odpowiadąjcym permutacji f. Tabelka ma tę przewagę nad ciągiem, że zmiana kolejności wypisywania elementów nie przeszkadza w odczytaniu permutacji - odpowiada przestawieniu kolumn, które można z powrotem uporządkowac:

$$\left(\vphantom{ \begin{array}{cccc} 3 & 4 & 2 & 1 2 & 3 & 4 & 1 \end{array} }\right.$$$$\begin{array}{cccc} 3 & 4 & 2 & 1 2 & 3 & 4 & 1 \end{array}$$$$\left.\vphantom{ \begin{array}{cccc} 3 & 4 & 2 & 1 2 & 3 & 4 & 1 \end{array} }\right)$$ = $$\left(\vphantom{ \begin{array}{cccc} 1 & 2 & 3 & 4 1 & 4 & 2 & 3 \end{array} }\right.$$$$\begin{array}{cccc} 1 & 2 & 3 & 4 1 & 4 & 2 & 3 \end{array}$$$$\left.\vphantom{ \begin{array}{cccc} 1 & 2 & 3 & 4 1 & 4 & 2 & 3 \end{array} }\right)$$

Liczba | S_n| elementów zbioru S_n permutacji zbioru n-elementowego wyraża się wzorem:

| S_n| = n!.

Rzeczywiście, zbiór S₀ ma jeden element (ciąg pusty, majacy 0 wyrazów) i 0! = 1; zbiór S₁ ma jeden element (ciąg jednowyrazowy) i 1! = 1. Załóżmy, że wzór na liczbę permutacji jest prawdziwy dla pewnej liczby naturalnej n. Wyróżnijmy (i nazwijmy (n + 1)-szym) jeden element zbioru (n + 1)-elementowego; pozostałe elementy tworzą zbiór n-elementowy. Każda permutacja zbioru (n + 1)-elementowego powstaje z jednoznacznie określonej permutacji zbioru n-elementowego, którą znajdujemy wykreślajac z tabelki (albo ciągu) (n + 1)-szy element i "dosuwając w lewo" elementy dolnego wiersza tak, żeby nie było w nim pustego miejsca:

$$\left(\vphantom{ \begin{array}{ccccccc} 1 & 2 & \ldots & i & \ldo... ...f(1) & f(2) & \ldots & f(i) = n+1 & \ldots & f(n) & f(n+1) \end{array} }\right.$$$$\begin{array}{ccccccc} 1 & 2 & \ldots & i & \ldots & n & n+1 f(1) & f(2) & \ldots & f(i) = n+1 & \ldots & f(n) & f(n+1) \end{array}$$$$\left.\vphantom{ \begin{array}{ccccccc} 1 & 2 & \ldots & i & \ldo... ...f(1) & f(2) & \ldots & f(i) = n+1 & \ldots & f(n) & f(n+1) \end{array} }\right)$$

$$\rightarrow$$ $$\left(\vphantom{ \begin{array}{ccccccc} 1 & 2 & \ldots & i & \ldo... ... f(1) & f(2) & \ldots & \bullet & \ldots & f(n) & f(n+1) \end{array} }\right.$$$$\begin{array}{ccccccc} 1 & 2 & \ldots & i & \ldots & n & \bullet f(1) & f(2) & \ldots & \bullet & \ldots & f(n) & f(n+1) \end{array}$$$$\left.\vphantom{ \begin{array}{ccccccc} 1 & 2 & \ldots & i & \ldo... ... f(1) & f(2) & \ldots & \bullet & \ldots & f(n) & f(n+1) \end{array} }\right)$$

$$\rightarrow$$ $$\left(\vphantom{ \begin{array}{cccccc} 1 & 2 & \ldots & i & \ldots & n f(1) & f(2) & \ldots & f(i+1) & \ldots & f(n+1) \end{array} }\right.$$$$\begin{array}{cccccc} 1 & 2 & \ldots & i & \ldots & n f(1) & f(2) & \ldots & f(i+1) & \ldots & f(n+1) \end{array}$$$$\left.\vphantom{ \begin{array}{cccccc} 1 & 2 & \ldots & i & \ldots & n f(1) & f(2) & \ldots & f(i+1) & \ldots & f(n+1) \end{array} }\right)$$

Zatem jest n! możliwosci utworzenia ciągu bez (n + 1)-szego elementu. Odtworzyć permutację (ciąg) z ciągu bez (n + 1)-szego elementu można dopisując (n + 1)-szy element, przy czym można to zrobić na n + 1 sposobów: (n + 1)-szy element można dopisać na początku (jako f (1)), przed drugim (jako f (2)), ..., przed n-tym (jako f (n)) albo na końcu (jako f (n + 1)). Łącznie liczba permutacji zbioru (n + 1)-elementowego jest równa

| S_n+1| = (n + 1) ^. | S_n| = (n + 1)n! = (n + 1)!

i wzór na liczbę permutacji jest prawdziwy dla wszystkich liczb naturalnych n na zasadzie indukcji matematycznej.

Uwaga: Permutacje jednego zbioru można ze sobą składać (złożenie funkcji) i obliczać permutację odwrotną (funkcja odwrotna). Łatwo to robić praktycznie za pomocą tabelek. W ten sposób zbiór S_n z działaniem składania okazuje się grupą, zwaną grupą symetryczną.