Zasada mnożenia
Jeśli czynność składa się z k etapów, a etap i-ty można wykonać na |Ai| sposobów (niezależnie od wyborów w pozostałych etapach), to cała czynność może być wykonana na |A1| · |A2| · ... · |Ak| sposobów
Czym jest zasada mnożenia?
Zasada mnożenia (zwana też regułą iloczynu) to podstawowa zasada kombinatoryki, która pozwala obliczyć liczbę możliwych wyników procesu wieloetapowego. Jeśli pewna czynność składa się z kolejnych etapów, a liczba możliwości na każdym etapie jest niezależna od wyborów na etapach poprzednich, to łączną liczbę wyników otrzymujemy, mnożąc liczby możliwości na poszczególnych etapach.
To najprostsza i zarazem najczęściej stosowana zasada zliczania. Leży u podstaw wszystkich wzorów kombinatorycznych - permutacje, wariacje i kombinacje można wyprowadzić właśnie z zasady mnożenia. Intuicyjnie: każda możliwość na pierwszym etapie "rozgałęzia się" na wszystkie możliwości na drugim etapie, dając iloczyn.
Elementy zasady
Zbiory możliwości na kolejnych etapach. Etap i-ty ma |Ai| możliwych wyborów. Na przykład: A1 = {koszulki}, A2 = {spodnie}, A3 = {buty}.
Liczba elementów (moc) zbioru Ai, czyli liczba możliwości na i-tym etapie. Musi być stała - nie może zależeć od wyborów dokonanych wcześniej.
Iloczyn kartezjański - zbiór wszystkich uporządkowanych k-tek (a1, a2, ..., ak), gdzie ai ∈ Ai. Każda taka k-tka to jeden pełny wynik procesu.
Liczba etapów (wyborów). Zasada działa dla dowolnej liczby etapów: dwóch, trzech, czterech i więcej. Dla k = 2 jest to najprostsza postać: |A × B| = |A| · |B|.
Interpretacja zasady
Wyobraź sobie drzewo, w którym każdy węzeł rozgałęzia się na tyle gałęzi, ile jest możliwości na danym etapie. Jeśli pierwszy etap ma m gałęzi, a drugi n, to na końcu drzewa jest m · n liści - każdy liść to jeden możliwy wynik. Trzeci etap pomnoży liczbę liści przez swoją liczbę możliwości itd.
Kluczowy warunek: liczba możliwości na każdym etapie musi być stała i niezależna od wyborów na poprzednich etapach. Jeśli wybór na etapie 1 ogranicza opcje na etapie 2, zasada mnożenia w prostej formie nie działa - trzeba analizować przypadki osobno lub użyć bardziej zaawansowanych metod.
Słowo "i" w treści zadania często sygnalizuje mnożenie: "wybieramy koszulkę I spodnie I buty" - mnożymy. Natomiast "lub" sygnalizuje dodawanie (zasada dodawania). Ta prosta reguła pomaga rozpoznać, którą zasadę zastosować.
Wizualizacja
Poniższy wykres ilustruje zasadę mnożenia dla trzech etapów: 4 koszulki × 3 pary spodni × 2 pary butów = 24 zestawy. Słupki pokazują, jak liczba możliwości rośnie po każdym etapie (4, potem 4 · 3 = 12, potem 12 · 2 = 24).
4 możliwości
3 możliwości → 4 · 3 = 12
2 możliwości → 12 · 2 = 24
Kiedy stosować zasadę mnożenia?
- Procesy wieloetapowe - gdy czynność dzieli się na kolejne, niezależne kroki (wybór koszulki, potem spodni, potem butów)
- Kody i hasła - obliczanie liczby możliwych kodów PIN, tablic rejestracyjnych, haseł (każda pozycja to osobny etap)
- Iloczyn kartezjański - gdy szukamy liczby par, trójek lub k-tek z danych zbiorów
- Fundament innych wzorów - permutacje (n · (n-1) · ... · 1), wariacje i inne wzory kombinatoryczne wynikają z zasady mnożenia
Przykłady obliczeniowe
Przykład 1: Kompletowanie zestawu ubrań
Zadanie: Masz 5 koszulek, 4 pary spodni i 3 pary butów. Na ile sposobów możesz skomponować zestaw składający się z koszulki, spodni i butów?
Rozwiązanie:
Wybór zestawu składa się z trzech niezależnych etapów. Stosujemy zasadę mnożenia:
Odpowiedź: Można skomponować 60 różnych zestawów. Każda z 5 koszulek łączy się z każdą z 4 par spodni (20 kombinacji), a każda z tych 20 kombinacji z każdą z 3 par butów.
Przykład 2: Kod PIN
Zadanie: Ile jest czterocyfrowych kodów PIN (cyfry od 0 do 9), jeśli cyfry mogą się powtarzać?
Rozwiązanie:
Każda z 4 pozycji to osobny etap z 10 możliwymi cyframi (0-9). Wybory są niezależne (cyfry mogą się powtarzać).
Odpowiedź: Istnieje 10 000 różnych kodów PIN. To kody od 0000 do 9999. Gdyby cyfry nie mogły się powtarzać, byłoby 10 · 9 · 8 · 7 = 5040 kodów.
Przykład 3: Tablica rejestracyjna
Zadanie: Tablica rejestracyjna składa się z 2 liter (z 26 liter alfabetu łacińskiego) i 4 cyfr (0-9). Ile jest możliwych tablic?
Rozwiązanie:
Mamy 6 pozycji: 2 literowe i 4 cyfrowe. Każda pozycja to niezależny etap.
Odpowiedź: Istnieje 6 760 000 możliwych tablic rejestracyjnych. Zasadę mnożenia zastosowaliśmy dwukrotnie: najpierw do grup (litery i cyfry), potem do poszczególnych pozycji.
Przykład 4: Trasy przejazdu
Zadanie: Z miasta A do miasta B prowadzą 3 drogi, z miasta B do C prowadzą 4 drogi, a z C do D prowadzą 2 drogi. Na ile sposobów można przejechać z A do D przez B i C?
Rozwiązanie:
Podróż składa się z 3 etapów: A → B (3 drogi), B → C (4 drogi), C → D (2 drogi). Wybór drogi na każdym etapie jest niezależny.
Odpowiedź: Z miasta A do D przez B i C można przejechać na 24 sposoby. Każda z 3 dróg A → B łączy się z każdą z 4 dróg B → C (12 tras do C), a każda z nich z każdą z 2 dróg C → D.
Częste błędy
Mylenie mnożenia z dodawaniem
Gdy wybieramy koszulkę I spodnie, mnożymy (5 · 4 = 20). Gdy wybieramy koszulkę LUB spodnie (jedno z dwóch), dodajemy (5 + 4 = 9). Słowo "i" oznacza mnożenie, "lub" oznacza dodawanie. Pomylenie tych zasad prowadzi do drastycznie błędnych wyników.
Niespełniony warunek niezależności
Zasada mnożenia wymaga, by liczba możliwości na każdym etapie była stała. Jeśli na etapie 2 liczba opcji zależy od wyboru na etapie 1 (np. "nie mogę wybrać tego samego koloru"), prosta zasada mnożenia nie działa. Trzeba albo policzyć osobno, albo użyć wariacji/permutacji.
Nieuwzględnienie powtórzeń
W kodach PIN cyfry mogą się powtarzać (10 · 10 · 10 · 10), ale przy ustawianiu osób w kolejce każda osoba jest unikalna (n · (n-1) · (n-2) · ...). Trzeba uważnie przeczytać, czy powtórzenia są dozwolone.
Pominięcie etapu o jednej możliwości
Jeśli na pewnym etapie jest tylko 1 możliwość, wciąż trzeba go uwzględnić (mnożymy przez 1, co nie zmienia wyniku). Nie wolno natomiast dodawać 1 ani pomijać tego etapu, bo zmienia to strukturę problemu.
Porady i wskazówki
Rysuj drzewo decyzji: Przy wątpliwościach narysuj drzewo decyzji dla małych liczb. Drzewo natychmiast pokazuje, czy mnożyć, czy dodawać, i pozwala policzyć liście jako kontrolę.
Identyfikuj etapy: Przed obliczeniami jasno wypisz etapy i liczbę możliwości na każdym. Na przykład: "Etap 1: wybór koszulki (5). Etap 2: wybór spodni (4). Wynik: 5 · 4 = 20." Taka struktura zapobiega pomyłkom.
Sprawdź niezależność: Przed zastosowaniem zasady upewnij się, że liczba opcji na każdym etapie nie zmienia się w zależności od wcześniejszych wyborów. Jeśli się zmienia - to wariacja (n · (n-1) · ...) lub inny model.
Łącz z innymi zasadami: W złożonych zadaniach zasada mnożenia często łączy się z zasadą dodawania. Na przykład: "Ile jest numerów 3-cyfrowych parzystych?" - ostatnia cyfra to 5 opcji (0, 2, 4, 6, 8), ale pierwsza cyfra nie może być 0 (9 opcji), więc trzeba rozważyć przypadki osobno.
Przypadki szczególne
Dwa etapy
Najprostsza postać: czynność składa się z dwóch kroków. Pierwszy ma m możliwości, drugi ma n. Łączna liczba wyników to m · n.
Przykład: 3 koszulki i 4 pary spodni = 3 · 4 = 12 zestawów.
Jednakowe etapy (potęga)
Gdy na każdym z k etapów jest tyle samo możliwości (n), wynik to nk. Dotyczy kodów, haseł i ciągów z powtórzeniami.
Kod PIN z 4 cyfr: 104 = 10 000. Hasło z 8 małych liter: 268 ≈ 208 mld.
Malejąca liczba opcji (permutacje)
Gdy każdy wybrany element jest usuwany ze zbioru, liczba opcji maleje o 1 na każdym etapie. To prowadzi do permutacji i wariacji bez powtórzeń.
Ustawianie 3 osób z 5 w kolejce: 5 · 4 · 3 = 60 = V(5, 3).
Etap z zerem możliwości
Jeśli na którymkolwiek etapie jest 0 możliwości, cała czynność jest niewykonalna. Iloczyn zawierający 0 daje 0.
Nie ma żadnych zestawów, jeśli nie masz ani jednej pary butów, nawet gdy masz 10 koszulek i 5 par spodni.