PERMUTACJE

Permutacja to wzajemnie jednoznaczne przekształcenie pewnego zbioru na siebie.

Permutacje zbiorów skończonych mogą być utożsamiane z ustawianiem elementów zbioru w pewnej kolejności.

Zapis macierzowy:

Permutację można też zapisać jako macierz A, taką, że

Na przykład permutację

można zapisać jako

Cykle:

Cyklem nazywamy każdą permutację postaci:

Cyklem jest permutacja:

którą można zapisać jako

Każdą permutację da się zapisać jako złożenie pewnej liczby cykli. Rozkład na cykle:

Permutacja bez powtórzeń:

n-elementowy zbiór

Pn = n!

Przykład:

Elementy zbioru A = {a,b,c} można ustawić w ciąg na P3 = 3! = 6 sposobów: abc,acb,bac,bca,cab,cba.

• Permutacja z powtórzeniami

Niech A oznacza zbiór złożony z k różnych elementów A = {a₁,a₂,...,a_k}. Permutacją n elementową z powtórzeniami, w której elementy a₁,a₂,...,a_k powtarzają się odpowiednio n₁,n₂,...,n_k razy, n₁ + n₂ + ... + n_k = n, jest każdy n-wyrazowy ciąg, w którym elementy a₁,a₂,...,a_k powtarzają się podaną liczbę razy.

Przykład:

Mamy dane dwie liczby: 1 i 2. Liczba permutacji 3-elementowych z powtórzeniami, gdy „1” pojawia się 2 razy wynosi: 3.

112

121

211

Permutacja z powtórzeniami to okrojona wariacja z powtórzeniami: odrzucamy tu wszystkie wyniki, gdzie „2” pojawia się 2 lub więcej razy, a więc:

221

212

122

222

Oraz, gdzie „1” pojawia się 3 razy: 111.

(ilość wariacji z powtórzeniami = 8).

WARIACJE

Wariacją z powtórzeniami k-wyrazową zbioru n-elementowego nazywa się każdy k-wyrazowy ciąg elementów tego zbioru (dowolny element może wystąpić wielokrotnie w ciągu). Kolejnosć ma znaczenie.

• Przykład

Za pomocą cyfr 1, 2, 3, 4, 5 można zapisać 25 liczb dwucyfrowych (niekoniecznie różnocyfrowych).

Wariacją bez powtórzeń k-wyrazową zbioru n-elementowego A
nazywa się każdy k-wyrazowy ciąg różnych elementów tego zbioru. Gdy k=n, wariację bez powtórzeń nazywa się permutacją. Kolejnosć ma znaczenie.

Przykład

Z cyfr 1, 2, 3, 4, 5 można utworzyć 20 liczb dwucyfrowych o różnych cyfrach.

KOMBINACJE

Kombinacja z powtórzeniami k-elementowa zbioru n-elementowego A to każdy k-elementowy multizbiór składający się z elementów zbioru A. Elementy te mogą się powtarzać.

• Przykład

Liczba kombinacji 2-elementowych z powtórzeniami zbioru 4-elementowego A = {a, b, c, d} jest równa
. Można je wymienić: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a,a}, {b,b}, {c,c}, {d,d}. Kolejność nie ma tutaj znaczenia, równie dobrze można napisać {c,d}, jak {d,c}.

Kombinacja bez powtórzeń to każdy podzbiór zbioru skończonego. Kombinacją k-elementową zbioru n-elementowego A nazywa się każdy k-elementowy podzbiór zbioru A (0≤k≤n). Dopełnieniem kombinacji z n po k jest kombinacja z n po n-k.

• Przykład

Liczba kombinacji 2-elementowych zbioru 4-elementowego A={a, b, c, d} jest równa
. Kombinacjami są podzbiory: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}.

---