Permutacje

Wprowadzenie do uporządkowanych układów

Permutacje są fundamentalnym pojęciem w kombinatoryce, które opisuje wszystkie możliwe uporządkowane układy elementów w danym zbiorze. W permutacjach wszystkie elementy są używane, a ich układ jest ważny. Każda zmiana w kolejności elementów tworzy inną permutację, co odróżnia je od kombinacji, gdzie kolejność nie ma znaczenia.

Jeśli mamy n różnych elementów, liczba wszystkich możliwych permutacji tych elementów wynosi: P(n) = n! (silnia n), gdzie n! = n * (n - 1) * (n - 2) * ... * 2 * 1

Przykład 1: Podstawowe permutacje

Ile różnych układów liter A, B i C istnieje? n = 3, zatem P(3) = 3! = 6. Permutacje to: ABC, ACB, BAC, BCA, CAB, CBA.

Permutacje z powtórzeniami

Jeśli zbiór zawiera powtarzające się elementy, to zamiana identycznych elementów nie tworzy nowej permutacji. W tym przypadku liczba permutacji jest zmniejszona przez podzielenie przez silnie liczby powtórzeń.

Jeśli mamy n elementów, z których:

r_1 jest pierwszego identycznego typu,

r_2 jest drugiego identycznego typu,

...,

r_k jest k-tego identycznego typu,

to wzór to: P(n; r_1, r_2, ..., r_k) = n! / (r_1! * r_2! * ... * r_k!)

Przykład 2: Permutacje z powtarzającymi się elementami

Ile różnych permutacji ma słowo MAMA? Litery: M pojawia się 2 razy, A pojawia się 2 razy, zatem n = 4, r_1 = 2, r_2 = 2. P = 4! / (2! * 2!) = 24 / (2 * 2) = 6. Permutacje to: MAMA, MAAM, AMMA, AAMM, AMAM, MMAA.

Permutacje cykliczne

Gdy układamy elementy w okręgu, mamy do czynienia z permutacjami cyklicznymi. W okręgu rotacje tego samego układu nie są uważane za nowe permutacje.

Dla n różnych elementów w okręgu wzór to: P_cykliczne(n) = (n - 1)!

Przykład: Ustawienie 5 osób wokół stołu, zatem (5 - 1)! = 4! = 24 możliwości.

Związek z wariacjami i kombinacjami

Permutacje: Używa wszystkich elementów, kolejność jest ważna.

Wariacje: Używa podzbioru elementów, kolejność jest ważna.

Kombinacje: Używa podzbioru elementów, kolejność nie jest ważna.

Zastosowania permutacji

Permutacje są używane do:

Układania ludzi, obiektów lub znaków.

Kodowania i tworzenia haseł.

Przestawiania elementów bez powtórzeń.

Rozwiązywania problemów w teorii gier i optymalizacji.

Podsumowanie

Permutacje reprezentują wszystkie możliwe sposoby uporządkowania elementów, gdzie sekwencja jest kluczowa. Liczba permutacji rośnie szybko wraz z liczbą elementów. Zrozumienie różnych form permutacji jest niezbędne do efektywnego rozwiązywania problemów kombinatorycznych.