Permutacja czy kombinacja – kiedy stosować te metody?

Najpierw odpowiedz na dwa pytania: czy kolejność elementów ma znaczenie oraz czy elementy mogą się powtarzać. Jeśli kolejność nie ma znaczenia, zwykle stosujesz kombinację. Jeśli ma znaczenie, wybierasz między permutacją a wariacją, zależnie od tego, czy wykorzystujesz wszystkie elementy i czy dopuszczasz powtórzenia.

Jak szybko rozpoznać metodę?

Kombinatoryka służy do liczenia możliwych wyborów, ustawień i układów bez wypisywania każdego przypadku osobno. W zadaniu nie zaczynaj jednak od wzoru. Najpierw sprawdź, czy zamiana miejscami dwóch elementów tworzy nowy wynik. Zestaw osób A i B jest taki sam jak B i A, ale kolejność A–B w kodzie lub na podium oznacza już inny rezultat.

Drugie pytanie dotyczy powtórzeń. W kodzie PIN cyfra może pojawić się ponownie, natomiast przy losowaniu kart bez zwracania tej samej karty nie wybierzesz drugi raz.

Permutacja czy kombinacja – tabela wyboru

Poniższa tabela pozwala szybko przyporządkować treść zadania do właściwej metody:

Czym różnią się te metody?

Permutacja

Permutacja oznacza uporządkowanie wszystkich elementów zbioru. Kolejność ma znaczenie, a każdy element jest użyty dokładnie raz. Dlatego stosujesz ją przy ustawianiu osób w kolejce, książek na półce albo wszystkich liter w wyrazie.

Dla różnych elementów liczbę permutacji oblicza się jako n!. Silnia oznacza iloczyn kolejnych liczb od 1 do n, na przykład 4! = 4 · 3 · 2 · 1 = 24.

Kombinacja

Kombinacja służy do wyboru grupy, gdy kolejność nie zmienia wyniku. Delegacja złożona z osób A, B i C jest tą samą delegacją niezależnie od kolejności wskazania tych osób. Podobnie przy wyborze kart liczy się ich zestaw, a nie kolejność wyciągania.

W kombinacji bez powtórzeń wybierasz k elementów z n-elementowego zbioru. Typowe przykłady to wybór drużyny, komisji lub kilku zadań spośród większej liczby.

Wariacja bez powtórzeń

Wariacja bez powtórzeń pojawia się wtedy, gdy wybierasz tylko część elementów, ale ich kolejność jest ważna. Przykładem jest podium. Zawodnicy A, B i C zajmujący miejsca w kolejności A–B–C tworzą inny wynik niż B–A–C.

Ten typ pasuje także do ustawienia sześciu osób na dziesięciu numerowanych miejscach. Nie wykorzystujesz wszystkich dostępnych osób, nie możesz użyć jednej osoby dwa razy, ale konkretne miejsce każdej z nich ma znaczenie.

Wariacja z powtórzeniami

Wariacja z powtórzeniami opisuje ciąg, w którym kolejność jest ważna, a ten sam element może pojawić się kilka razy. Najłatwiej rozpoznać ją na przykładzie kodu PIN. Kod 1212 różni się od 2112, a cyfra 1 może zostać użyta więcej niż raz.

Tak samo działa kilka rzutów kostką. Wynik 2, 5, 2 jest innym ciągiem niż 2, 2, 5, a powtórzenie tej samej liczby jest dozwolone.

Najczęstsza pomyłka polega na uznaniu każdego wyboru za kombinację. Sam fakt wybierania elementów nie wystarcza. Jeżeli wynik zapisujesz jako uporządkowany ciąg, przechodzisz do wariacji. W kombinacji interesuje Cię wyłącznie to, jakie elementy znalazły się w grupie.

Jak analizować zadanie krok po kroku?

Przed sięgnięciem po wzór przejdź przez poniższą procedurę:

• Określ zbiór – ustal, ile wszystkich elementów masz do dyspozycji, czyli znajdź n.
• Określ wybór – sprawdź, ile elementów wybierasz lub ile pozycji tworzysz, czyli ustal k.
• Sprawdź kolejność – zapytaj, czy wynik A, B jest inny niż B, A.
• Sprawdź powtórzenia – ustal, czy ten sam element może zostać wybrany ponownie.
• Sprawdź, czy używasz wszystkiego – jeśli kolejność ma znaczenie i wykorzystujesz cały zbiór, chodzi o permutację.

Pomocne są też słowa występujące w treści zadania. „Kolejka”, „miejsca”, „kod”, „numer”, „podium” zwykle wskazują na znaczenie kolejności. „Drużyna”, „delegacja”, „komisja”, „zestaw kart” najczęściej oznaczają kombinację, bo liczy się skład grupy.

Trzeba zachować ostrożność przy identycznych elementach. Klocki z literami A, A, T, T nie są czterema różnymi elementami, mimo że fizycznie mogą występować jako cztery klocki. Zwykłe liczenie wszystkich przestawień zawyżyłoby wynik, ponieważ zamiana dwóch identycznych liter nie tworzy nowego słowa. W takich zadaniach potrzebna jest permutacja z powtórzeniami albo bezpośrednie wypisanie możliwości, jeśli zbiór jest mały.

Krótka wskazówka na koniec

Nie zaczynaj od zapamiętywania wzoru. Najpierw ustal, czy wynik zależy od kolejności, czy można powtarzać elementy i czy wykorzystujesz cały zbiór. Gdy te trzy informacje są jasne, wybór między permutacją, kombinacją i wariacją staje się znacznie prostszy.