Permutacja to po prostu ustawienie wszystkich danych elementów w określonej kolejności.
Ważne są dwie rzeczy:
• wykorzystujemy wszystkie elementy,
• kolejność ma znaczenie.
Najważniejsza myśl:
Jeżeli ustawiamy n różnych elementów w kolejności, to:
oznacza liczbę wszystkich możliwych ustawień.
Skąd bierze się silnia?
Załóżmy, że ustawiamy 6 różnych osób w kolejce.
Na pierwsze miejsce mamy 6 możliwości.
Na drugie miejsce zostaje już tylko 5 osób.
Potem 4, następnie 3, 2 i 1.
Taki iloczyn zapisujemy krócej:
Silnia
Przyjmujemy też:
Przykład: liczby z warunkiem
Z cyfr 1, 2, 4, 6, 7 tworzymy liczby pięciocyfrowe, używając każdej cyfry dokładnie raz.
Ile z nich jest większych od 60 000?
Aby liczba była większa od 60 000, pierwszą cyfrą musi być:
Na pierwsze miejsce mamy więc 2 możliwości.
Pozostałe 4 cyfry możemy ustawić na:
sposoby.
Przykład: liczby parzyste
Z cyfr 2, 3, 5, 6, 7, 8 tworzymy liczby sześciocyfrowe bez powtarzania cyfr.
Ile z nich jest parzystych?
Liczba parzysta musi kończyć się cyfrą parzystą.
Do wyboru mamy:
czyli 3 możliwości na ostatnią cyfrę.
Pozostałe 5 cyfr ustawiamy dowolnie:
Przykład: osoby w kolejce z warunkiem
W kolejce stoi 8 osób: 3 dziewczyny i 5 chłopców.
Na ile sposobów można ustawić wszystkich tak, aby wszystkie dziewczyny stały na początku kolejki?
Najpierw ustawiamy 3 dziewczyny na pierwszych trzech miejscach:
Potem ustawiamy 5 chłopców:
Te dwa wybory są niezależne, więc mnożymy:
Upraszczanie wyrażeń z silniami
Nie trzeba zawsze liczyć całej silni. Często wygodniej ją rozwinąć tylko tyle, ile potrzeba.
Uprość:
Rozwijamy tylko 10!:
Zatem:
Wskazówka:
Jeśli w ułamku masz np. 12! i 10!, nie licz obu ogromnych liczb.
i 10! od razu się skróci.
Wyznaczanie liczby elementów
Wszystkich permutacji pewnego zbioru jest 720. Ile elementów ma ten zbiór?
Szukamy takiej liczby n, dla której:
Wiemy, że:
Permutacje z powtórzeniami
Czasem nie wszystkie elementy są różne.
Wtedy zwykłe n! daje za dużo wyników, bo zamiana miejscami dwóch identycznych elementów nie tworzy nowego ustawienia.
Ile różnych napisów można utworzyć z liter słowa:
Mamy 7 liter.
Powtarzają się:
• litera M — 2 razy,
• litera A — 2 razy,
• litera T — 2 razy,
• litera E — 1 raz.
Gdyby wszystkie litery były różne, byłoby 7! ustawień.
Musimy jednak podzielić przez ustawienia identycznych liter:
Permutacje z powtórzeniami
Jeżeli mamy n elementów, a niektóre z nich powtarzają się odpowiednio n₁, n₂, …, nₖ razy, to liczba ustawień wynosi:
Jak rozpoznać permutację?
Zadaj sobie trzy pytania:
1. Czy wykorzystuję wszystkie elementy?
2. Czy każdy element wykorzystuję dokładnie raz?
3. Czy kolejność ma znaczenie?
Jeśli tak — bardzo możliwe, że chodzi o permutację.
Zadania
Zadanie 1
Z cyfr 1, 3, 4, 5, 7, 9 tworzymy liczby sześciocyfrowe, używając każdej cyfry dokładnie raz.
Ile z tych liczb jest podzielnych przez 5?
Pokaż rozwiązanie
Liczba jest podzielna przez 5, jeśli kończy się cyfrą 0 lub 5.
Nie mamy cyfry 0, więc ostatnią cyfrą musi być:
Ostatnie miejsce jest więc już ustalone.
Pozostałych 5 cyfr możemy ustawić dowolnie:
Zadanie 2
Z cyfr 1, 2, 3, 4, 5 tworzymy liczby pięciocyfrowe, używając każdej cyfry dokładnie raz.
Ile z nich jest większych od 40 000?
Pokaż rozwiązanie
Aby liczba była większa od 40 000, pierwszą cyfrą musi być:
Czyli na pierwsze miejsce mamy 2 możliwości.
Pozostałe 4 cyfry ustawiamy na:
sposoby.
Zadanie 3
W kolejce ustawia się 9 osób. Wśród nich są Ola i Kuba.
Na ile sposobów można ustawić wszystkich, jeśli Ola ma stać na początku kolejki?
Pokaż rozwiązanie
Pierwsze miejsce jest już zajęte przez Olę.
Pozostałe 8 osób możemy ustawić dowolnie:
Zadanie 4
Pięć różnych osób ma zostać zakwaterowanych w pięciu różnych jednoosobowych pokojach.
Na ile sposobów można je rozmieścić?
Pokaż rozwiązanie
Każda osoba trafia do innego pokoju.
Tak naprawdę ustawiamy 5 osób w 5 różnych miejscach.
Zadanie 5
Uprość:
Pokaż rozwiązanie
Rozwijamy 12! tylko do 9!:
Zatem:
Zadanie 6
Wszystkich możliwych permutacji pewnego zbioru jest:
Ile elementów ma ten zbiór?
Pokaż rozwiązanie
Szukamy n, dla którego:
Wiemy, że:
Zadanie 7
Ile różnych napisów można otrzymać, przestawiając wszystkie litery słowa:
Pokaż rozwiązanie
Słowo ma 6 liter.
Powtarzają się:
A — 3 razy,
N — 2 razy,
S — 1 raz.
Korzystamy ze wzoru na permutacje z powtórzeniami:
Zadanie 8
Ile różnych liczb sześciocyfrowych można otrzymać, przestawiając cyfry liczby:
Pokaż rozwiązanie
Mamy 6 cyfr.
Każda z cyfr 1, 2 i 3 występuje po 2 razy.