Permutacje
Permutacją zbioru $n$-elementowego nazywamy każdy n-wyrazowy ciąg utworzony ze wszystkich elementów tego zbioru.
Permutacja spełnia następujące warunki:
- każda permutacja obejmuje wszystkie dane elementy,
- istotna jest kolejność elementów permutacji.
Z permutacjami zbioru mamy do czynienia wówczas, gdy porządkujemy elementy tego zbioru. Permutacja to każde ustawienie wszystkich elementów zbioru w dowolnej kolejności.
Z trzech danych elementów: a, b, c, można utworzyć następujące permutacje:
$\{a, b, c\}, \{a, c, b\}, \{b, a, c\}, \{b, c, a\}, \{c, a, b\}, \{c, b, a\}$
Liczba permutacji zbioru złożonego z $n$ elementów jest równa $n!$ ($n$ silnia). $$P_n = n!$$
Zdefiniowane wyżej pojęcie permutacji można rozszerzyć na przypadki, gdy brane są pod uwagę powtórzenia elementów. Permutacja z powtórzeniami rozpatruje przypadki, gdy liczba powtórzeń danego elementu jest ściśle określona.
Permutacją z powtórzeniami zbioru n-elementowego, nazywamy każdy ciąg $n$-wyrazowy utworzony z elementów tego zbioru, wśród których pewne elementy powtarzają się odpowiednio $n_1, n_2, \ldots, n_k$ razy.
Jeżeli spośród elementów: $a$, $b$ i $c$, element $a$ weźmiemy dwa razy, element $b$ jeden raz i element $c$ jeden raz,
możemy utworzyć następujące permutacje z powtórzeniami.
$\{a, a, b, c\}, \{a, a, c, b\}, \{a, b, a, c\}, \{a, b, c, a\}, \{a, c, a, b\}, \{a, c, b, a\},$
$\{b, a, a, c\}, \{b, a, c, a\}, \{b, c, a, a\}, \{c, a, a, b\}, \{c, a, b, a\}, \{c, b, a, a\}$
Liczba permutacji z powtórzeniami zbioru n-elementowego, wśród których pewne elementy powtarzają się odpowiednio $n_1, n_2, \ldots, n_k$ razy wyraża się wzorem $P_n^{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1! n_2! \ldots n_k!}$