Zadania kombinatoryczne z ustawieniami

Wyobraź sobie grupę osób ustawiających się do zdjęcia. Te same osoby mogą stworzyć wiele różnych ustawień, bo zmiana miejsc choćby dwóch osób daje nowy wynik. W zadaniach kombinatorycznych z ustawieniami najważniejsze jest więc pytanie: kto może stać gdzie i jakie warunki ograniczają kolejność?

Konkret: ustawienia w codziennych sytuacjach

• Osoby ustawiają się w kolejce.
• Książki układamy na półce.
• Uczniowie zajmują miejsca w rzędzie.
• Wybrane osoby mają stać obok siebie albo nie mogą być sąsiadami.

Reprezentacja: miejsca jako pola

Rysujemy tyle pól, ile jest ustawianych elementów. Na pierwsze miejsce możemy wybrać jeden z n elementów, na drugie jeden z n−1 pozostałych i tak dalej. Liczbę możliwości otrzymujemy przez mnożenie.

• Jeżeli ustawiamy wszystkie n różnych elementów, otrzymujemy n! ustawień.
• Jeżeli ustawiamy tylko k spośród n elementów, stosujemy wariacje bez powtórzeń.
• Jeżeli kilka elementów ma stać razem, traktujemy je chwilowo jak jeden blok.
• Jeżeli elementy nie mogą stać razem, często liczymy wszystkie ustawienia i odejmujemy ustawienia niedozwolone.

Abstrakcja: podstawowe modele

• Wszystkie różne elementy w szeregu: n!.
• Blok złożony z dwóch elementów: ustawiamy blok i pozostałe elementy, a potem liczymy kolejność wewnątrz bloku.
• Warunek „nie obok siebie”: wszystkie ustawienia minus ustawienia z blokiem.

FAJNY TRIK EDUKACYJNY

Zapamiętaj akronim U-S-T-A-W: Ustal elementy, Sprawdź warunki, Traktuj grupy jak bloki, A policz ustawienia, Weryfikuj przypadki. W pałacu pamięci wyobraź sobie czerwony dywan z ponumerowanymi miejscami. Każda osoba po wejściu zamienia się w gigantyczny pionek. Dwie osoby, które mają stać razem, zostają sklejone ogromną gumą w jeden blok, a osoby, które nie mogą być sąsiadami, odpycha sprężyna. Ten obraz przypomina, kiedy łączyć elementy, a kiedy odejmować niedozwolone ustawienia.

Przykład krok po kroku: kolejka

Na ile sposobów może ustawić się w kolejce 5 osób?

• Krok 1: pierwsze miejsce — 5 możliwości.
• Krok 2: drugie miejsce — 4 możliwości.
• Krok 3: kolejne miejsca — 3, 2 i 1 możliwość.
• Krok 4: 5!=5·4·3·2·1=120.
• Wynik: istnieje 120 ustawień.

Przykład krok po kroku: dwie osoby obok siebie

Na ile sposobów można ustawić 5 osób, jeśli Ania i Bartek mają stać obok siebie?

• Krok 1: traktujemy Anię i Bartka jako jeden blok.
• Krok 2: mamy więc 4 obiekty do ustawienia — blok i 3 pozostałe osoby.
• Krok 3: 4!=24 ustawienia obiektów.
• Krok 4: wewnątrz bloku możliwe są ustawienia AB lub BA — 2 możliwości.
• Krok 5: 24·2=48.
• Wynik: są 48 ustawienia.

Przykład krok po kroku: osoby nie mogą stać obok siebie

Na ile sposobów można ustawić 5 osób, jeśli Ania i Bartek nie mogą stać obok siebie?

• Krok 1: wszystkich ustawień jest 5!=120.
• Krok 2: ustawień, w których stoją razem, jest 48.
• Krok 3: odejmujemy 120−48=72.
• Wynik: istnieją 72 dozwolone ustawienia.

Przykład krok po kroku: książki określonego rodzaju razem

Na półce ustawiamy 3 różne książki matematyczne i 2 różne książki historyczne. Ile ustawień ma wszystkie książki matematyczne obok siebie?

• Krok 1: trzy książki matematyczne traktujemy jak jeden blok.
• Krok 2: ustawiamy blok i 2 książki historyczne — 3!=6 sposobów.
• Krok 3: wewnątrz bloku książki matematyczne można ustawić na 3!=6 sposobów.
• Krok 4: 6·6=36.
• Wynik: istnieje 36 ustawień.

Najczęstsze błędy

• Stosowanie n!, mimo że ustawiamy tylko część elementów.
• Zapominanie o kolejności wewnątrz bloku.
• Odejmowanie złej liczby ustawień niedozwolonych.
• Traktowanie identycznych i różnych elementów tak samo.
• Podwójne liczenie tych samych przypadków.

Kontrola wyniku

• Sprawdź, czy każda zamiana miejsc tworzy nowy wynik.
• Policz, ile obiektów pozostaje po utworzeniu bloku.
• Nie zapomnij o ustawieniach wewnątrz bloku.
• Przy warunku „nie razem” wynik powinien być mniejszy od liczby wszystkich ustawień.
• Dla małej liczby elementów wypisz ustawienia i porównaj z obliczeniem.

Najczęstsze pytania