Permutacje bez powtórzeń
gdzie n to liczba wszystkich elementów zbioru, a n! to silnia liczby n
Czym są permutacje bez powtórzeń?
Permutacja bez powtórzeń to każde uporządkowanie wszystkich elementów danego zbioru, w którym każdy element występuje dokładnie raz. Innymi słowy, permutacja to sposób ustawienia n różnych obiektów w określonej kolejności. Zmiana kolejności choćby dwóch elementów tworzy nową permutację.
Liczbę wszystkich permutacji n-elementowego zbioru obliczamy za pomocą silni: n! = 1 · 2 · 3 · ... · n. Na przykład dla 3 elementów {A, B, C} istnieje 3! = 6 różnych ustawień. Wraz ze wzrostem liczby elementów liczba permutacji rośnie niezwykle szybko - już 10 elementów daje ponad 3,6 miliona różnych ustawień.
Elementy wzoru
Liczba permutacji n-elementowego zbioru, czyli liczba wszystkich możliwych uporządkowań n różnych elementów. Wynik jest zawsze liczbą naturalną dodatnią.
Liczba elementów zbioru, który chcemy uporządkować. Musi to być liczba naturalna (n ≥ 0). Wszystkie elementy muszą być różne (bez powtórzeń).
Silnia liczby n, czyli iloczyn wszystkich liczb naturalnych od 1 do n. Na przykład 5! = 1 · 2 · 3 · 4 · 5 = 120. Z definicji przyjmujemy, że 0! = 1.
Interpretacja permutacji
Dla jednego elementu istnieje dokładnie 1 permutacja (1! = 1). Element może stać tylko w jednym miejscu.
Dla małych zbiorów liczbę permutacji łatwo policzyć i wypisać. Na przykład: 2! = 2, 3! = 6, 4! = 24, 5! = 120. Wszystkie ustawienia można wypisać ręcznie.
Silnia rośnie bardzo szybko: 10! = 3 628 800, a 20! to już ponad 2,4 · 1018. Dla dużych zbiorów nie sposób wypisać wszystkich permutacji - służą do tego wzory i algorytmy.
Wizualizacja
Poniższy wykres pokazuje, jak szybko rośnie liczba permutacji wraz ze wzrostem liczby elementów. Oś Y jest w skali logarytmicznej, co pozwala uchwycić ogromne różnice między wartościami silni dla kolejnych n.
Liczba permutacji rośnie szybciej niż jakakolwiek funkcja wykładnicza
3! = 6, 5! = 120, 7! = 5 040, 10! = 3 628 800
Kiedy stosować permutacje bez powtórzeń?
- Ustawianie osób w kolejce lub rzędzie - ile jest sposobów ustawienia n osób w jednej linii, np. kolejka do kasy, układ miejsc
- Kolejność prezentacji lub występów - na ile sposobów można ustalić kolejność n wystąpień, np. porządek referatów na konferencji
- Układanie przedmiotów na półce - ile jest sposobów ułożenia n różnych książek, trofeów czy figurek w rzędzie
- Tworzenie anagramów - ile różnych słów (nawet bezsensownych) można utworzyć ze wszystkich liter danego wyrazu, gdy żadna litera się nie powtarza
Przykłady obliczeniowe
Przykład 1: Ustawienie osób w rzędzie
Zadanie: Na ile sposobów można ustawić 5 osób w jednym rzędzie?
Rozwiązanie:
Szukamy liczby permutacji 5 elementów:
Odpowiedź: 5 osób można ustawić w rzędzie na 120 różnych sposobów.
Przykład 2: Kolejność książek na półce
Zadanie: Mamy 7 różnych książek. Na ile sposobów można je ustawić obok siebie na półce?
Rozwiązanie:
Każde ustawienie wszystkich 7 książek to permutacja:
Odpowiedź: 7 książek można ułożyć na półce na 5 040 różnych sposobów.
Przykład 3: Anagramy wyrazu
Zadanie: Ile różnych ciągów liter (anagramów) można utworzyć ze wszystkich liter wyrazu "LAMPA"? Uwaga: litera A powtarza się, ale najpierw policzmy tak, jakby litery były różne.
Rozwiązanie:
Wyraz "LAMPA" ma 5 liter. Gdyby wszystkie były różne, mielibyśmy:
Jednak litera A występuje 2 razy, więc stosujemy permutacje z powtórzeniami:
Odpowiedź: Z liter wyrazu "LAMPA" można utworzyć 60 różnych anagramów. Gdyby wszystkie litery były różne (np. w wyrazie "LAMPY"), byłoby ich 120.
Przykład 4: Ustalanie kolejności zawodników
Zadanie: W finale biegu startuje 8 zawodników. Na ile sposobów mogą zająć miejsca od 1 do 8 (zakładając brak remisów)?
Rozwiązanie:
Każda kolejność na mecie to permutacja 8 zawodników:
Odpowiedź: Istnieje 40 320 możliwych kolejności na mecie 8 zawodników.
Częste błędy
Mylenie permutacji z kombinacjami
Permutacje liczą uporządkowania (kolejność ma znaczenie), a kombinacje liczą wybory (kolejność nie ma znaczenia). Ustawienie {A, B, C} i {C, B, A} to dwie różne permutacje, ale ta sama kombinacja.
Stosowanie permutacji przy powtarzających się elementach
Wzór P(n) = n! zakłada, że wszystkie elementy są różne. Jeśli niektóre się powtarzają (np. litery w wyrazie "MAMA"), należy użyć wzoru na permutacje z powtórzeniami.
Błędne obliczanie silni
Silnia to iloczyn kolejnych liczb naturalnych od 1 do n. Częstym błędem jest pominięcie jednego czynnika lub nieprawidłowe mnożenie. Warto liczyć krok po kroku: 5! = 1 · 2 = 2, potem 2 · 3 = 6, 6 · 4 = 24, 24 · 5 = 120.
Używanie permutacji zamiast wariacji
Permutacje dotyczą ustawienia WSZYSTKICH elementów zbioru. Jeśli wybieramy i ustawiamy tylko k elementów z n (k < n), to jest wariacja bez powtórzeń, nie permutacja.
Porady i wskazówki
Rozumowanie krok po kroku: Na pierwsze miejsce możesz wybrać n elementów, na drugie n-1, na trzecie n-2 itd. Mnożąc: n · (n-1) · (n-2) · ... · 1 = n!. Ten tok rozumowania pomaga zrozumieć, skąd bierze się silnia.
Wartości silni warto zapamiętać: 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720, 7! = 5 040, 8! = 40 320, 9! = 362 880, 10! = 3 628 800. Na maturze nie musisz ich znać na pamięć, ale znajomość pierwszych wartości przyspiesza obliczenia.
Słowa kluczowe w zadaniach: Rozpoznasz permutacje po zwrotach takich jak: "na ile sposobów można ustawić", "ile jest różnych kolejności", "ile jest uporządkowań", "ustalić kolejność". Gdy w zadaniu jest mowa o WSZYSTKICH elementach i ich KOLEJNOŚCI - to permutacja.
Związek z wariacjami: Permutacja to szczególny przypadek wariacji, w którym k = n. Wzór na wariacje V(n,k) = n!/(n-k)! dla k = n daje n!/0! = n!/1 = n!, czyli permutację.
Przypadki szczególne
Permutacja zbioru pustego
Dla n = 0 istnieje dokładnie jedna permutacja - permutacja pusta. Dlatego z definicji 0! = 1.
Permutacje cykliczne
Gdy elementy ustawiamy w okrąg (np. osoby przy okrągłym stole), liczba różnych ustawień jest mniejsza, bo obrót nie tworzy nowego układu.
Przykład: 5 osób przy okrągłym stole można posadzić na (5-1)! = 4! = 24 sposoby.
Permutacje z powtórzeniami
Gdy wśród n elementów niektóre się powtarzają (np. n1 elementów jednego rodzaju, n2 drugiego itd.), stosujemy inny wzór.
Przykład: Anagramy wyrazu "MAMA" (4 litery, M×2, A×2): 4!/(2!·2!) = 6.
Permutacje z ustalonymi pozycjami
Jeśli k elementów ma ustalone pozycje, permutujemy tylko pozostałe n-k elementów.
Przykład: 6 osób w rzędzie, ale 2 osoby muszą stać na końcach - permutujemy 4 pozostałe: 4! · 2! = 48.