Permutacje bez powtórzeń

Autor podstrony: Krzysztof Zajączkowski

Stronę tą wyświetlono już: 10868 razy

A niechaj będzie taki zbiór A={1; 2; 3}, dla którego elementy zbioru B stanowią wszystkie możliwe ułożenia elementów zbioru A. W takim przypadku każdy element zbioru B stanowi permutację bez powtórzeń zbioru A albowiem w zbiorze A nie ma powtarzających się takich samych elementów.

Zbór wszystkich możliwych permutacji stanowi zbiór B, którego elementy wypisane zostały w kolumnie poniżej:

1;2;3 1;3;2 2;1;3 2;3;1 3;2;1 3;1;2

W powyższym przypadku do czynienia mamy z permutacjami bez powtórzeń, dla których wzór na liczebność takiego zbioru można opisać za pomocą następującego wzoru:

Równanie [1] [1]

Zapis wyrażenia w formacie TeX-a:

P_n=n!

gdzie:

Stosując wzór [1] do powyższego przypadku otrzymujemy 3! = 6.

Rozwiążmy teraz kilka prostych zadań związanych z permutacjami bez powtórzeń.

Zadanie 1

Oblicz na ile możliwych, niepowtarzalnych sposobów można ustawić na parkingu obok siebie trzy samochody: Porsche, Doodgea Challengera z 1970 oraz Ferrari F50.

Rozwiązanie:

Nasz zbiór podstawowy składa się z 3 elementów a więc liczba możliwych ułożeń naszych cennych samochodów wynosi 3! = 6.

Zadanie 2

Na półce stoi sześciotomowe dzieło, oblicz: a) ile istnieje sposobów ustawienia tomów na półce; b) ile istnieje możliwości ustawienia tomów tak, aby tomy 1, 2 oraz 3 stały zawsze obok siebie w kolejności rosnącej; c) ile istnieje możliwości ustawienia tak, aby pierwsze trzy tomy stały zawsze obok siebie.

Rozwiązanie:

a) Zbiór podstawowy w tym przypadku składa się z n = 6 elementów, a więc podstawiając do wzoru [2] otrzymujemy liczebność permutacji P6=720.

b) W tym przypadku nasz zbiór podstawowy wygląda następująco: A={123; 4; 5; 6}. Liczebność n=4, a więc P4=24.

c) Ostatni przypadek jest nieco trudniejszy. Podstawowy zbór A={1;2;3}. Dla zbioru A można obliczyć liczebność permutacji dla ustawienia obok siebie poszczególnych tomów, która wynosi P3=3!=6. Nas jednak interesuje ułożenie tych tomów w konfiguracji z pozostałymi tomami tego dzieła. Dla przykładu więc zbór B={PA 1;4;5;6} musi zostać rozpatrzony dla każdej permutacji zbioru A z tego też wynika, że liczebność naszego zbioru rozwiązań będzie iloczynem permutacji zbioru 3 elementowego i 4 elementowoego. Innymi słowy rozwiązanie jest następujące:

Równanie [2] [2]

Zapis wyrażenia w formacie TeX-a:

P_{3}\cdot P_{4}=3!\cdot{4!}=144

Zadanie 3

Ile wyrazów, które mają jak i nie mają znaczenia można ułożyć z liter wyrazu PATYK, ułożonych w taki sposób, aby samogłoski nie znajdowały się obok siebie.

Rozwiązanie:

Od liczby wszystkich możliwych ułożeń odjąć wszystkie możliwe permutacje dla wariantu, gdy samogłoski z sobą sąsiadują, a więc w następujący sposób:

Równanie [3] [3]

Zapis wyrażenia w formacie TeX-a:

P_{5}-P_{2}\cdot P_{4}=5!-2!\cdot{4!}=72
Propozycje książek