Permutacje

Wyobraź sobie pięć różnych książek rozsypanych na podłodze. Możesz ustawiać je na półce w wielu kolejnościach, a każda zmiana miejsc tworzy nowe ustawienie. Permutacje pomagają policzyć wszystkie takie ustawienia bez wypisywania ich pojedynczo.

Konkret: ustawianie przedmiotów

• Ustawiasz osoby w kolejce.
• Układasz różne książki na półce.
• Tworzysz szyk liter z różnych znaków.
• Rozmieszczasz zawodników na miejscach od pierwszego do ostatniego.

Reprezentacja: malejąca liczba wyborów

Jeżeli ustawiasz n różnych elementów, to na pierwszym miejscu możesz wybrać jeden z n elementów. Na drugim zostaje n−1 możliwości, na trzecim n−2 i tak dalej, aż na ostatnim miejscu pozostaje tylko jeden element.

• Pierwsze miejsce: n możliwości.
• Drugie miejsce: n−1 możliwości.
• Trzecie miejsce: n−2 możliwości.
• Ostatnie miejsce: 1 możliwość.

Abstrakcja: silnia

Liczba permutacji n różnych elementów wynosi n!, czyli iloczyn wszystkich dodatnich liczb całkowitych od n do 1.

• n!=n·(n−1)·(n−2)·...·2·1.
• 1!=1.
• 0!=1.
• Dla 4 elementów: 4!=4·3·2·1=24.

FAJNY TRIK EDUKACYJNY

Zapamiętaj akronim U-S-T-A-W: Upewnij się, że elementy są różne, Sprawdź, czy używasz wszystkich, Traktuj kolejność jako ważną, Aktualizuj liczbę wolnych miejsc, Wymnóż malejące liczby. W pałacu pamięci gigantyczny wykrzyknik stoi przy drzwiach i wpuszcza osoby do kolejki. Za każdym wejściem kurczy się o jeden poziom: 5, potem 4, potem 3, 2 i 1. To wykrzyknik silni — wielki znak, który przypomina o mnożeniu malejących liczb.

Przykład krok po kroku: książki

Na półce ustawiamy 4 różne książki. Na ile sposobów można je ułożyć?

• Krok 1: na pierwsze miejsce wybieramy 1 z 4 książek.
• Krok 2: na drugie miejsce zostają 3 książki.
• Krok 3: potem zostają 2, a na końcu 1.
• Krok 4: 4·3·2·1=24.
• Wynik: książki można ustawić na 24 sposoby.

Przykład krok po kroku: osoby w szeregu

Pięć osób ustawia się w jednym szeregu. Ile różnych ustawień może powstać?

• Krok 1: wybór pierwszej osoby — 5 możliwości.
• Krok 2: wybór drugiej — 4 możliwości.
• Krok 3: dalej 3, 2 i 1 możliwość.
• Krok 4: 5!=5·4·3·2·1=120.
• Wynik: istnieje 120 ustawień.

Przykład krok po kroku: cyfry bez powtórzeń

Ile liczb czterocyfrowych można utworzyć z cyfr 1, 2, 3, 4, używając każdej dokładnie raz?

• Krok 1: używamy wszystkich 4 różnych cyfr.
• Krok 2: kolejność cyfr ma znaczenie.
• Krok 3: liczba ustawień to 4!.
• Krok 4: 4!=24.
• Wynik: można utworzyć 24 liczby.

Permutacje z powtórzeniami

Jeżeli niektóre elementy są identyczne, zwykłe n! liczy część ustawień wielokrotnie. Wtedy dzielimy przez silnie liczebności powtarzających się grup.

Dla n elementów, wśród których odpowiednio n₁, n₂, ... elementów jest jednakowych, liczba ustawień wynosi n!/(n₁!·n₂!·...).

Przykład krok po kroku: słowo MAMA

Ile różnych ustawień liter można utworzyć ze słowa MAMA?

• Krok 1: mamy 4 litery.
• Krok 2: litera M powtarza się 2 razy, a litera A także 2 razy.
• Krok 3: liczba ustawień to 4!/(2!·2!).
• Krok 4: 24/(2·2)=6.
• Wynik: istnieje 6 różnych ustawień.

Najczęstsze błędy

• Stosowanie n!, gdy nie używamy wszystkich elementów.
• Ignorowanie powtarzających się elementów.
• Liczenie sytuacji, w których kolejność nie ma znaczenia, jako permutacji.
• Zapominanie, że 0!=1.
• Błędne rozwijanie silni, na przykład 5!=5·4 zamiast 5·4·3·2·1.

Kontrola wyniku

• Dla 3 elementów wypisz wszystkie ustawienia i sprawdź, że jest ich 3!=6.
• Upewnij się, że każda permutacja wykorzystuje wszystkie elementy dokładnie raz.
• Sprawdź, czy zamiana dwóch miejsc rzeczywiście tworzy nowy wynik.
• Przy powtórzeniach sprawdź, ile identycznych ustawień policzyłoby samo n!.
• Oceń, czy wynik rośnie szybko wraz z liczbą elementów.

Najczęstsze pytania