Zadania z kombinatoryki - jak rozpoznać wariację, permutację i kombinację

Klasa 3 liceum i technikum

Zadanie z kombinatoryki rozwiązujemy w trzech krokach: najpierw ustalamy, co jest jednym wynikiem (ciąg, ustawienie czy zbiór), potem dzielimy liczenie na etapy (mnożymy) albo przypadki (dodajemy), a na końcu sprawdzamy, czy żaden wynik nie został policzony dwa razy. Wzory na wariacje, permutacje i kombinacje to tylko gotowe klocki - w zadaniach maturalnych prawie zawsze trzeba je łączyć.

Krok 1: co jest jednym wynikiem?

Najpewniejszy test na kolejność: zamień miejscami dwa wybrane elementy i zapytaj, czy wynik jest ten sam. W grupie $10$ osób:

• „wybierz $3$ osoby na dyżur” - zamiana nic nie zmienia, to zbiór: $\binom{10}{3} = 120$;
• „wybierz zwycięzcę, drugie i trzecie miejsce” - zamiana daje inny wynik, to ciąg: $10 \cdot 9 \cdot 8 = 720$;
• „ustaw wszystkie $10$ osób w kolejce” - ciąg ze wszystkich elementów: $10! = 3\,628\,800$.

Słowa w treści bywają mylące. „Ile jest liczb trzycyfrowych…” to zawsze ciąg cyfr (kolejność ma znaczenie), nawet jeśli w treści pada słowo „wybieramy”. A „ile jest trójkątów o wierzchołkach w danych punktach” to zbiór, bo trójkąt $ABC$ to ten sam trójkąt co $CAB$.

Łączenie modeli: wybór grupy i funkcji

Przykład 1. Z $10$ osób wybieramy czteroosobowy zespół, a w nim jednego lidera. Na ile sposobów można to zrobić?

Sposób 1. Najpierw zespół, potem lider. Zespół to zbiór: $\binom{10}{4} = 210$. Lidera wybieramy spośród $4$ członków zespołu:

$\binom{10}{4} \cdot 4 = 210 \cdot 4 = 840.$

Sposób 2. Najpierw lider, potem reszta. Lider - jedna z $10$ osób, pozostałych trzech członków wybieramy z $9$ osób:

$10 \cdot \binom{9}{3} = 10 \cdot 84 = 840.$

Dwa różne rozumowania dały ten sam wynik - to najlepsze sprawdzenie w kombinatoryce. Jeśli umiesz policzyć coś na dwa sposoby, zrób to.

Przypadki i reguła dodawania: „dokładnie” i „co najwyżej”

Przykład 2. W grupie jest $6$ dziewcząt i $7$ chłopców. Na ile sposobów można wybrać czteroosobową delegację, w której jest co najwyżej jedna dziewczyna?

„Co najwyżej jedna” to dwa rozłączne przypadki: zero dziewcząt albo dokładnie jedna.

Krok 1. Zero dziewcząt - same chłopcy: $\binom{7}{4} = 35$.

Krok 2. Dokładnie jedna dziewczyna - jedna z $6$ dziewcząt i trzech z $7$ chłopców: $6 \cdot \binom{7}{3} = 6 \cdot 35 = 210$.

Krok 3. Reguła dodawania: $35 + 210 = 245$.

Odpowiedź: $245$ delegacji.

Zdarzenie przeciwne: „co najmniej jeden”

Przykład 3. Ta sama grupa ($6$ dziewcząt, $7$ chłopców). Ile jest czteroosobowych delegacji, w których jest co najmniej jedna dziewczyna?

Wprost to cztery przypadki (jedna, dwie, trzy, cztery dziewczyny). Przeciwieństwo - żadnej dziewczyny - to jeden przypadek:

$\binom{13}{4} - \binom{7}{4} = 715 - 35 = 680.$

Pułapka podwójnego liczenia. Kusi rozumowanie: „najpierw wybieram jedną dziewczynę ($6$ sposobów), żeby warunek był spełniony, a potem dowolne trzy osoby z pozostałych $12$”. Daje to $6 \cdot \binom{12}{3} = 6 \cdot 220 = 1320$ - prawie dwa razy za dużo. Dlaczego? Delegacja z dwiema dziewczynami, Anią i Basią, została policzona dwa razy: raz, gdy „pierwszą” była Ania, a Basia weszła w „dowolne trzy”, i drugi raz odwrotnie. Wybór „najpierw jedna, potem reszta” sztucznie wprowadza kolejność tam, gdzie jej nie ma. Bezpieczne są tylko dwie drogi: dopełnienie albo rozłączne przypadki „dokładnie $1$, $2$, $3$, $4$”:

$6 \cdot 35 + 15 \cdot 21 + 20 \cdot 7 + 15 \cdot 1 = 210 + 315 + 140 + 15 = 680.$

Elementy, które nie mogą stać obok siebie

Przykład 4. Cztery dziewczyny i trzech chłopców ustawiają się w rzędzie. Na ile sposobów mogą to zrobić, jeśli żadnych dwóch chłopców nie może stać obok siebie?

Dopełnienie byłoby tu kłopotliwe (chłopcy mogą stać po dwóch albo po trzech obok siebie). Lepsza jest metoda luk.

Krok 1. Ustawiamy dziewczyny: $4! = 24$ sposoby. Między nimi i na brzegach powstaje $5$ luk:

$\_\ D\ \_\ D\ \_\ D\ \_\ D\ \_$

Krok 2. Wstawiamy chłopców w luki - każdy w inną lukę, więc nigdy nie staną obok siebie. Chłopcy są różni, a luki też, więc to wariacja bez powtórzeń: $V_5^3 = 5 \cdot 4 \cdot 3 = 60$.

Krok 3. $24 \cdot 60 = 1440$.

Odpowiedź: $1440$ ustawień (na $7! = 5040$ wszystkich).

Podział na grupy: kiedy dzielić przez k!

Przykład 5. Sześć osób dzielimy na trzy pary (np. do gry w szachy). Na ile sposobów?

Krok 1. Wybieramy pary po kolei: pierwszą na $\binom{6}{2} = 15$ sposobów, drugą z pozostałych czterech na $\binom{4}{2} = 6$, ostatnia para jest wymuszona: $15 \cdot 6 \cdot 1 = 90$.

Krok 2. Usuwamy kolejność par. Pary nie mają numerów - podział $\{AB, CD, EF\}$ to to samo co $\{CD, EF, AB\}$. Każdy podział policzyliśmy $3! = 6$ razy:

$\frac{90}{3!} = 15.$

Gdyby pary szły do ponumerowanych pokoi, dzielenie przez $3!$ byłoby błędem i wynik wynosiłby $90$. Pytanie kontrolne: czy grupy są rozróżnialne?

Kombinatoryka a prawdopodobieństwo

Prawie każde szkolne zadanie z prawdopodobieństwa to dwa zadania z kombinatoryki: liczymy wszystkie wyniki i wyniki sprzyjające. W urnie jest $5$ kul białych i $3$ czarne, losujemy jednocześnie dwie. Prawdopodobieństwo, że obie są białe:

$P = \frac{\binom{5}{2}}{\binom{8}{2}} = \frac{10}{28} = \frac{5}{14}.$

Ważne, żeby licznik i mianownik liczyć tym samym modelem (tu oba jako kombinacje). Więcej: rachunek prawdopodobieństwa i zaskakujący paradoks urodzin.

Typowe błędy

• „Najpierw jeden, potem reszta” przy warunku „co najmniej jeden” - liczy te same grupy wiele razy. Używaj dopełnienia albo rozłącznych przypadków.
• Przypadki, które się pokrywają. Przed dodaniem sprawdź, czy żaden wynik nie należy do dwóch przypadków.
• Dzielenie przez $k!$ przy grupach rozróżnialnych (pokoje, drużyny o nazwach) albo jego brak przy nierozróżnialnych.
• Różne modele w liczniku i mianowniku prawdopodobieństwa - albo oba z kolejnością, albo oba bez.

Najczęstsze pytania

Jak rozpoznać, czy to wariacja, permutacja czy kombinacja? Zapytaj, czy kolejność ma znaczenie. Jeśli nie - kombinacja. Jeśli tak i ustawiamy wszystkie elementy - permutacja. Jeśli tak i wybieramy tylko część - wariacja (z powtórzeniami, gdy elementy mogą się powtarzać, bez powtórzeń, gdy nie mogą).

Kiedy liczyć przez zdarzenie przeciwne? Gdy warunek brzmi „co najmniej jeden” albo „nie wszystkie”. Liczymy wszystkie możliwości i odejmujemy te bez żadnego wyróżnionego elementu - to zwykle jeden prosty przypadek.

Dlaczego nie można najpierw wybrać jednej dziewczyny, a potem reszty delegacji? Bo delegacja z kilkoma dziewczynami zostaje policzona kilka razy - raz dla każdej dziewczyny, która mogła być wybrana „jako pierwsza”. Wynik wychodzi za duży.

Kiedy w kombinatoryce dodajemy, a kiedy mnożymy? Mnożymy kolejne etapy jednego wyboru (wybieramy matematyków i fizyków). Dodajemy rozłączne przypadki (zero dziewcząt lub jedna dziewczyna).

Jak policzyć ustawienia, w których dwie osoby nie stoją obok siebie? Najprościej przez dopełnienie: wszystkie ustawienia minus ustawienia, w których stoją obok siebie (sklejone w blok). Gdy takich osób jest więcej, ustaw najpierw pozostałe osoby i wstawiaj „zakazane” w luki między nimi.

Na ile sposobów można podzielić 6 osób na 3 pary? Na $\tfrac{\binom{6}{2} \cdot \binom{4}{2} \cdot \binom{2}{2}}{3!} = 15$ sposobów. Dzielimy przez $3!$, bo pary nie są ponumerowane.

Przećwicz

• Kombinatoryka - zadania mieszane → - rozpoznawanie modelu, „co najmniej jeden” przez dopełnienie, zasada włączeń i wyłączeń, podział na grupy i do pokoi, liczby o danej sumie cyfr (zadania z pełnym rozwiązaniem krok po kroku).
• Zadania z poprzednich lekcji: reguła mnożenia, wariacje, permutacje, kombinacje.
• Cały zestaw: kombinatoryka - zadania z rozwiązaniami →

Podsumowanie

• Najpierw ustal, co jest jednym wynikiem: ciąg (kolejność ważna) czy zbiór.
• Etapy mnożymy, rozłączne przypadki dodajemy; „co najmniej jeden” liczymy przez dopełnienie.
• „Najpierw jeden wyróżniony, potem reszta” prowadzi do podwójnego liczenia.
• „Nie obok siebie”: dopełnienie dla dwóch elementów, metoda luk dla większej liczby.
• Grupy nierozróżnialne - dzielimy przez liczbę ich ustawień $k!$.
• Gdy się da, policz wynik dwoma sposobami.

Zobacz też

• Symbol Newtona i trójkąt Pascala - następna lekcja: własności liczb $\binom{n}{k}$.
• Zasada włączeń i wyłączeń - liczenie, gdy przypadki się pokrywają.
• Zasada szufladkowa Dirichleta - gdy trzeba pokazać, że coś musi się powtórzyć.